In the semi-streaming model, an algorithm must process any \(n\)-vertex graph by making one or few passes over a stream of its edges, use \(\tilde{O}(n) := O(n \cdot \mathrm{polylog}(n))\) words of space, and at the end of the last pass, output a solution to the problem at hand. Approximating (single-source) shortest paths on undirected graphs is a longstanding open question in this model. In this work, we make progress on this question from both upper and lower bound fronts: 1) We present a simple randomized algorithm that for any \(\varepsilon \gt 0\), with high probability computes \((1+\varepsilon)\)-approximate shortest paths from a given source vertex in \(O\left( \frac{1}{\varepsilon} \cdot n \log^3 n \right)\) space and \(O\left( \frac{1}{\varepsilon} \cdot \left(\frac{\log n}{\log\log n}\right)^{2} \right)\) passes. The algorithm can also be derandomized and made to work on dynamic streams at a cost of some extra \(\mathrm{poly}(\log n,1/\varepsilon)\) factors only in the space. Previously, the best known algorithms for this problem required \(1/\varepsilon \cdot \log^{c}n\) passes, for an unspecified large constant \(c\). 2) We prove that any semi-streaming algorithm that with large constant probability outputs any constant approximation to shortest paths from a given source vertex (even to a single fixed target vertex and only the distance, not necessarily the path) requires \(\Omega\left( \frac{\log n}{\log\log n} \right)\) passes. We emphasize that our lower bound holds for any constant-factor approximation of shortest paths. Previously, only constant-pass lower bounds were known and only for small approximation ratios below two. Our results collectively reduce the gap in the pass complexity of approximating single-source shortest paths in the semi-streaming model from \(\mathrm{polylog}(n)\) vs. \(\omega(1)\) to only a quadratic gap.

We study graph coloring problems in the streaming model, wherein the goal is to process an \(n\)-vertex graph whose edges arrive in a stream, using a limited space that is much smaller than the trivial \(O(n^2)\) bound. While prior work has largely focused on coloring graphs with a large number of colors—typically as a function of the maximum degree—we explore the opposite end of the spectrum: deciding whether the input graph can be colored using only a few, say, a constant number of colors. We are interested in each of the adversarial, random order, or dynamic streams, and—as is the standard in this model—focus solely on the space complexity rather than running time. Our work lays the foundation for this new direction by establishing both upper and lower bounds on space complexity of key variants of the problem.

In the streaming set cover problem, m sets from a universe of size n are arriving one by one in a stream, and the algorithm is allowed to process the stream using one or a few passes and a space of o(mn), which is sublinear in the input size. The goal is to determine the minimal (or approximately minimal) number of sets that cover the universe at the end of the last pass.

In the distributed triangle detection problem, we have an n-vertex network G = (V, E) with one player for each vertex of the graph who sees the edges incident on the vertex. The players communicate in synchronous rounds using the edges of this network and have a limited bandwidth of O(log n) bits over each edge. The goal is to detect whether or not G contains a triangle as a subgraph in a minimal number of rounds.We prove that any protocol (deterministic or randomized) for distributed triangle detection requires Ω(log log n) rounds of communication. Prior to our work, only one-round lower bounds were known for this problem.The primary technique for proving these types of distributed lower bounds is via reductions from two-party communication complexity. However, it has been known for a while that this approach is provably incapable of establishing any meaningful lower bounds for distributed triangle detection. Our main technical contribution is a new information theoretic argument which combines recent advances on multi-pass graph streaming lower bounds with the point-to-point communication aspects of distributed models, and can be of independent interest.

We study the chain communication problem introduced by Cormode et al. [ICALP 2019]. For k ≥ 1, in the chain_{n,k} problem, there are k string and index pairs (X_i, σ_i) for i ∈ [k] such that the value at position σ_i in string X_i is the same bit for all k pairs. The input is shared between k+1 players as follows. Player 1 has the first string X₁ ∈ {0,1}ⁿ, player 2 has the first index σ₁ ∈ [n] and the second string X₂ ∈ {0,1}ⁿ, player 3 has the second index σ₂ ∈ [n] along with the third string X₃ ∈ {0,1}ⁿ, and so on. Player k+1 has the last index σ_k ∈ [n]. The communication is one way from each player to the next, starting from player 1 to player 2, then from player 2 to player 3 and so on. Player k+1, after receiving the message from player k, has to output a single bit which is the value at position σ_i in X_i for any i ∈ [k]. It is a generalization of the well-studied index problem, which is equivalent to chain_{n, 2}. Cormode et al. proved that the chain_{n,k} problem requires Ω(n/k²) communication, and they used it to prove streaming lower bounds for the approximation of maximum independent sets. Subsequently, Feldman et al. [STOC 2020] used it to prove lower bounds for streaming submodular maximization. However, it is not known whether the Ω(n/k²) lower bound used in these works is optimal for the problem, and in fact, it was conjectured by Cormode et al. that Ω(n) bits are necessary. We prove the optimal lower bound of Ω(n) for chain_{n,k} when k = o(n/log n) as our main result. This settles the open conjecture of Cormode et al., barring the range of k = Ω(n /log n). The main technique is a reduction to a non-standard index problem where the input to the players is such that the answer is biased away from uniform. This biased version of index is analyzed using tools from information theory. As a corollary, we get an improved lower bound for approximation of maximum independent set in vertex arrival streams via a reduction from chain directly.

