Estimating Gaps in Martingales and Applications to CoinTossing: Constructions and Hardness Consider designing a distributed cointossing protocol for n processors such that the probability of heads is X0 in 0,1, and an adversary can reset one processor to change the distribution of the final outcome. For X012, in the noncryptographic setting, Blumu0027s majority protocol is frac1sqrt2pi n insecure. For computationally bounded adversaries and any X0 in 0,1, the protocol of Moran,Naor,Segev (2009) is only O(1n) insecure. In this paper, we study discretetime martingales (X0,X1,..,Xn) such that Xi in 0,1, for all i in 0,..,n, and Xn in 0,1. In particular, for any X0 in 0,1, we construct martingales that yield frac12sqrtfracX_0(1X_0)n insecure cointossing protocols with nbit communication; irrespective of the number of bits required to represent the output distribution. Note that for sufficiently small X0, we achieve higher security than Moran et alu0027s protocol even against computationally unbounded adversaries. For X012, our protocol requires only 40% of the processors to obtain the same security as the majority protocol. We introduce a new inductive technique that uses geometric transformations to estimate the large gaps in these martingales. For any X0 in 0,1, we show that there exists a stopping time T such that mathbbEX_TX_T1geqfrac2sqrt2n1cdot X_0(1X_0). The inductive technique also constructs martingales that demonstrate the optimality of our bound  we construct optimal martingales such that any T hasmathbbEX_TX_T1leqfrac1sqrtncdotsqrtX_0(1X_0). Our lowerbound holds for all X0 in 0,1; while the previous bound of Cleve,Impagliazzo (1993) exists only for positive constant X0. Our approach only employs elementary techniques and avoids the complex probabilistic tools inherent to the approaches of Cleve,Impagliazzo (1993) and Beimel,Haitner,Makriyannis,Omri (2018).

Towards Optimal Moment Estimation in Streaming and Distributed Models One of the oldest problems in the data stream model is to approximate the pth moment mathcalX_pp  sum_i1n mathcalX_ip of an underlying vector mathcalX in mathbbRn, which is presented as a sequence of poly(n) updates to its coordinates. Of particular interest is when p in (0,2. Although a tight space bound of Theta(epsilon2 log n) bits is known for this problem when both positive and negative updates are allowed, surprisingly there is still a gap in the space complexity when all updates are positive. Specifically, the upper bound is O(epsilon2 log n) bits, while the lower bound is only Omega(epsilon2  log n) bits. Recently, an upper bound of tildeO(epsilon2  log n) bits was obtained assuming that the updates arrive in a random order.  :126,show that for p in (0, 1, the random order assumption is not needed. Namely, we give an upper bound for worstcase streams of tildeO(epsilon2  log n) bits for estimating mathcalX_pp. Our techniques also give new upper bounds for estimating the empirical entropy in a stream. On the other hand, we :126,show that for p in (1,2, in the natural coordinator and blackboard communication topologies, there is an tildeO(epsilon2) bit maxcommunication upper bound based on a randomized rounding scheme. Our protocols also give rise to protocols for heavy hitters and approximate matrix product. We generalize our results to arbitrary communication topologies G, obtaining an tildeO(epsilon2 log d) maxcommunication upper bound, where d is the diameter of G. Interestingly, our upper bound rules out natural communication complexitybased approaches for proving an Omega(epsilon2 log n) bit lower bound for p in (1,2 for streaming algorithms. In particular, any such lower bound must come from a topology with large diameter.