Streaming algorithms in adversarial settings have attracted considerable attention recently. We show that, in the white-box adversarial streaming model [Miklós Ajtai et al., 2022], the fundamental problem of estimating the F_p moment to within any constant factor requires Ω(n) memory. In this model, the internal state of the (randomized) streaming algorithm is visible to an adversary, who can exploit this information when constructing subsequent stream updates. As a corollary, we also obtain a white-box lower bound for the well-studied problem of estimating the maximum matching size in graphs. [Miklós Ajtai et al., 2022] proved that two-party white-box communication protocols can be derandomized. This allows them to prove deterministic communication lower bounds and automatically derive white-box (communication and streaming) lower bounds. However, such two-party lower bounds can only rule out approximation of the F_p moment within a specific constant factor. Ruling out approximation within any constant factor typically requires proving a lower bound for a multi-party communication problem. We show that white-box communication protocols involving any number of parties can be derandomized, provided they compute a total function. However, this derandomization fails entirely when extended to partial functions and, consequently, to approximation problems. We are therefore compelled to prove our moment estimation lower bound for the white-box model directly. Our proof introduces a novel hybrid technique that, instead of taking hybrids over input distributions, constructs hybrids over white-box adversaries.

Sampling a random walk is a fundamental primitive in many graph applications. In the streaming model, it is known that sampling an L-step random walk on an n-vertex directed graph requires Ω(n L) space, implying that no sublinear-space streaming algorithm exists for general graphs. We show that sublinear algorithms are possible for the case of dense graphs, where every vertex has out-degree at least Ω(n). In particular, we give a one-pass turnstile streaming algorithm that uses only 𝒪̃(L) memory for such graphs. More broadly, for graphs with minimum out-degree at least d, our streaming algorithm samples a random walk using 𝒪̃(n/d ⋅ L) memory. We show that our algorithm is optimal in a strong "beyond worst-case" sense. To formalize this, we introduce the notion of universal optimality for graph streaming algorithms. Informally, a streaming algorithm is universally optimal if it performs (almost) as well as possible on every graph, assuming a worst-case choice of the streaming order. This notion of universal optimality is a key conceptual contribution of our work.

Abstract. We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are [Formula: see text] players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex; this way, each edge is known by both its endpoints and is thus shared by two players. The players communicate in simultaneous rounds by posting their messages on a shared blackboard visible to all players, with the goal of computing an MIS of the graph. While the MIS problem is well studied in other distributed models and while shared blackboard is, perhaps, the simplest broadcast model, lower bounds for our problem were only known against one-round protocols. We present a lower bound on the round-communication tradeoff for computing an MIS in this model. Specifically, we show that, when [Formula: see text] rounds of interaction are allowed, at least one player needs to communicate [Formula: see text] bits. In particular, with logarithmic bandwidth, finding an MIS requires [Formula: see text] rounds. This lower bound can be compared with the algorithm of Ghaffari et al. [ Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018, pp. 129–138] that solves the MIS in [Formula: see text] rounds but with a logarithmic bandwidth for an average player. Additionally, our lower bound further extends to the closely related problem of maximal bipartite matching. The presence of edge-sharing gives the algorithms in our model a surprising power, and numerous algorithmic results exploiting this power are known. For a similar reason, proving lower bounds in this model is much more challenging because this sharing in the players’ inputs prohibits the use of standard number-in-hand communication complexity arguments. Thus, to prove our results, we devise a new round elimination framework, which we call partial-input embedding, that may also be useful in future work for proving round-sensitive lower bounds in the presence of shared inputs. Finally, we discuss several implications of our results to multiround (adaptive) distributed sketching algorithms, broadcast congested clique, and the welfare maximization problem in two-sided matching markets.