A semi-streaming algorithm in dynamic graph streams processes any n-vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph and using O (n · polylog(n )) space. Semi-streaming algorithms for dynamic streams were first obtained in the seminal work of Ahn, Guha, and McGregor in 2012, alongside the introduction of the graph sketching technique, which remains the de facto way of designing algorithms in this model and a highly popular technique for designing graph algorithms in general.

In the semi-streaming model for processing massive graphs, an algorithm makes multiple passes over the edges of a given n-vertex graph and is tasked with computing the solution to a problem using O(n · log(n)) space. Semi-streaming algorithms for Maximal Independent Set (MIS) that run in O(loglogn) passes have been known for almost a decade, however, the best lower bounds can only rule out single-pass algorithms. We close this large gap by proving that the current algorithms are optimal: Any semi-streaming algorithm for finding an MIS with constant probability of success requires Ω(loglogn) passes. This settles the complexity of this fundamental problem in the semi-streaming model, and constitutes one of the first optimal multi-pass lower bounds in this model. We establish our result by proving an optimal round vs communication tradeoff for the (multi-party) communication complexity of MIS. The key ingredient of this result is a new technique, called hierarchical embedding, for performing round elimination: we show how to pack many but small hard (r−1)-round instances of the problem into a single r-round instance, in a way that enforces any r-round protocol to effectively solve all these (r−1)-round instances also. These embeddings are obtained via a novel application of results from extremal graph theory—in particular dense graphs with many disjoint unique shortest paths—together with a newly designed graph product, and are analyzed via information-theoretic tools such as direct-sum and message compression arguments.

We prove that any semi-streaming algorithm for $(1+\varepsilon)$ approximation of maximum bipartite matching requires \begin{equation*}\Omega\left(\frac{\log (1 / \varepsilon)}{\log (1 / \beta)}\right)\end{equation*} passes, where $\beta \in(0,1)$ is the largest parameter so that an n-vertex graph with $n^{\beta}$ edge-disjoint induced matchings of size $\Theta(n)$ exist (such graphs are referred to as Ruzsa-Szemerédi graphs). Currently, it is known that \begin{equation*}\Omega\left(\frac{1}{\log \log n}\right) \leqslant \beta \leqslant 1-\Theta\left(\frac{\log ^{*} n}{\log n}\right)\end{equation*} and closing this huge gap between upper and lower bounds has remained a notoriously difficult problem in combinatorics.Under the plausible hypothesis that $\beta=\Omega(1)$, our lower bound result provides the first pass-approximation lower bound for (small) constant approximation of matchings in the semi-streaming model, a longstanding open question in the graph streaming literature.Our techniques are based on analyzing communication protocols for compressing (hidden) permutations. Prior work in this context relied on reducing such problems to Boolean domain and analyzing them via tools like XOR Lemmas and Fourier analysis on Boolean hypercube. In contrast, our main technical contribution is a hardness amplification result for permutations through concatenation in place of prior XOR Lemmas. This result is proven by analyzing permutations directly via simple tools from group representation theory combined with detailed information-theoretic arguments, and can be of independent interest.

In this paper we study two fully-dynamic multi-dimensional vector load balancing problems with recourse. The adversary presents a stream of n job insertions and deletions, where each job j is a vector in ℝ^d_{≥ 0}. In the vector scheduling problem, the algorithm must maintain an assignment of the active jobs to m identical machines to minimize the makespan (maximum load on any dimension on any machine). In the vector bin packing problem, the algorithm must maintain an assignment of active jobs into a number of bins of unit capacity in all dimensions, to minimize the number of bins currently used. In both problems, the goal is to maintain solutions that are competitive against the optimal solution for the active set of jobs, at every time instant. The algorithm is allowed to change the assignment from time to time, with the secondary objective of minimizing the amortized recourse, which is the average cardinality of the change of the assignment per update to the instance. For the vector scheduling problem, we present two simple algorithms. The first is a randomized algorithm with an O(1) amortized recourse and an O(log d/log log d) competitive ratio against oblivious adversaries. The second algorithm is a deterministic algorithm that is competitive against adaptive adversaries but with a slightly higher competitive ratio of O(log d) and a per-job recourse guarantee bounded by Õ(log n + log d log OPT). We also prove a sharper instance-dependent recourse guarantee for the deterministic algorithm. For the vector bin packing problem, we make the so-called small jobs assumption that the size of all jobs in all the coordinates is O(1/log d) and present a simple O(1)-competitive algorithm with O(log n) recourse against oblivious adversaries. For both problems, the main challenge is to determine when and how to migrate jobs to maintain competitive solutions. Our central idea is that for each job, we make these decisions based only on the active set of jobs that are "earlier" than this job in some ordering ≺ of the jobs.

We continue the study of the communication complexity of gap cycle counting problems. These problems have been introduced by Verbin and Yu [SODA 2011] and have found numerous applications in proving streaming lower bounds. In the noisy gap cycle counting problem (NGC), there is a small integer k ≥ 1 and an n-vertex graph consisted of vertex-disjoint union of either k-cycles or 2k-cycles, plus O(n/k) disjoint paths of length k−1 in both cases (“noise”). The edges of this graph are partitioned between Alice and Bob whose goal is to decide which case the graph belongs to with minimal communication from Alice to Bob.