algorithms satisfy Property (P2), we have that $S_{t-1}\in\\{\lfloor
s_{t-1}\rfloor,\lceil s_{t-1}\rceil\\}$.

Case I: $s_{t-1}\in\mathbb{Z}$. This is an easy case. It is immediate that
$\Pr_{\mathcal{D}}[X_{t}=1\bigm{|}\mathcal{E}]=x_{t}$ here. This is also not
hard to see this for the offline algorithm. Recall that the offline algorithm
starts with a copy $y$ of $x$. Since $s_{t-1}\in\mathbb{Z}$, the offline
algorithm would set $X_{i}$ for exactly $s_{t-1}$ indices $i\in[t-1]$ to one
(and the rest in $[t-1]$ to zero), and would then recursively run on the
suffix $(y_{t},y_{t+1},\ldots,y_{n})$ of $y$ with no correlation with the
rounding thus far. Furthermore, $y_{j}=x_{j}$ for all $j\geq t$. Thus, by
Property (P1) applied to this suffix, we have that
$\Pr_{\mathcal{D}^{\prime}}[X_{t}=1\bigm{|}\mathcal{E}]=x_{t}$ also.

We may thus assume from now on that $z\doteq s_{t-1}-\lfloor s_{t-1}\rfloor$
lies in $(0,1)$.

Case II: $s_{t-1}\not\in\mathbb{Z}$ and $z+x_{t}\leq 1$. An easy sub-case here
is that $S_{t-1}=\lceil s_{t-1}\rceil$; here, since both the offline and
online algorithms satisfy Property (P2), it is immediate that in this sub-case

$\Pr_{\mathcal{D}}[X_{t}=1\bigm{|}\mathcal{E}]=\Pr_{\mathcal{D}^{\prime}}[X_{t}=1\bigm{|}\mathcal{E}]=0.$

We may thus assume that $S_{t-1}=\lfloor s_{t-1}\rfloor$. By the definition of
the online algorithm 3 we have that

$\Pr_{\mathcal{D}}[X_{t}=1\bigm{|}\mathcal{E}]=\frac{x_{t}}{1-z}.$ (22)

We now analyze $\Pr_{\mathcal{D}^{\prime}}[X_{t}=1\bigm{|}\mathcal{E}]$.
Consider the offline algorithm _just before_ it involves $x_{t}$ in STEP: at
this point in time, it has:

  * •

set $\lfloor s_{t-1}\rfloor$ of the variables $(X_{i}:i<t)$ to one;

  * •

set $t-2-\lfloor s_{t-1}\rfloor$ of the variables $(X_{i}:i<t)$ to zero; and,
recalling again that the offline algorithm starts with a copy $y$ of $x$,

  * •

it has assigned the current value $z$ to one variable $y_{i^{*}}$ where
$i^{*}\in[t-1]$ is a random variable from some distribution.

At this point, the offline algorithm is basically recursively run on the
sequence $(y_{i^{*}},y_{t},y_{t+1},\ldots,y_{n})$, where $y_{i^{*}}=z$ and
$y_{j}=x_{j}$ for all $j\geq t$. Crucially, since $S_{t-1}=\lfloor
s_{t-1}\rfloor$, the conditioning on $\mathcal{E}$ says that the variable
$y_{i^{*}}$ is _eventually rounded to $0$_. Thus, we can compute
$\Pr_{\mathcal{D}^{\prime}}[X_{t}=1\bigm{|}\mathcal{E}]$ as follows. Suppose
the offline algorithm is run on the sequence
$(u_{1},u_{2},\ldots,u_{n-t+2})\doteq(y_{i^{*}},y_{t},y_{t+1},\ldots,y_{n})$,
to output a random bit-vector $(U_{1},U_{2},\ldots,U_{n-t+2})$; then,

$\Pr_{\mathcal{D}^{\prime}}[X_{t}=1\bigm{|}\mathcal{E}]=\Pr_{\mathcal{D}^{\prime}}[U_{2}=1\bigm{|}U_{1}=0].$
(23)

But since $u_{1}+u_{2}=z+x_{t}\leq 1$, the first STEP applied to $u_{1}$ and
$u_{2}$ ensures that _at most one of $u_{1}$ and $u_{2}$ gets rounded to one_.
This yields

$\Pr_{\mathcal{D}^{\prime}}[U_{2}=1\bigm{|}U_{1}=0]=\frac{Pr_{\mathcal{D}^{\prime}}[(U_{2}=1)\wedge(U_{1}=0)]}{Pr_{\mathcal{D}^{\prime}}[U_{1}=0]}=\frac{Pr_{\mathcal{D}^{\prime}}[U_{2}=1]}{Pr_{\mathcal{D}^{\prime}}[U_{1}=0]}=\frac{x_{t}}{1-z},$

where the second equality holds since at most one of $U_{1}$ and $U_{2}$ is
one; we are thus done by (22).

Case III: $s_{t-1}\not\in\mathbb{Z}$ and $z+x_{t}>1$. This is handled
similarly. The easy sub-case here is that $S_{t-1}=\lfloor s_{t-1}\rfloor$;
here, since both the offline and online algorithms satisfy Property (P2), it
is immediate that