The seminal work of Ahn, Guha, and McGregor in 2012 introduced the graph sketching technique and used it to present the first streaming algorithms for various graph problems over dynamic streams with both insertions and deletions of edges. This includes algorithms for cut sparsification, spanners, matchings, and minimum spanning trees (MSTs). These results have since been improved or generalized in various directions, leading to a vastly rich host of efficient algorithms for processing dynamic graph streams.

We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are n players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex – this way, each edge is known by both its endpoints and is thus shared by two players. The players communicate in simultaneous rounds by posting their messages on a shared blackboard visible to all players, with the goal of computing an MIS of the graph. While the MIS problem is well studied in other distributed models, and while shared blackboard is, perhaps, the simplest broadcast model, lower bounds for our problem were only known against one-round protocols. We present a lower bound on the round-communication tradeoff for computing an MIS in this model. Specifically, we show that when r rounds of interaction are allowed, at least one player needs to communicate $\Omega(n^{1/20^{r+1}})$ bits. In particular, with logarithmic bandwidth, finding an MIS requires $\Omega(\log\log n)$ rounds. This lower bound can be compared with the algorithm of Ghaffari, Gouleakis, Konrad, Mitrović, and Rubinfeld [PODC 2018] that solves MIS in $O(\log\log n)$ rounds but with a logarithmic bandwidth for an average player. Additionally, our lower bound further extends to the closely related problem of maximal bipartite matching. The presence of edge-sharing gives the algorithms in our model a surprising power and numerous algorithmic results exploiting this power are known. For a similar reason, proving lower bounds in this model is much more challenging, as this sharing in the players’ inputs prohibits the use of standard number-in-hand communication complexity arguments. Thus, to prove our results, we devise a new round elimination framework, which we call partial-input embedding, that may also be useful in future work for proving round-sensitive lower bounds in the presence of shared inputs. Finally, we discuss several implications of our results to multi-round (adaptive) distributed sketching algorithms, broadcast congested clique, and to the welfare maximization problem in two-sided matching markets.

In the reliable transmission problem, a sender, Alice, wishes to transmit a bit-string x to a remote receiver, Bob, over a binary channel with adversarial noise. The solution to this problem is to encode x using an error correcting code. As it is long known that the distance of binary codes is at most 1/2, reliable transmission is possible only if the channel corrupts (flips) at most a 1/4-fraction of the communicated bits.We revisit the reliable transmission problem in the two-way setting, where both Alice and Bob can send bits to each other. Our main result is the construction of two-way error correcting codes that are resilient to a constant fraction of corruptions strictly larger than 1/4. Moreover, our code has constant rate and requires Bob to only send one short message. We mention that our result resolves an open problem by Haeupler, Kamath, and Velingker [APPROX-RANDOM, 2015] and by Gupta, Kalai, and Zhang [STOC, 2022].Curiously, our new two-way code requires a fresh perspective on classical error correcting codes: While classical codes have only one distance guarantee for all pairs of codewords (i.e., the minimum distance), we construct codes where the distance between a pair of codewords depends on the “compatibility” of the messages they encode. We also prove that such codes are necessary for our result.

