Niv Buchbinder

Niv Buchbinder, Moran Feldman, Siyue Liu et al.

We study random order semi-streaming algorithms for submodular maximization under a wide range of combinatorial constraint classes, including matroids, matroid $p$-parity, $p$-exchange systems and $p$-systems. For most of these classes of constraints, our results are the first improvement over what is known to be achievable for adversarial order. For matroids, matching and $p$-matchoids, previous random order results were known, and we improve over some of these as well. In the case of matroids, our improved results show a separation between adversarial and random order semi-streaming algorithms, and exponentially improve the number of passes necessary for getting $1 - 1/e - \varepsilon$ approximation for maximizing a monotone submodular function subject to a matroid constraint. We also prove a new hardness result showing a similar separation for $p$-systems. Our results are based on two new technical tools. One tool provides a general way to translate offline algorithms for many classes of constraints into random order semi-streaming algorithms. The other tool is a semi-streaming variant of a recently proposed offline algorithm for matroid constraints.

Niv Buchbinder, Iftach Haitner, Nissan Levi et al.

In a multi-party fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some adversarial parties try to bias the output. In this work we focus on the case of an arbitrary number of corrupted parties. Cleve [STOC 1986] has shown that in any such $m$-round coin-flipping protocol, the corrupted parties can bias the honest parties' common output bit by $Θ(1/m)$. For more than two decades, the best known coin-flipping protocol was the one of Awerbuch et al. [Manuscript 1985], who presented a $t$-party, $m$-round protocol with bias $Θ(t/\sqrt{m})$. This was changed by the breakthrough result of Moran et al. [TCC 2009], who constructed an $m$-round, two-party coin-flipping protocol with optimal bias $Θ(1/m)$. Haitner and Tsfadia [STOC 2014] constructed an $m$-round, three-party coin-flipping protocol with bias $O(\log^3m / m)$. Still for the case of more than three parties, the best known protocol remained the $Θ(t/\sqrt{m})$-bias protocol of Awerbuch et al. We make a step towards eliminating the above gap, presenting a $t$-party, $m$-round coin-flipping protocol, with bias $O(\frac{t^4 \cdot 2^t \cdot \sqrt{\log m}}{m^{1/2+1/\left(2^{t-1}-2\right)}})$ for any $t\le \tfrac12 \log\log m$. This improves upon the $Θ(t/\sqrt{m})$-bias protocol of Awerbuch et al., and in particular, for $t\in O(1)$ it is an $1/m^{\frac12 + Θ(1)}$-bias protocol. For the three-party case, it is an $O(\sqrt{\log m}/m)$-bias protocol, improving over the $O(\log^3m / m)$-bias protocol of Haitner and Tsfadia. Our protocol generalizes that of Haitner and Tsfadia, by presenting an appropriate recovery protocol for the remaining parties to interact in, in the case that some parties abort or are caught cheating. We prove the fairness of the new protocol by presenting a new paradigm for analyzing fairness of coin-flipping protocols.