$\Pr_{\mathcal{D}}[X_{t}=1\bigm{|}\mathcal{E}]=\Pr_{\mathcal{D}^{\prime}}[X_{t}=1\bigm{|}\mathcal{E}]=1.$

We may thus assume that $S_{t-1}=\lceil s_{t-1}\rceil$. By the definition of
the online algorithm 3 we have that

$\Pr_{\mathcal{D}}[X_{t}=1\bigm{|}\mathcal{E}]=\frac{x_{t}+z-1}{z}.$ (24)

Now, the offline algorithm is, like in Case II, essentially run on the
sequence
$(u_{1},u_{2},\ldots,u_{n-t+2})\doteq(y_{i^{*}},y_{t},y_{t+1},\ldots,y_{n})$—where
$y_{i^{*}}$ is initially $z$—to output a random bit-vector
$(U_{1},U_{2},\ldots,U_{n-t+2})$, _with the key difference from Case II being
that $U_{1}$ will eventually be set to $1$_. So,

$\Pr_{\mathcal{D}^{\prime}}[X_{t}=1\bigm{|}\mathcal{E}]=\Pr_{\mathcal{D}^{\prime}}[U_{2}=1\bigm{|}U_{1}=1].$
(25)

Now, since $u_{1}+u_{2}=z+x_{t}>1$, the first STEP applied to $u_{1}$ and
$u_{2}$ ensures that _at least_ one of $u_{1}$ and $u_{2}$ gets rounded to
one. This implies

$\displaystyle\Pr_{\mathcal{D}^{\prime}}[U_{2}=1\bigm{|}U_{1}=1]$
$\displaystyle=$
$\displaystyle\frac{Pr_{\mathcal{D}^{\prime}}[U_{2}=1]-Pr[(U_{2}=1)\wedge(U_{1}=0)]}{Pr_{\mathcal{D}^{\prime}}[U_{1}=1]}$
$\displaystyle=$
$\displaystyle\frac{Pr_{\mathcal{D}^{\prime}}[U_{2}=1]-Pr_{\mathcal{D}^{\prime}}[U_{1}=0]}{Pr_{\mathcal{D}^{\prime}}[U_{1}=1]}$
$\displaystyle=$ $\displaystyle\frac{x_{t}+z-1}{z},$

where the second equality holds since at least one of $U_{1}$ and $U_{2}$ is
one; we are thus done by (24). This concludes the proof of the inductive step.
∎

##  Appendix C Deferred Proofs of Section 4

In this section we provide deferred proofs of claims from Section 4, restated
below for ease of reference.

See 4.7

###### Proof of 4.7.

Taking the derivative of $g(y)$, we get

$g^{\prime}(y)=\exp(-(1-y)\cdot(1+\delta))\cdot\left((1-\epsilon)-(1-y\cdot(1-\epsilon))\cdot(1+\delta)\right),$

which vanishes at $y^{*}=\frac{\epsilon+\delta}{(1-\epsilon)(1+\delta)}$.
Next, we consider the second derivative of $g$.

$g^{\prime\prime}(y)=g^{\prime}(y)\cdot(1+\delta)+\exp(-(1-y)\cdot(1+\delta))\cdot(1-\epsilon)\cdot(1+\delta).$

The first summand, $g^{\prime}(y)\cdot(1+\delta)$, vanishes at $y^{*}$, by the
above, while the second summand is positive, since $\epsilon\leq 1$ and
$\delta\geq 0$. We conclude that $y^{*}$ is the global minimum of $g$. ∎

See 4.8

###### Proof.

Fix $\epsilon,\delta$. For notational simplicity, let $f=f_{\epsilon,\delta}$
and let $z^{*}=z^{*}_{\epsilon,\delta}$. Since $f$ is the sum of twice-
differentiable convex functions (namely an exponential and a linear term), we
have that $f^{\prime\prime}(z)\geq 0$ for all $z$. Therefore, if
$f^{\prime}(z^{*})\geq 0$, then for all $z\geq z^{*}$ we have that

$\displaystyle
f^{\prime}(z)=f^{\prime}(z^{*})+\int_{z^{*}}^{z}f^{\prime\prime}(x)\,dx\geq
f^{\prime}(z^{*})\geq 0.$

Thus, if moreover $f(z^{*})\geq 0$, then the desired statement follows, i.e.,
for all $x\geq z^{*}$ we have that

$\displaystyle f(z)$
$\displaystyle=f(z^{*})+\int_{z^{*}}^{z}f^{\prime}(x)\,dx\geq f(z^{*})\geq
0.\qed$

###  C.1 Polytime implementation

So far, we ignored computational aspects of our ODRS of 4.9. In this section
we show how our grouping method used to increase our rounding ratio beyond
$1-\frac{1}{e}$ moreover allows us to compute $\Pr[P_{t}=S]$ for all sets
$S\subseteq[n]$ in polynomial time — and thus obtain a polytime ODRS — while
only decreasing our rounding ratio by an arbitrarily small constant
$\gamma>0$.

See 4.10

###### Proof.