In this paper we explore fundamental problems in randomized communication complexity such as computing SetIntersection on sets of size $k$ and EqualityTesting between vectors of length $k$. Sağlam and Tardos [ Proceedings of the 54 th Annual IEEE Symposium on Foundations of Computer Science, 2013, pp. 678--687] and Brody et al. [ Algorithmica, 76 (2016), pp. 796--845] showed that for these types of problems, one can achieve optimal communication volume of $O(k)$ bits, with a randomized protocol that takes $O(\log^* k)$ rounds. They also proved that this is one point along the optimal round-communication trade-off curve. Aside from rounds and communication volume, there is a third parameter of interest, namely the error probability $p_{{err}}$, which we write $2^{-E}$. It is straightforward to show that protocols for SetIntersection or EqualityTesting need to send at least $\Omega(k + E)$ bits, regardless of the number of rounds. Is it possible to simultaneously achieve optimality in all three parameters, namely $O(k + E)$ communication and $O(\log^* k)$ rounds? In this paper we prove that there is no universally optimal algorithm, and we complement the existing round-communication trade-offs [M. Sağlam and G. Tardos, Proceedings of the 54 th Annual IEEE Symposium on Foundations of Computer Science, 2013, pp. 678--687; J. Brody et al., Algorithmica, 76 (2016), pp. 796--845] with a new trade-off between rounds, communication, and probability of error. In particular, any protocol for solving multiple EqualityTesting in $r$ rounds with failure probability $p_{{err}} = 2^{-E}$ has communication volume $\Omega(Ek^{1/r})$. We present several algorithms for multiple EqualityTesting (and its variants) that match or nearly match our lower bound and the lower bound of [M. Sağlam and G. Tardos, Proceedings of the 54 th Annual IEEE Symposium on Foundations of Computer Science, 2013, pp. 678--687; J. Brody et al., Algorithmica, 76 (2016), pp. 796--845]. Lower bounds on EqualityTesting extend to SetIntersection for every $r, k,$ and $p_{{err}}$ (which is trivial); in the reverse direction, we prove that upper bounds on EqualityTesting for $r, k, p_{{err}}$ imply similar upper bounds on SetIntersection with parameters $r+1, k,$ and $p_{{err}}$. Our original motivation for considering $p_{{err}}$ as an independent parameter came from the problem of enumerating triangles in distributed (${CONGEST}$) networks having maximum degree $\Delta$. We prove that this problem can be solved in $O(\Delta/\log n + \log\log \Delta)$ time with high probability $1-1/{poly}(n)$. This beats the trivial (deterministic) $O(\Delta)$-time algorithm and is superior to the $\tilde{O}(n^{1/3})$ algorithm of [Y. Chang, S. Pettie, and H. Zhang, Proceedings of the 30 th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 821--840; Y. Chang and T. Saranurak, Proceedings of the ACM Symposium on Principles of Distributed Computing, 2019, pp. 66--73] when $\Delta=\tilde{O}(n^{1/3})$.

In this paper we explore fundamental problems in randomized communication complexity such as computing Set Intersection on sets of size k and Equality Testing between vectors of length k. Brody et al. [BCK+ 16] and Sağlam and Tardos [ST13] showed that for these types of problems, one can achieve optimal communication volume of O(k) bits, with a randomized protocol that takes O(log* k) rounds. They also proved [BCK+ 16, ST13] that this is one point along the optimal round-communication tradeoff curve. Aside from rounds and communication volume, there is a third parameter of interest, namely the error probability perr. It is straightforward to show that protocols for Set Intersection or Equality Testing need to send bits. Is it possible to simultaneously achieve optimality in all three parameters, namely communication and O(log* k) rounds? In this paper we prove that there is no universally optimal algorithm, and complement the existing round-communication trade-offs [BCK+ 16, ST13] with a new tradeoff between rounds, communication, and probability of error. In particular: Any protocol for solving Multiple Equality Testing in r rounds with failure probability perr = 2−E has communication volume Ω(Ek1/r). There exists a protocol for solving Multiple Equality Testing in r + log* (k/E) rounds with O(k + rEk1/r) communication, thereby essentially matching our lower bound and that of [BCK+ 16, ST13]. Lower bounds on Equality Testing extend to Set Intersection, for every r, k, and perr (which is trivial); in the reverse direction, upper bounds on Equality Testing for r, k, perr imply similar upper bounds on Set Intersection with parameters r + 1, k, and perr. Our original motivation for considering perr as an independent parameter came from the problem of enumerating triangles in distributed (CONGEST) networks having maximum degree Δ. We prove that this problem can be solved in O(Δ/log n + log log Δ) time with high probability 1 – 1/poly(n). This beats the trivial (deterministic) O(Δ)-time algorithm and is superior to the Õ(n1/3) algorithm of [CPZ19, CS19] when Δ = Õ(n1/3).