First, we scale down all the fractions $x_{i,t}$ by a $(1-\gamma)$ factor
(this results in a valid fractional matching). As this additional downscaling
is linear, this results in each offline node having fractional degree
$\hat{s}_{i,t}\leq 1-\gamma$ in the assignment $\hat{x}$, by 4.5.
Consequently, by the same argument as 4.3, each bin but at most one in
$B\in\mathcal{B}_{t}$ has $\sum_{i\in B}\hat{x}_{i,t}\leq\frac{\gamma}{2}$.
But since
$\sum_{i}\hat{x}_{i,t}\leq\sum_{i}x_{i,t}\cdot(1+\delta)\leq(1+\delta)$, this
implies that each bin but one has total $x$-value at least $\sum_{i\in
B}x_{it}\geq\gamma/2(1+\delta)$. Consequently, by the fractional matching
constraint, whereby $\sum_{i}x_{i,t}\leq 1$, there are at most
$2(1+\delta)/\gamma+1=O(1/\gamma)$ such non-empty bins.

The benefit of few bins is that now at each time $t$ the set of bidders is a
set of at most $O(1/\gamma)$ offline nodes, and so there are at most
$n^{O(1/\epsilon)}$ possible sets $S\subseteq[n]$ in the support of the
distribution over $P_{t}$. Moreover, for each such set $S\subseteq[n]$, it is
straightforward to compute the probability that $S$ is the set of first-time
proposers at time $t$ in time $n^{O(1/\gamma)}$. (Briefly, for each subset
$S$, we guess for each of the $O(1/\gamma)$ nodes in $S$ at what time they
made their first bid. The probability of each of these $n^{O(1/\gamma)}$
guessed events is then easy to compute in polynomial time, by computing the
probability that these nodes did bid in these guessed time steps and no other
times.) All in all, this allows to compute, exactly, the support of the
distribution of $P_{t}$, in time $n^{O(1/\gamma)}$. Therefore, by 2.1, the CRS
invocations take time $\mathrm{poly}(n^{O(1/\gamma)}=n^{O(1/\gamma)}$ per time
step. On the other hand, having scaled down the values $x_{i,t}$ by a factor
of $(1-\gamma)$ trivially incurs a multiplicative loss of $(1-\gamma)$ in the
rounding ratio, and so the obtained ODRS has rounding ratio of
$\ratio(1-\gamma)\geq\ratio-\gamma$. ∎

###  C.2 Deferred proofs of the $b$-matching ODRS

In this section we prove that our extension of Algorithm 4 from matching to
$b$-matchings results in similar benefits when much grouping occurs. We start
by introducing some useful notation.

Our online level-set rounding algorithm, Algorithm 3, makes at most one random
choice when deciding whether to allocate another online node to the center of
the star. Our $b$-matching ODRS follows the same logic (from the perspective
of the offline node, playing the role of the star’s center). Denote by
$C_{i,t}$ an indicator for the relevant coin for $i$ coming up heads. Our
extended core ODRS, Algorithm 4, correlates these coins for different offline
nodes $i$ at time $t$. Let $S_{i,t}\in\\{\lfloor s_{i,t}\rfloor,\lceil
s_{i,t}\rceil\\}$ be the number of times $i$ bids by time $t$. By our
algorithm’s definition, we have the following expression for
$[S_{i,t}\neq\lceil s_{i,t}\rceil]$.

$\displaystyle[S_{i,t}\neq\lceil
s_{i,t}\rceil]=\begin{cases}[S_{i,t-1}\neq\lceil
s_{i,t-1}\rceil]\cdot(1-C_{i,t-1})&\textrm{if }\lceil s_{i,t}\rceil=\lceil
s_{i,t-1}\rceil\\\ 1-[S_{i,t-1}=\lceil s_{i,t-1}\rceil]\cdot
C_{i,t-1}&\textrm{if }\lceil s_{i,t}\rceil>\lceil s_{i,t-1}\rceil.\end{cases}$

######  Lemma C.1.

For any time $t$, the random variables $\\{S_{i,t}\\}_{i}$ are NA.

###### Proof.

Proof by induction on $t\geq 1$. The base case is trivial, as $S_{i,1}=0$
deterministically for all $i$. We turn to the inductive step for $t$, assuming
that the variables $S_{i,t-1}$ are NA. First, by 2.4, for any bin
$B\in\mathcal{B}_{t-1}$ at time $t-1$, the binary variables $C_{i,t-1}$ for
all nodes $i\in B$, whose sum is at most one, are NA. Moreover, the
distributions over different bins are independent, and so by closure of NA
under products (2.5), all $C_{i,t-1}$ are NA. Moreover, the variables
$C_{i,t-1}$ are independent from the variables $S_{i,t-1}$ (who are functions
only of $C_{i,t^{\prime}}$ for all $t^{\prime}<t-1$), and consequently, by our
inductive hypothesis and another application of closure of NA under products
(2.5), all the variables $\\{S_{i,t-1},C_{i,t-1}\\}_{i}$ are NA. Therefore,
since $S_{i,t-1}\in[\lfloor s_{i,t-1}\rfloor,\lceil s_{i,t-1}\rceil]$, we find
that $[S_{i,t}\neq\lceil s_{i,t}\rceil]$ is a decreasing function of
$S_{i,t-1}$ and $C_{i,t-1}$, i.e., they are decreasing functions of disjoint
NA variables. Therefore, by yet another application of closure of NA under
products (2.5), the events $\\{[S_{i,t}\neq\lceil s_{i,t}\rceil]\\}_{i}$ are
NA. Finally, since $S_{i,t}=\lceil s_{i,t}\rceil-[S_{i,t}\neq\lceil
s_{i,t}\rceil]$ are monotone decreasing functions of NA variables, the
variables $S_{i,t}$ are themselves NA, as desired. ∎

We are now ready to prove that our generalization of Algorithm 4 results in
bins essentially simulating offline nodes bidding with a probability equal to
their constituent nodes’ bids. That is, we are ready to prove the following
generalization of 4.4.

######  Lemma C.2.

For any time $t$ and set of offline nodes $S\subseteq[n]$, the $b$-matching
extension of Algorithm 4 satisfies

$\Pr[S\cap P_{t}\neq\emptyset]\geq
1-\prod_{B\in\mathcal{B}_{t}}\left(1-\sum_{i\in B\cap S}x_{it}\right).$

###### Proof.

We denote by $\mathcal{B}^{\prime}_{t}\subseteq\mathcal{B}_{t}$ the set of
singleton bins $B=\\{i\\}$ for which $\lceil s_{i,t+1}\rceil>\lceil
s_{i,t}\rceil$. For such bins $B\in\mathcal{B}^{\prime}_{t}$, $B=\\{i\\}$, we
have that $\Pr[P_{t}\cap S\cap B=\emptyset]=1-x_{i,t}$. For other bins
$B\in\mathcal{B}_{t}\setminus\mathcal{B}^{\prime}_{t}$, we have that $\Pr[i\in
P_{t}]=x_{i,t}$, by independence of $C_{i,t}$ and $S_{i,t}$ and since
$\Pr[C_{i,t}]=\frac{x_{i,t}}{1-(s_{i,t}-\lfloor s_{i,t}\rfloor)}$ and
$\Pr[S_{i,t}=\lfloor s_{i,t}\rfloor]=s_{i,t}-\lfloor s_{i,t}\rfloor$ (the
latter following from our online level-set algorithm’s analysis). Therefore,
by $\sum_{i\in B}C_{i,t}\leq 1$ implying disjointness of the events $[i\in
P_{t}]$ for $i\in B$, we have that $\Pr[P_{t}\cap S\cap
B=\emptyset]=1-\sum_{i\in B\cap S}x_{i,t}$. It remains to show that the events
$[P_{t}\cap S\cap B=\emptyset]$ for different $B$ are negative cylinder
dependent, giving the desired inequality,

$\displaystyle\Pr[P_{t}\cap
S=\emptyset]=\Pr\left[\bigwedge_{B\in\mathcal{B}_{t}}(P_{t}\cap S\cap
B=\emptyset)\right]\leq\prod_{B\in\mathcal{B}_{t}}\Pr[P_{t}\cap S\cap
B=\emptyset]=\prod_{B\in\mathcal{B}_{t}}\left(1-\sum_{i\in B\cap
S}x_{i,t}\right).$

Now, for bins $B=\\{i\\}\in\mathcal{B}^{\prime}_{t}$, we have that
$\mathds{1}[P_{t}\cap S\cap B=\emptyset]=1-[S_{i,t}=\lceil s_{i,t}\rceil]\cdot
C_{i,t}$. For non-singleton bins $B\in\mathcal{B}_{t}$, we have that
$\mathds{1}[P_{t}\cap S\cap B=\emptyset]=1-\sum_{i\in B\cap
S}C_{i,t}\cdot[S_{i,t}=\lfloor s_{i,t}\rfloor]$. In both cases, the indicators
$\mathds{1}[P_{t}\cap S\cap B=\emptyset]$ are NA, as they are monotone
decreasing functions of disjoint NA variables (here, we need to first apply
decreasing functions that map $S_{i,t}$ to $\lceil s_{i,t}\rceil-S_{i,t}$ for
all $i\in B\in\mathcal{B}_{t}\setminus\mathcal{B}^{\prime}_{t}$ and all other
variables to themselves). Hence, by closure of NA under such functions (2.5),
the variables $\mathds{1}[P_{t}\cap S\cap B=\emptyset]$ are NA. Therefore, by
2.3, these variables are negative cylinder dependent, yielding the required
inequality above. The lemma follows. ∎

##  Appendix D Deferred Proofs of Section 6

In this section we prove that any sufficiently many binary variables must
contain some $2^{r}$ with some (near-)positive $2^{r}$-wise correlation,
generalizing the special case of $r=1$ given by 6.1. See 6.3

###### Proof.

We prove this claim for all $0\leq\epsilon\leq p\leq 1$ by induction on $r\geq
1$, and note that the claim is trivial if $p^{2^{r}}\leq\epsilon$, in which
case the RHS is negative, so $n_{r}(p,\epsilon)=2^{r}$ suffices. 6.1 proves
the base case, showing that
$n_{1}(p,\epsilon)\leq\lceil\frac{2p}{\epsilon}+1\rceil$ suffices. To prove
the inductive step, consider a set of
$k:=n_{1}(p,\frac{\epsilon}{2^{2^{r}}})+2m$ variables
$Y_{1},\dots,Y_{k}\sim\mathrm{Ber}(p)$, for $m$ to be determined shortly.
Then, we find a sequence of disjoint pairs
$I_{1},I_{2},\dots,I_{m}\subseteq[n]$, where for each $I_{s}=\\{i,j\\}$,
$s\in[m]$, we have that
$\mathrm{Cov}(Y_{i},Y_{j})\geq-\frac{\epsilon}{2^{2^{r}}}$. The existence of
such pairs follows by repeatedly invoking 6.1 applied to the variables
$\\{Y_{i}\mid i\in[n]\setminus\bigcup_{\ell=1}^{s}{I_{\ell}}\\}$ to obtain the
pair $I_{s+1}$. Now, for each pair $I_{s}=\\{i,j\\}$ as above, define a new
variable $Z_{s}:=Y_{i}\cdot Y_{j}$. By
$\mathrm{Cov}(Y_{i},Y_{j})\geq-\frac{\epsilon}{2^{2^{r}}}$, we have that
$\Pr[Z_{s}]\geq p^{2}-\frac{\epsilon}{2^{2^{r}}}$. Next, couple these combined
variables with equiprobable variables
$A_{s}\sim\mathrm{Ber}(p^{2}-\frac{\epsilon}{2^{2^{r}}})$ with $Z_{s}\geq
A_{s}$ always. Then, if we take
$m=n_{r-1}(p^{2}-\frac{\epsilon}{2^{2^{r}}},\frac{\epsilon}{2})$, the
inductive hypothesis applied to the $m$ variables $A_{s}$ implies the
existence of a subset $S\subseteq[m]$ of $2^{r-1}$ of these variables
satisfing the following.

$\displaystyle\mathbb{E}\left[\prod_{i\in\bigcup_{s\in S}I_{s}}Y_{i}\right]$
$\displaystyle=\mathbb{E}\left[\prod_{s\in
S}Z_{s}\right]\geq\mathbb{E}\left[\prod_{s\in
S}A_{s}\right]\geq\left(p^{2}-\frac{\epsilon}{2^{2^{r}}}\right)^{2^{r-1}}-\frac{\epsilon}{2}\geq
p^{2^{r}}-2^{2^{r-1}}\cdot\frac{\epsilon}{2^{2^{r}}}-\frac{\epsilon}{2}\geq
p^{2^{r}}-\epsilon.$

Above, the first inequality follows by the coupling $Z_{s}\geq A_{s}$, the
second inequality follows from the inductive hypothesis, the third inequality
follows from $(a-b)^{k}\geq a^{k}-2^{k}\cdot b$ for any $a,b\in[0,1]$ and
$k\in\mathbb{N}$ (as seen by expanding $(a-b)^{k}$), and the final inequality
follows from $2^{2^{r}-1}\geq 2^{2^{r-1}}$ for $r\geq 1$. We conclude that
$\\{Y_{i}\mid i\in\bigcup_{s\in S}I_{s}\\}$ is the desired subset of $2^{r}$
variables in $Y_{1},\dots,Y_{n}$. ∎

######  Remark D.1.

We did not attempt to optimize the minimum possible $n_{r}(p,\epsilon)$ above.
Nonetheless, for concrete bounds, we note that if $p^{2^{r}}\geq\epsilon$,
then our proof yields bounds satisfying the following recurrence.

$\displaystyle n_{1}(p,\epsilon)$
$\displaystyle\leq\left\lceil\frac{2p}{\epsilon}+1\right\rceil\leq\frac{4p}{\epsilon},$
$\displaystyle n_{r}(p,\epsilon)$ $\displaystyle\leq
n_{1}\left(p,\frac{\epsilon}{2^{2^{r}}}\right)+2n_{r-1}\left(p^{2}-\frac{\epsilon}{2^{2^{r}}},\frac{\epsilon}{2}\right)\leq\frac{4\cdot
2^{2^{r}}p}{\epsilon}+2n_{r-1}\left(p^{2}-\frac{\epsilon}{2^{2^{r}}},\frac{\epsilon}{2}\right).$

Noting that this recurrence is monotone increasing in $p$, we have that
$n_{r}(p,\epsilon)=O\left(2^{2^{r}}\cdot\frac{p}{\epsilon}\right)$.

## References

  * [1] Algorithms with predictions (ALPS).  https://algorithms-with-predictions.github.io/.  Accessed: 2022-11-07.
  * Aggarwal et al. [2011] Aggarwal, G., Goel, G., Karande, C., and Mehta, A. 2011\.  Online vertex-weighted bipartite matching and single-bid budgeted allocations.  In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1253–1264.
  * Aggarwal et al. [2003] Aggarwal, G., Motwani, R., Shah, D., and Zhu, A. 2003\.  Switch scheduling via randomized edge coloring.  In Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS). 502–512.
  * Agrawal et al. [2009] Agrawal, R., Gollapudi, S., Halverson, A., and Ieong, S. 2009\.  Diversifying search results.  In Proceedings of the 2nd Symposium on Web Search and Data Mining (WSDM). 5–14.
  * Ahmed et al. [2017] Ahmed, F., Dickerson, J. P., and Fuge, M. D. 2017\.  Diverse weighted bipartite b-matching.  In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), C. Sierra, Ed. 35–41.
  * Bahmani et al. [2012] Bahmani, B., Mehta, A., and Motwani, R. 2012\.  Online graph edge-coloring in the random-order arrival model.  Theory of Computing 8, 1, 567–595.
  * Bansal and Cohen [2021] Bansal, N. and Cohen, I. R. 2021\.  Contention resolution, matrix scaling and fair allocation.  In Proceedings of the 19th Workshop on Approximation and Online Algorithms (WAOA). 252–274.
  * Bar-Noy et al. [1992] Bar-Noy, A., Motwani, R., and Naor, J. 1992\.  The greedy algorithm is optimal for on-line edge coloring.  Information Processing Letters (IPL) 44, 5, 251–253.
  * Bechtel et al. [2022] Bechtel, C., Dughmi, S., and Patel, N. 2022\.  Delegated Pandora’s box.  666–693.
  * Bhattacharya et al. [2021] Bhattacharya, S., Grandoni, F., and Wajc, D. 2021\.  Online edge coloring algorithms via the nibble method.  In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2830–2842.
  * Birnbaum and Mathieu [2008] Birnbaum, B. and Mathieu, C. 2008\.  On-line bipartite matching made simple.  ACM SIGACT News 39, 1, 80–87.
  * Blanc and Charikar [2021] Blanc, G. and Charikar, M. 2021\.  Multiway online correlated selection.  In Proceedings of the 62nd Symposium on Foundations of Computer Science (FOCS). 1277–1284.
  * Borcea et al. [2009] Borcea, J., Brändén, P., and Liggett, T. 2009\.  Negative dependence and the geometry of polynomials.  Journal of the American Mathematical Society 22, 2, 521–567.
  * Boyce [1982] Boyce, B. 1982\.  Beyond topicality: A two stage view of relevance and the retrieval process.  Info. Processing and Management 18, 105––109.
  * Brändén and Jonasson [2012] Brändén, P. and Jonasson, J. 2012\.  Negative dependence in sampling.  Scandinavian Journal of Statistics 39, 4, 830–838.
  * Braverman et al. [2022] Braverman, M., Derakhshan, M., and Molina Lovett, A. 2022\.  Max-weight online stochastic matching: Improved approximations against the online benchmark.  In Proceedings of the 23rd ACM Conference on Economics and Computation (EC). 967–985.
  * Buchbinder et al. [2023] Buchbinder, N., Naor, J. S., and Wajc, D. 2023\.  Lossless online rounding for online bipartite matching (despite its impossibility).  In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). To appear.
  * Buolamwini and Gebru [2018] Buolamwini, J. and Gebru, T. 2018\.  Gender shades: Intersectional accuracy disparities in commercial gender classification.  In Proceedings of the 1stConference on Fairness, Accountability and Transparency (FAccT), S. A. Friedler and C. Wilson, Eds. Proceedings of Machine Learning Research (PMLR) Series, vol. 81. 77–91.
  * Calinescu et al. [2011] Calinescu, G., Chekuri, C., Pál, M., and Vondrák, J. 2011\.  Maximizing a monotone submodular function subject to a matroid constraint.  SIAM Journal on Computing (SICOMP) 40, 6, 1740–1766.
  * Carbonell and Goldstein [2017] Carbonell, J. G. and Goldstein, J. 2017\.  The use of MMR, diversity-based reranking for reordering documents and producing summaries.  SIGIR Forum 51, 2, 209–210.
  * Chawla et al. [2010] Chawla, S., Hartline, J. D., Malec, D. L., and Sivan, B. 2010\.  Multi-parameter mechanism design and sequential posted pricing.  In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC). 311–320.
  * Chekuri et al. [2010] Chekuri, C., Vondrák, J., and Zenklusen, R. 2010\.  Dependent randomized rounding via exchange properties of combinatorial structures.  In Proceedings of the 51st Symposium on Foundations of Computer Science (FOCS). 575–584.
  * Chekuri et al. [2011] Chekuri, C., Vondrák, J., and Zenklusen, R. 2011\.  Multi-budgeted matchings and matroid intersection via dependent rounding.  In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1080–1097.
  * Chekuri et al. [2014] Chekuri, C., Vondrák, J., and Zenklusen, R. 2014\.  Submodular function maximization via the multilinear relaxation and contention resolution schemes.  SIAM Journal on Computing (SICOMP) 43, 6, 1831–1879.
  * Christofides and Vaggelatou [2004] Christofides, T. C. and Vaggelatou, E. 2004\.  A connection between supermodular ordering and positive/negative association.  Journal of Multivariate analysis 88, 1, 138–151.
  * Clarke et al. [2008] Clarke, C. L. A., Kolla, M., Cormack, G. V., Vechtomova, O., Ashkan, A., Büttcher, S., and MacKinnon, I. 2008\.  Novelty and diversity in information retrieval evaluation.  In Proceedings of the 31st ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR). 659–666.
  * Cohen et al. [2019] Cohen, I. R., Peng, B., and Wajc, D. 2019\.  Tight bounds for online edge coloring.  In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS). 1–25.
  * Cohen and Wajc [2018] Cohen, I. R. and Wajc, D. 2018\.  Randomized online matching in regular graphs.  In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 960–979.
  * Devanur et al. [2013] Devanur, N. R., Jain, K., and Kleinberg, R. D. 2013\.  Randomized primal-dual analysis of ranking for online bipartite matching.  In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 101–107.
  * Dickerson et al. [2019] Dickerson, J. P., Sankararaman, K. A., Srinivasan, A., and Xu, P. 2019\.  Balancing relevance and diversity in online bipartite matching via submodularity.  In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI). 1877–1884.
  * Dubhashi et al. [2007] Dubhashi, D., Jonasson, J., and Ranjan, D. 2007\.  Positive influence and negative dependence.  Combinatorics, Probability and Computing 16, 01, 29–41.
  * Dubhashi and Ranjan [1996] Dubhashi, D. and Ranjan, D. 1996\.  Balls and bins: A study in negative dependence.  BRICS Report Series 3, 25\.
  * Dughmi [2020] Dughmi, S. 2020\.  The outer limits of contention resolution on matroids and connections to the secretary problem.  In Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP). 42:1–42:18.
  * Dughmi [2022] Dughmi, S. 2022\.  Matroid secretary is equivalent to contention resolution.  In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS). 58:1–58:23.
  * [35] Dütting, P., Feldman, M., Kesselheim, T., and Lucier, B. Prophet inequalities made easy: Stochastic optimization by pricing nonstochastic inputs.  SIAM Journal on Computing (SICOMP) 49, 3\.
  * Eden et al. [2021] Eden, A., Feldman, M., Fiat, A., and Segal, K. 2021\.  An economics-based analysis of ranking for online bipartite matching.  In Proceedings of the 4th Symposium on Simplicity in Algorithms (SOSA). 107–110.
  * Ehsani et al. [2018] Ehsani, S., Hajiaghayi, M., Kesselheim, T., and Singla, S. 2018\.  Prophet secretary for combinatorial auctions and matroids.  In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 700–714.
  * Ezra et al. [2020] Ezra, T., Feldman, M., Gravin, N., and Tang, Z. G. 2020\.  Online stochastic max-weight matching: prophet inequality for vertex and edge arrival models.  In Proceedings of the 21st ACM Conference on Economics and Computation (EC). 769–787.
  * Fahrbach et al. [2020] Fahrbach, M., Huang, Z., Tao, R., and Zadimoghaddam, M. 2020\.  Edge-weighted online bipartite matching.  In Proceedings of the 61st Symposium on Foundations of Computer Science (FOCS). 412–423.
  * Feige and Vondrák [2006] Feige, U. and Vondrák, J. 2006\.  The allocation problem with submodular utility functions.  In Proceedings of the 47th Symposium on Foundations of Computer Science (FOCS).
  * Feldman et al. [2009] Feldman, J., Korula, N., Mirrokni, V., Muthukrishnan, S., and Pál, M. 2009\.  Online ad assignment with free disposal.  In Proceedings of the 5th Conference on Web and Internet Economics (WINE). 374–385.
  * Feldman et al. [2015] Feldman, M., Gravin, N., and Lucier, B. 2015\.  Combinatorial auctions via posted prices.  In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 123–135.
  * Feldman et al. [2016] Feldman, M., Svensson, O., and Zenklusen, R. 2016\.  Online contention resolution schemes.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1014–1033.
  * Gandhi et al. [2006] Gandhi, R., Khuller, S., Parthasarathy, S., and Srinivasan, A. 2006\.  Dependent rounding and its applications to approximation algorithms.  Journal of the ACM (JACM) 53, 3, 324–360.
  * Gao et al. [2021] Gao, R., He, Z., Huang, Z., Nie, Z., Yuan, B., and Zhong, Y. 2021\.  Improved online correlated selection.  In Proceedings of the 62nd Symposium on Foundations of Computer Science (FOCS). 1265–1276.
  * Hosseini et al. [2022] Hosseini, H., Huang, Z., Igarashi, A., and Shah, N. 2022\.  Class fairness in online matching.  arXiv preprint arXiv:2203.03751.
  * Huang et al. [2022] Huang, Z., Shu, X., and Yan, S. 2022\.  The power of multiple choices in online stochastic matching.  In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC). 91–103.
  * Huang and Tao [2019] Huang, Z. and Tao, R. 2019\.  Understanding zadimoghaddam’s edge-weighted online matching algorithm: Unweighted case.  arXiv preprint arXiv:1910.02569.
  * Joag-Dev and Proschan [1983] Joag-Dev, K. and Proschan, F. 1983\.  Negative association of random variables with applications.  The Annals of Statistics, 286–295.
  * Kalyanasundaram and Pruhs [2000] Kalyanasundaram, B. and Pruhs, K. R. 2000\.  An optimal deterministic algorithm for online $b$-matching.  Theoretical Computer Science (TCS) 233, 1, 319–325.
  * Karp et al. [1990] Karp, R. M., Vazirani, U. V., and Vazirani, V. V. 1990\.  An optimal algorithm for on-line bipartite matching.  In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC). 352–358.
  * Kleinberg and Weinberg [2012] Kleinberg, R. and Weinberg, S. M. 2012\.  Matroid prophet inequalities.  In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC). 123–136.
  * Kong [2022] Kong, Y. 2022\.  Are “intersectionally fair” ai algorithms really fair to women of color? a philosophical analysis.  In Proceedings of the 5thConference on Fairness, Accountability, and Transparency (FAccT). 485–494.
  * Krengel and Sucheston [1978] Krengel, U. and Sucheston, L. 1978\.  On semiamarts, amarts, and processes with finite value.  Probability on Banach spaces 4, 197–266.
  * Kulkarni et al. [2022] Kulkarni, J., Liu, Y. P., Sah, A., Sawhney, M., and Tarnawski, J. 2022\.  Online edge coloring via tree recurrences and correlation decay.  In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC). 2958–2977.
  * Lattanzi et al. [2020] Lattanzi, S., Lavastida, T., Moseley, B., and Vassilvitskii, S. 2020\.  Online scheduling via learned weights.  In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1859–1877.
  * Lavastida et al. [2021] Lavastida, T., Moseley, B., Ravi, R., and Xu, C. 2021\.  Learnable and instance-robust predictions for online matching, flows and load balancing.  In Proceedings of the 29th Annual European Symposium on Algorithms (ESA). 59:1–59:17.
  * Lee and Singla [2018] Lee, E. and Singla, S. 2018\.  Optimal online contention resolution schemes via ex-ante prophet inequalities.  In Proceedings of the 26th Annual European Symposium on Algorithms (ESA).
  * Li and Xian [2021] Li, S. and Xian, J. 2021\.  Online unrelated machine load balancing with predictions revisited.  In International Conference on Machine Learning. 6523–6532.
  * Mehta et al. [2007] Mehta, A., Saberi, A., Vazirani, U., and Vazirani, V. 2007\.  Adwords and generalized online matching.  Journal of the ACM (JACM) 54, 5, 22.
  * Mitzenmacher and Vassilvitskii [2020] Mitzenmacher, M. and Vassilvitskii, S. 2020\.  Algorithms with predictions.  CoRR abs/2006.09123.
  * Papadimitriou et al. [2021] Papadimitriou, C., Pollner, T., Saberi, A., and Wajc, D. 2021\.  Online stochastic max-weight bipartite matching: Beyond prophet inequalities.  In Proceedings of the 22nd ACM Conference on Economics and Computation (EC). 763–764.
  * Pemantle and Peres [2014] Pemantle, R. and Peres, Y. 2014\.  Concentration of lipschitz functionals of determinantal and other strong rayleigh measures.  Combinatorics, Probability and Computing 23, 1, 140–160.
  * Pollner et al. [2022] Pollner, T., Roghani, M., Saberi, A., and Wajc, D. 2022\.  Improved online contention resolution for matchings and applications to the gig economy.  In Proceedings of the 23rd ACM Conference on Economics and Computation (EC). 321–322.
  * Saberi and Wajc [2021] Saberi, A. and Wajc, D. 2021\.  The greedy algorithm is _not_ optimal for on-line edge coloring.  In Proceedings of the 48th International Colloquium on Automata, Languages and Programming (ICALP). 109:1–109:18.
  * Srinivasan [2001] Srinivasan, A. 2001\.  Distributions on level-sets with applications to approximation algorithms.  In Proceedings of the 42nd Symposium on Foundations of Computer Science (FOCS). 588–597.
  * Srinivasan [2007] Srinivasan, A. 2007\.  Approximation algorithms for stochastic and risk-averse optimization.  In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1305–1313.
  * Swamy and Shmoys [2006] Swamy, C. and Shmoys, D. B. 2006\.  Approximation algorithms for 2-stage stochastic optimization problems.  ACM SIGACT News 37, 1, 33–46.
  * Swamy and Shmoys [2012] Swamy, C. and Shmoys, D. B. 2012\.  Sampling-based approximation algorithms for multistage stochastic optimization.  SIAM Journal on Computing (SICOMP) 41, 4, 975–1004.
  * Tang et al. [2022] Tang, Z. G., Wu, J., and Wu, H. 2022\.  (fractional) online stochastic matching via fine-grained offline statistics.  In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC). 77–90.
  * Torrico and Toriello [2022] Torrico, A. and Toriello, A. 2022\.  Dynamic relaxations for online bipartite matching.  INFORMS Journal on Computing 34, 4, 1841–2382.
  * Vazirani [2001] Vazirani, V. V. 2001\.  Approximation algorithms. Vol. 1.  Springer.
  * Wajc [2020] Wajc, D. 2020\.  Matching theory under uncertainty.  Ph.D. thesis, Carnegie Mellon University.
  * Williamson and Shmoys [2011] Williamson, D. P. and Shmoys, D. B. 2011\.  The design of approximation algorithms.  Cambridge university press.