We revisit several fundamental graph problems in the deterministic two-party communication model. Our main contributions include: - We give a new Õ(n^{3/2})-bit protocol for computing a maximum matching in general graphs. While the same upper bound can be obtained by simulating the classic algorithms of Micali-Vazirani [Silvio Micali and Vijay V. Vazirani, 1980] and Gabow [Harold N. Gabow, 2017], our protocol is conceptually simple and avoids the intricacies of finding a maximal set of shortest augmenting paths. - We give a new Õ(n)-bit protocol for negative-cycle detection and negative-weight single-source shortest paths. Our protocol simplifies that of Blikstad et al. [Joakim Blikstad et al., 2022] by replacing a long chain of reductions with a more direct approach based on vertex potentials. - We give a combinatorial Õ(n)-bit protocol for computing a maximum matching in bipartite graphs, obtained by reinterpreting the near-linear communication protocol of Blikstad et al. [Joakim Blikstad et al., 2022] through a discretized analysis. Together, these results provide simpler protocols for several basic graph problems. We hope they will inspire further advances on the communication complexity of a wide range of graph problems.

The space complexity of deterministic streaming algorithms for approximating the length of the longest increasing subsequence (LIS) in a string of length n has been known to be Θ̃(√n) for almost two decades. In contrast, the space complexity of this problem for randomized streaming algorithms remains one of the few longstanding open problems in one-pass streaming. In fact, no better than Ω(log n) lower bounds are known, and the best upper bounds are no better than their deterministic counterparts. In this paper, we push the limits of our understanding of the streaming space complexity of the approximate LIS length problem by studying it in the white-box adversarial streaming model. This model is an intermediate model between deterministic and randomized streaming algorithms that has recently attracted attention. In the white-box model, the streaming algorithm can draw fresh randomness when processing each incoming element, but an adversary generating the stream observes all previously used randomness and adaptively chooses the subsequent elements of the stream. We prove a tight (up to logarithmic factors) Ω(√n) space lower bound for any white-box streaming algorithm that approximates the length of the LIS of a stream of length n to within a factor better than 1.1. Thus, for this problem, white-box algorithms offer no improvement over deterministic ones.

Abstract. In this work, we prove an [Formula: see text] unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in [Formula: see text]-node directed acyclic graphs under edge insertions. This is the first super-logarithmic lower bound for any natural graph problem. In proving the lower bound, we also make novel contributions to the state-of-the-art data structure lower bound techniques that we hope may lead to further progress in proving lower bounds.

In the static retrieval problem, a data structure must answer retrieval queries mapping a set of n keys in a universe $[U]$ to v-bit values. Information-theoretically, retrieval data structures can use as little as nv bits of space. For small value sizes v, it is possible to achieve $O(1)$ query time while using space $n v+o(n)$ bits-whether or not such a result is possible for larger values of v (e.g., $v=\Theta(\log n)$) has remained open.In this paper, we obtain a tight lower bound (as well as matching upper bounds) for the static retrieval problem. In the case where values are large, we show that there is actually a significant tension between time and space. It is not possible, for example, to get $O(1)$ query time using $n v+o(n)$ bits of space, when $v=\Theta(\log n)$ (and assuming the word RAM model with $O(\log n)$-bit words)At first glance, our lower bound would seem to render retrieval unusable in many settings that aim to achieve very low redundancy. However, our second result offers a way around this: We show that, whenever a retrieval data structure $D_{1}$ is stored along with another data structure $D_{2}$ (whose size is similar to or larger than the size of $D_{1}$), it is possible to implement the combined data structure $D_{1} \cup D_{2}$ so that queries to $D_{1}$ take $O(1)$ time, operations on $D_{2}$ take the same asymptotic time as if $D_{2}$ were stored on its own, and the total space is $n v+\operatorname{Space}\left(D_{2}\right)+n^{0.67}$ bits.

Computing the approximate quantiles or ranks of a stream is a fundamental task in data monitoring. Given a stream of elements x1,x2,. ..,xn and a query x, a relative-error quantile estimation algorithm can estimate the rank of x with respect to the stream, up to a multiplicative ±∈ · rank(x ) error. Notably, this requires the sketch to obtain more precise estimates for the ranks of elements on the tails of the distribution, as compared to the additive ±en error regime. This is particularly favorable for some practical applications, such as anomaly detection.

The majority of streaming problems are defined and analyzed in a static setting, where the data stream is any worst-case sequence of insertions and deletions which is fixed in advance. However, many real-world applications require a more flexible model, where an adaptive adversary may select future stream elements after observing the previous outputs of the algorithm. Over the last few years, there has been increased interest in proving lower bounds for natural problems in the adaptive streaming model. In this work, we give the first known adaptive attack against linear sketches for the well-studied$\ell_{0}$-estimation problem over turnstile, integer streams. For any linear streaming algorithm$\mathcal{A}$which uses sketching matrix$\mathbf{A}\varepsilon \mathbb{Z}^{r\times n}$, this attack makes$\tilde{\mathcal{O}}(r^{8})$queries and succeeds with high constant probability in breaking the sketch. Additionally, we give an adaptive attack against linear sketches for the$\ell_{0}$-estimation problem over finite fields$\mathbb{F}_{p}$, which requires a smaller number of$\tilde{\mathcal{O}}(r^{3})$queries. Finally, we provide an adaptive attack over$\mathbb{R}^{n}$against linear sketches A$\in \mathbb{R}^{r\times \mathfrak{n}}$for$\ell_{0}$-estimation, in the setting where A has all nonzero subdeterminants at least$\frac{1}{\text{poly}(r)}$. Our results provide an exponential improvement over the previous number of queries known to break an$\ell_{0}$-estimation sketch.

A single-player game of Memory is played with $n$ distinct pairs of cards, with the cards in each pair bearing identical pictures. The cards are laid face-down. A move consists of revealing two cards, chosen adaptively. If these cards match, i.e., they bear the same picture, they are removed from play; otherwise, they are turned back to face down. The object of the game is to clear all cards while minimizing the number of moves. Past works have thoroughly studied the expected number of moves required, assuming optimal play by a player has that has perfect memory. In this work, we study the Memory game in a space-bounded setting. We prove two time-space tradeoff lower bounds on algorithms (strategies for the player) that clear all cards in $T$ moves while using at most $S$ bits of memory. First, in a simple model where the pictures on the cards may only be compared for equality, we prove that $ST = Ω(n^2 \log n)$. This is tight: it is easy to achieve $ST = O(n^2 \log n)$ essentially everywhere on this tradeoff curve. Second, in a more general model that allows arbitrary computations, we prove that $ST^2 = Ω(n^3)$. We prove this latter tradeoff by modeling strategies as branching programs and extending a classic counting argument of Borodin and Cook with a novel probabilistic argument. We conjecture that the stronger tradeoff $ST = \widetildeΩ(n^2)$ in fact holds even in this general model.

Dictionaries have been one of the central questions in data structures. A dictionary data structure maintains a set of key-value pairs under insertions and deletions such that given a query key, the data structure efficiently returns its value. The state-of-the-art dictionaries [4] store n key-value pairs with only O(n log(k) n) bits of redundancy, and support all operations in O(k) time, for k ≤ log* n. It was recently shown to be optimal [16].

Estimating the ε-approximate quantiles or ranks of a stream is a fundamental task in data monitoring. Given a stream x_1,..., x_n from a universe \mathcalU with total order, an additive-error quantile sketch \mathcalM allows us to approximate the rank of any query y\in \mathcalU up to additive ε n error. In 2001, Greenwald and Khanna gave a deterministic algorithm (GK sketch) that solves the ε-approximate quantiles estimation problem using O(ε^-1 łog(ε n)) space \citegreenwald2001space ; recently, this algorithm was shown to be optimal by Cormode and Vesleý in 2020 \citecormode2020tight. However, due to the intricacy of the GK sketch and its analysis, over-simplified versions of the algorithm are implemented in practical applications, often without any known theoretical guarantees. In fact, it has remained an open question whether the GK sketch can be simplified while maintaining the optimal space bound. In this paper, we resolve this open question by giving a simplified deterministic algorithm that stores at most (2 + o(1))ε^-1 łog (ε n) elements and solves the additive-error quantile estimation problem; as a side benefit, our algorithm achieves a smaller constant factor than the \frac11 2 ε^-1 łog(ε n) space bound in the original GK sketch~\citegreenwald2001space. Our algorithm features an easier analysis and still achieves the same optimal asymptotic space complexity as the original GK sketch. Lastly, our simplification enables an efficient data structure implementation, with a worst-case runtime of O(łog(1/ε) + łog łog (ε n)) per-element for the ordinary ε-approximate quantile estimation problem. Also, for the related "weighted'' quantile estimation problem, we give efficient data structures for our simplified algorithm which guarantee a worst-case per-element runtime of O(łog(1/ε) + łog łog (ε W_n/w_\textrmmin )), achieving an improvement over the previous upper bound of \citeassadi2023generalizing.

Graph sketching is a powerful paradigm for analyzing graph structure via linear measurements introduced by Ahn, Guha, and McGregor (SODA'12) that has since found numerous applications in streaming, distributed computing, and massively parallel algorithms, among others. Graph sketching has proven to be quite successful for various problems such as connectivity, minimum spanning trees, edge or vertex connectivity, and cut or spectral sparsifiers. Yet, the problem of approximating shortest path metric of a graph, and specifically computing a spanner, is notably missing from the list of successes. This has turned the status of this fundamental problem into one of the most longstanding open questions in this area. We present a partial explanation of this lack of success by proving a strong lower bound for a large family of graph sketching algorithms that encompasses prior work on spanners and many (but importantly not also all) related cut-based problems mentioned above. Our lower bound matches the algorithmic bounds of the recent result of Filtser, Kapralov, and Nouri (SODA'21), up to lower order terms, for constructing spanners via the same graph sketching family. This establishes near-optimality of these bounds, at least restricted to this family of graph sketching techniques, and makes progress on a conjecture posed in this latter work.

In this work, we prove a $\tilde{\Omega}(\lg^{3/2} n)$ unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions. This is the first super-logarithmic lower bound for any natural graph problem. In proving the lower bound, we also make novel contributions to the state-of-the-art data structure lower bound techniques that we hope may lead to further progress in proving lower bounds.

Augmented B-trees (aB-trees) are a broad class of data structures. The seminal work “succincter” by Pǎtraşcu [1] showed that any aB-tree can be stored using only two bits of redundancy, while supporting queries to the tree in time proportional to its depth. It has been a versatile building block for constructing succinct data structures, including rank/select data structures, dictionaries, locally decodable arithmetic coding, storing balanced parenthesis, etc.In this paper, we show how to “dynamize” an aB-tree. Our main result is the design of dynamic aB-trees (daB-trees) with branching factor two using only three bits of redundancy (with the help of lookup tables that are of negligible size in applications), while supporting updates and queries in time polynomial in its depth. As an application, we present a dynamic rank/select data structure for n-bit arrays, also known as a dynamic fully indexable dictionary (FID) [2]. It supports updates and queries in $O(\log n / \log \log n)$ time, and when the array has m ones, the \begin{equation*}\log \begin{pmatrix}n \\m\end{pmatrix}+On / 2^{\log 0.199} n\end{equation*}bits. Note that the update and query times are optimal even without space constraints due to a lower bound by Fredman and Saks [3]. Prior to our work, no dynamic FID with near-optimal update and query times and redundancy $o(n / \log n)$ was known. We further show that a dynamic sequence supporting insertions, deletions and rank/select queries can be maintained in (optimal) $O(\log n / \log \log n)$ time and with $O\left(n \cdot \operatorname{poly} \log \log n / \log ^{2} n\right)$ bits of redundancy.

A dictionary data structure maintains a set of at most n keys from the universe $[U]$ under key insertions and deletions, such that given a query $x \in[U]$, it returns if x is in the set. Some variants also store values associated to the keys such that given a query x, the value associated to x is returned when x is in the set.This fundamental data structure problem has been studied for six decades since the introduction of hash tables in 1953. A hash table occupies $O(n \log U)$ bits of space with constant time per operation in expectation. There has been a vast literature on improving its time and space usage. The state-of-the-art dictionary by Bender, Farach-Colton, Kuszmaul, Kuszmaul and Liu [1] has space consumption close to the information-theoretic optimum, using a total of \begin{equation*}\log \begin{pmatrix} U \\ n \end{pmatrix}+On\log ^{\left(k\right)} n\end{equation*} bits, while supporting all operations in $O(k)$ time, for any parameter $k \leq \log ^{*} n$. The term $O\left(\log ^{(k)} n\right)=O(\underbrace{\log \cdots \log n})$ is referred to as the wasted bits per key.In this paper, we prove a matching cell-probe lower bound: For $U=n^{1+\Theta(1)}$, any dictionary with $O\left(\log ^{(k)} n\right)$ wasted bits per key must have expected operational time $\Omega(k)$, in the cell-probe model with word-size $w=\Theta(\log U)$. Furthermore, if a dictionary stores values of $\Theta(\log U)$ bits, we show that regardless of the query time, it must have $\Omega(k)$ expected update time. It is worth noting that this is the first cell-probe lower bound on the trade-off between space and update time for general data structures.

We consider the Max-Cut problem, asking how much space is needed by a streaming algorithm in order to estimate the value of the maximum cut in a graph. This problem has been extensively studied over the last decade, and we now have a near-optimal lower bound for one-pass streaming algorithms, showing that they require linear space to guarantee a better-than-2 approximation [50, 52]. This result relies on a lower bound for the cycle-finding problem, showing that it is hard for a one-pass streaming algorithm to find a cycle in a union of matchings. The end-goal of our research is to prove a similar lower bound for multi-pass streaming algorithms that guarantee a better-than-2 approximation for Max-Cut, a highly challenging open problem. In this paper, we take a significant step in this direction, showing that even o(log n)-pass streaming algorithms need nΩ(1) space to solve the cycle-finding problem. Our proof is quite involved, dividing the cycles in the graph into “short” and “long” cycles, and using tailor-made lower bound techniques to handle each case.

In this paper, we prove a strong XOR lemma for bounded-round two-player randomized communication. For a function $f:\mathcal{X}\times \mathcal{Y}\rightarrow\{0,1\}$, the n-fold XOR function $f^{\oplus n}:\mathcal{X}^{n}\times \mathcal{Y}^{n}\rightarrow\{0,1\}$ maps n input pairs $(X_{1},\ldots,\ X_{n},\ Y_{1},\ldots\,\ Y_{n})$ to the XOR of the n output bits $f(X_{1},\ Y_{1})\oplus\cdots\oplus f(X_{n},\ Y_{n})$. We prove that if every r-round communication protocols that computes f with probability 2/3 uses at least C bits of communication, then any r-round protocol that computes $f^{\oplus n}$ with probability $1/2+\exp(-O(n))$ must use $n\cdot(r^{-O(r)}\cdot C-1)$ bits. When r is a constant and C is sufficiently large, this is $\Omega(n\cdot C)$ bits. It matches the communication cost and the success probability of the trivial protocol that computes the n bits $f(X_{i},\ Y_{i})$ independently and outputs their XOR, up to a constant factor in n. A similar XOR lemma has been proved for f whose communication lower bound can be obtained via bounding the discrepancy [17]. By the equivalence between the discrepancy and the correlation with 2-bit communication protocols [19], our new XOR lemma implies the previous result.

Storing a counter incremented N times would naively consume O(log N) bits of memory. In 1978 Morris described the very first streaming algorithm: the "Morris Counter" [15]. His algorithm's space bound is a random variable, and it has been shown to be O(log log N + log(1/ε) + log(1/δ)) bits in expectation to provide a (1+ε)-approximation with probability $1-δ to the counter's value. We provide a new simple algorithm with a simple analysis showing that randomized space O(log log N + log(1/ε) + log log(1/δ)) bits suffice for the same task, i.e. an exponentially improved dependence on the inverse failure probability. We then provide a new analysis showing that the original Morris Counter itself, after a minor but necessary tweak, actually also enjoys this same improved upper bound. Lastly, we prove a new lower bound for this task showing optimality of our upper bound. We thus completely resolve the asymptotic space complexity of approximate counting. Furthermore all our constants are explicit, and our lower bound and tightest upper bound differ by a multiplicative factor of at most 3+o(1).

For positive integers $U$, $n$, and $\sigma$, given a set $S$ of $n$ (distinct) keys from key space $[U]$, each associated with a value from $[\sigma]$, the static dictionary problem asks one to preprocess these (key, value) pairs into a data structure, supporting value-retrieval queries: for any given $x\in [U]$, ${valRet}(x)$ must return the value associated with $x$ if $x\in S$, or return $\bot$ if $x\notin S$. The special case where $\sigma=1$ is called the membership problem. The “textbook” solution is to use a hash table, which occupies linear space and answers each query in constant time. On the other hand, the minimum possible space to encode all (key, value) pairs is only ${OPT}:= \lceil\lg_2\binom{U}{n}+n\lg_2 \sigma\rceil$ bits, which could be much smaller than a hash table. In this paper, we design a randomized dictionary data structure using ${OPT}+{poly}\lg n+O(\lg^{(\ell)} U)$ bits of space, and it has expected constant query time, assuming the query algorithm can access an external lookup table of size $n^{\epsilon}$ for any constant $\ell$ and $\epsilon$. The lookup table depends only on $U$, $n$, and $\sigma$, and not the input. Previously, even for membership queries and $U\leq n^{O(1)}$, the best known data structure with constant query time requires ${OPT}+n/{poly}\lg n$ bits of space (Pagh [ SIAM J. Comput., 31 (2001), pp. 353--363] and Pǎtraşcu [ FOCS, IEEE Computer Society, Los Alamitos, CA, 2008, pp. 305--313]); the best known using ${OPT}+n^{1-\epsilon}$ space has query time $O(\lg n)$. Our new data structure answers open questions by Pǎtraşcu and Thorup [ FOCS, IEEE Computer Society, Los Alamitos, CA, 2008, pp. 305--313; Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 109 (2013), pp. 7--13]. We also present a scheme that compresses a sequence $X\in[\sigma]^n$ to its zeroth order (empirical) entropy up to $\sigma\cdot{poly}\lg n$ extra bits, supporting decoding each $X_i$ in $O(\lg \sigma)$ expected time.

For a directed graph G with n vertices and a start vertex u_start, we wish to (approximately) sample an L-step random walk over G starting from u_start with minimum space using an algorithm that only makes few passes over the edges of the graph. This problem found many applications, for instance, in approximating the PageRank of a webpage. If only a single pass is allowed, the space complexity of this problem was shown to be Θ̃(n ⋅ L). Prior to our work, a better space complexity was only known with Õ(√L) passes. We essentially settle the space complexity of this random walk simulation problem for two-pass streaming algorithms, showing that it is Θ̃(n ⋅ √L), by giving almost matching upper and lower bounds. Our lower bound argument extends to every constant number of passes p, and shows that any p-pass algorithm for this problem uses Ω̃(n ⋅ L^{1/p}) space. In addition, we show a similar Θ̃(n ⋅ √L) bound on the space complexity of any algorithm (with any number of passes) for the related problem of sampling an L-step random walk from every vertex in the graph.

In this paper, we study the distributed sketching complexity of connectivity. In distributed graph sketching, an n-node graph G is distributed to n players such that each player sees the neighborhood of one vertex. The players then simultaneously send one message to the referee, who must compute some function of G with high probability. For connectivity, the referee must output whether G is connected. The goal is to minimize the message lengths. Such sketching schemes are equivalent to one-round protocols in the broadcast congested clique model. We prove that the expected average message length must be at least Ω(log3 n) bits, if the error probability is at most 1/4. It matches the upper bound obtained by the AGM sketch [AGM12], which even allows the referee to output a spanning forest of G with probability 1 – 1/poly n. Our lower bound strengthens the previous Ω(log3 n) lower bound for spanning forest computation [NY19]. Hence, it implies that connectivity, a decision problem, is as hard as its “search” version in this model.

We give an almost quadratic n2−o(1) lower bound on the space consumption of any o(√logn)-pass streaming algorithm solving the (directed) s-t reachability problem. This means that any such algorithm must essentially store the entire graph. As corollaries, we obtain almost quadratic space lower bounds for additional fundamental problems, including maximum matching, shortest path, matrix rank, and linear programming.

Consider the following gap cycle counting problem in the streaming model: The edges of a 2-regular n-vertex graph G are arriving one-by-one in a stream and we are promised that G is a disjoint union of either k-cycles or 2k-cycles for some small k; the goal is to distinguish between these two cases using a limited memory. Verbin and Yu [SODA 2011] introduced this problem and showed that any single-pass streaming algorithm solving it requires n1-Ω(1/k)space. This result and the proof technique behind it-the Boolean Hidden Hypermatching communication problem-has since been used extensively for proving streaming lower bounds for various problems, including approximating MAX-CUT, matching size, property testing, matrix rank and Schatten norms, streaming unique games and CSPs, and many others. Despite its significance and broad range of applications, the lower bound technique of Verbin and Yu comes with a key weakness that is also inherited by all subsequent results: the Boolean Hidden Hypermatching problem is hard only if there is exactly one round of communication and, in fact, can be solved with logarithmic communication in two rounds. Therefore, all streaming lower bounds derived from this problem only hold for single-pass algorithms. Our goal in this paper is to remedy this state-of-affairs. We prove the first multi-pass lower bound for the gap cycle counting problem: Any p-pass streaming algorithm that can distinguish between disjoint union of k-cycles vs 2k-cycles-or even k-cycles vs one Hamiltonian cycle-requires n1-1/kΩ(1/p)space. This makes progress on multiple open questions in this line of research dating back to the work of Verbin and Yu. As a corollary of this result and by simple (or even no) modification of prior reductions, we can extend many of previous lower bounds to multi-pass algorithms. For instance, we can now prove that any streaming algorithm that ( 1+ε) -approximates the value of MAX-CUT, maximum matching size, or rank of an n-by- n matrix, requires either nΩ(1)space or Ω(log(1/ε)) passes. For all these problems, prior work left open the possibility of even an O(logn) space algorithm in only two passes.

The membership problem asks to maintain a set $S\subseteq[u]$, supporting insertions and membership queries, i.e., testing if a given element is in the set. A data structure that computes exact answers is called a dictionary. When a (small) false positive rate $ε$ is allowed, the data structure is called a filter. The space usages of the standard dictionaries or filters usually depend on the upper bound on the size of $S$, while the actual set can be much smaller. Pagh, Segev and Wieder (FOCS'13) were the first to study filters with varying space usage based on the current $|S|$. They showed in order to match the space with the current set size $n=|S|$, any filter data structure must use $(1-o(1))n(\log(1/ε)+(1-O(ε))\log\log n)$ bits, in contrast to the well-known lower bound of $N\log(1/ε)$ bits, where $N$ is an upper bound on $|S|$. They also presented a data structure with almost optimal space of $(1+o(1))n(\log(1/ε)+O(\log\log n))$ bits provided that $n>u^{0.001}$, with expected amortized constant insertion time and worst-case constant lookup time. In this work, we present a filter data structure with improvements in two aspects: - it has constant worst-case time for all insertions and lookups with high probability; - it uses space $(1+o(1))n(\log (1/ε)+\log\log n)$ bits when $n>u^{0.001}$, achieving optimal leading constant for all $ε=o(1)$. We also present a dictionary that uses $(1+o(1))n\log(u/n)$ bits of space, matching the optimal space in terms of the current size, and performs all operations in constant time with high probability.

In this paper, we present a new algorithm for maintaining linear sketches in turnstile streams with faster update time. As an application, we show that log n Count sketches or CountMin sketches with a constant number of columns (i.e., buckets) can be implicitly maintained in worst-case O(log0.582 n) update time using O(log n) words of space, on a standard word RAM with word-size w = Θ(log n). The exponent 0.582 ≈ 2ω/3 – 1, where ω is the current matrix multiplication exponent. Due to the numerous applications of linear sketches, our algorithm improves the update time for many streaming problems in turnstile streams, in the high success probability setting, without using more space, including ℓ2 norm estimation, ℓ2 heavy hitters, point query with ℓ1 or ℓ2 error, etc. Our algorithm generalizes, with the same update time and space, to maintaining log n linear sketches, where each sketch partitions the coordinates into k < logo(l) n buckets using a c-wise independent hash function for constant c, maintains the sum of coordinates for each bucket. Moreover, if arbitrary word operations are allowed, the update time can be further improved to O(log0.187 n), where 0.187 ≈ ω/2 – 1. Our update algorithm is adaptive, and it circumvents the non-adaptive cell-probe lower bounds for turnstile streaming algorithms by Larsen, Nelson and Nguyên (STOC’15). On the other hand, our result also shows that proving unconditional cell-probe lower bound for the update time seems very difficult, even if the space is restricted to be (nearly) the optimum. If ω = 2, the cell-probe update time of our algorithm would be logo(l) n. Hence, proving any higher lower bound would imply ω > 2.

Motivated by storage applications, we study the following data structure problem: an encoder wishes to store a collection of jointly-distributed files : = (X1, X2, …, Xn) ∼ µ which are correlated (Hµ ≤ Σi Hµ(Xi)), using as little (expected) memory as possible, such that each individual file Xi can be recovered quickly with few (ideally constant) memory accesses. In the case of independent random files, a dramatic result by Pǎtraşcu (FOCS’08) and subsequently by Dodis, Pǎtraşcu and Thorup (STOC’10) shows that it is possible to store using just a constant number of extra bits beyond the information-theoretic minimum space, while at the same time decoding each Xi in constant time. However, in the (realistic) case where the files are correlated, much weaker results are known, requiring at least Ω(n/poly lg n) extra bits for constant decoding time, even for “simple” joint distributions µ. We focus on the natural case of compressing Markov chains, i.e., storing a length-n random walk on any (possibly directed) graph G. Denoting by κ(G, n) the number of length-n walks on G, we show that there is a succinct data structure storing a random walk using lg2 κ(G, n) + O(lg n) bits of space, such that any vertex along the walk can be decoded in O(1) time on a word-RAM. If the graph is strongly connected (e.g., undirected), the space can be improved to only lg2 k(G, n) + 5 extra bits. For the harder task of matching the point-wise optimal space of the walk, i.e., the empirical entropy , we present a data structure with O(1) extra bits at the price of O(lg n) decoding time, and show that any improvement on this would lead to an improved solution on the long-standing Dictionary problem. All of our data structures support the online version of the problem with constant update and query time.

Given an integer array A[1..n], the Range Minimum Query problem (RMQ) asks to preprocess A into a data structure, supporting RMQ queries: given a,b∈ [1,n], return the index i∈[a,b] that minimizes A[i], i.e., argmin i∈[a,b] A[i]. This problem has a classic solution using O(n) space and O(1) query time by Gabow, Bentley, Tarjan (STOC, 1984) and Harel, Tarjan (SICOMP, 1984). The best known data structure by Fischer, Heun (SICOMP, 2011) and Navarro, Sadakane (TALG, 2014) uses 2n+n/(logn/t) t +Õ(n 3/4) bits and answers queries in O(t) time, assuming the word-size is w=Θ(logn). In particular, it uses 2n+n/polylogn bits of space as long as the query time is a constant.

Given a set S of n (distinct) keys from key space [U], each associated with a value from Σ, the static dictionary problem asks to preprocess these (key, value) pairs into a data structure, supporting value-retrieval queries: for any given x∈ [U], valRet(x) must return the value associated with x if x∈ S, or return ⊥ if x∉ S. The special case where |Σ|=1 is called the membership problem. The “textbook” solution is to use a hash table, which occupies linear space and answers each query in constant time. On the other hand, the minimum possible space to encode all (key, value) pairs is only OPT:= ⌈lg2(

This paper proves the first superlogarithmic lower bounds on the cell probe complexity of dynamic Boolean (also known as decision) data structure problems, a long-standing milestone in data structure lower bounds. We introduce a new method for proving dynamic cell probe lower bounds and use it to prove an $\tilde{\Omega}({lg}^{1.5} \ n)$ lower bound on the operational time of a wide range of Boolean data structure problems, most notably, on the query time of dynamic range counting over $\mathbb{F}_2$ [M. Patrascu, Lower bounds for $2$-dimensional range counting, in STOC 2007, ACM, New York, 2007, pp. 40--46]. Proving an $\omega({\rm lg} \ n)$ lower bound for this problem was explicitly posed as one of five important open problems in the late Mihai Pǎtraşcu's obituary [M. Thorup, Bull. Eur. Assoc. Theor. Comput. Sci., 109 (2013), pp. 7--13]. This result also implies the first $\omega({lg} \ n)$ lower bound for the classical 2-dimensional (2D) range counting problem, one of the most fundamental data structure problems in computational geometry and spatial databases. We derive similar lower bounds for Boolean versions of dynamic polynomial evaluation and 2D rectangle stabbing, and for the (non-Boolean) problems of range selection and range median. Our technical centerpiece is a new way of “weakly” simulating dynamic data structures using efficient one-way communication protocols with small advantage over random guessing. This simulation involves a surprising excursion to low-degree (Chebyshev) polynomials which may be of independent interest, and offers an entirely new algorithmic angle on the “cell sampling” method of Panigrahy, Talwar, and Wieder [ Lower bounds on near neighbor search via metric expansion, FOCS 2010, IEEE Computer Society, Los Alamitos, CA, 2010, pp. 805--814].

We show optimal lower bounds for spanning forest computation in two different models: One wants a data structure for fully dynamic spanning forest in which updates can insert or delete edges amongst a base set of n vertices. The sole allowed query asks for a spanning forest, which the data structure should successfully answer with some given (potentially small) constant probability ∊ > 0. We prove that any such data structure must use Ω(n log3 n) bits of memory. There is a referee and n vertices in a network sharing public randomness, and each vertex knows only its neighborhood; the referee receives no input. The vertices each send a message to the referee who then computes a spanning forest of the graph with constant probability ∊ > 0. We prove the average message length must be Ω(log3 n) bits. Both our lower bounds are optimal, with matching upper bounds provided by the AGM sketch [AGM12] (which even succeeds with probability 1 – 1/poly(n)). Furthermore, for the first setting we show optimal lower bounds even for low failure probability δ, as long as δ > 2−n1−∊.

Given an n-bit array A, the succinct rank data structure problem asks to construct a data structure using space n+r bits for r≪ n, supporting rank queries of form rank (u)=∑i=0u−1 A[i]. In this paper, we design a new succinct rank data structure with r=n/(logn)Ω(t)+n1−c and query time O(t) for some constant c>0, improving the previous best-known by Pǎtraşcu, which has r=n/(logn/t)Ω(t)+Õ(n3/4) bits of redundancy. For r>n1−c, our space-time tradeoff matches the cell-probe lower bound by Pǎtraşcu and Viola, which asserts that r must be at least n/(logn)O(t). Moreover, one can avoid an n1−c-bit lookup table when the data structure is implemented in the cell-probe model, achieving r=⌈ n/(logn)Ω(t)⌉. It matches the lower bound for the full range of parameters.

Measuring the distances between vertices on graphs is one of the most fundamental components in network analysis. Since finding shortest paths requires traversing the graph, it is challenging to obtain distance information on large graphs very quickly. In this work, we present a preprocessing algorithm that is able to create landmark based distance sketches efficiently, with strong theoretical guarantees. When evaluated on a diverse set of social and information networks, our algorithm significantly improves over existing approaches by reducing the number of landmarks stored, preprocessing time, or stretch of the estimated distances.

In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players, Bob, his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result each time before the next piece is revealed to Bob. This model has a closer and more natural correspondence to dynamic data structures than classic communication models do, and hence presents a new perspective on data structures.

This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic boolean (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.

Due to the lack of unconditional polynomial lower bounds, it is now in fashion to prove conditional lower bounds in order to advance our understanding of the class P. The vast majority of these lower bounds are based on one of three famous hypotheses: the 3-SUM conjecture, the all pairs shortest paths (APSP) conjecture, and the Strong Exponential Time Hypothesis. Only circumstantial evidence is known in support of these hypotheses, and no formal relationship between them is known. In hopes of obtaining “less conditional" and therefore more reliable lower bounds, we consider the conjecture that at least one of the above three hypotheses is true. We design novel reductions from 3-SUM, APSP, and CNF-SAT, and derive interesting consequences of this very plausible conjecture, including tight $n^{3-o(1)}$ lower bounds for purely combinatorial problems about the triangles in unweighted graphs; new $n^{1-o(1)}$ lower bounds for the amortized update and query times of dynamic algorithms for Single-Source Reachability, Strongly Connected Components, and Max-Flow; new $n^{1.5-o(1)}$ lower bound for computing a set of $n$ $st$-maximum-flow values in a directed graph with $n$ nodes and $\tilde{O}(n)$ edges; and a hierarchy of natural graph problems on $n$ nodes with complexity $n^{c}$ for $c \in (2,3)$. Only slightly nontrivial consequences of this conjecture were known prior to our work. Along the way we also obtain new conditional lower bounds for the Single-Source Max-Flow problem.

We consider the problem of solving systems of multivariate polynomial equations of degree k over a finite field. For every integer k ≤ 2 and finite field q where q = pd for a prime p, we give, to the best of our knowledge, the first algorithms that achieve an exponential speedup over the brute force O(qn) time algorithm in the worst case. We present two algorithms, a randomized algorithm with running time qn+o(n) · q−n/O(k) time if q < 24ekd, and otherwise, where e = 2.718… is Napier's constant, and a deterministic algorithm for counting solutions with running time qn+o(n) · q−n/O(kq6/7d). For the important special case of quadratic equations in F2, our randomized algorithm has running time O(20.8765n). For systems over 2 we also consider the case where the input polynomials do not have bounded degree, but instead can be efficiently represented as a ΣΠΣ circuit, i.e., a sum of products of sums of variables. For this case we present a deterministic algorithm running in time 2n-dn for δ = 1/O(log(s/n)) for instances with s product gates in total and n variables. Our algorithms adapt several techniques recently developed via the polynomial method from circuit complexity. The algorithm for systems of ΣΠΣ polynomials also introduces a new degree reduction method that takes an instance of the problem and outputs a subexponential-sized set of instances, in such a way that feasibility is preserved and every polynomial among the output instances has degree O(log(s/n)).

One of the biggest open problems in external memory data structures is the priority queue problem with DecreaseKey operations. If only Insert and ExtractMin operations need to be supported, one can design a comparison-based priority queue performing O((N/B)lgM/B N) I/Os over a sequence of N operations, where B is the disk block size in number of words and M is the main memory size in number of words. This matches the lower bound for comparison-based sorting and is hence optimal for comparison-based priority queues. However, if we also need to support DecreaseKeys, the performance of the best known priority queue is only O((N/B) lg2 N) I/Os. The big open question is whether a degradation in performance really is necessary. We answer this question affirmatively by proving a lower bound of Ω((N/B) lglgN B) I/Os for processing a sequence of N intermixed Insert, ExtraxtMin and DecreaseKey operations. Our lower bound is proved in the cell probe model and thus holds also for non-comparison-based priority queues.

This paper develops a new technique for proving amortized, randomized cell-probe lower bounds on dynamic data structure problems. We introduce a new randomized nondeterministic four-party communication model that enables "accelerated", error-preserving simulations of dynamic data structures. We use this technique to prove an Ω(n(log n/log log n)2) cell-probe lower bound for the dynamic 2D weighted orthogonal range counting problem (2D-ORC) with n/poly log n updates and n queries, that holds even for data structures with exp(-Ω̃(n)) success probability. This result not only proves the highest amortized lower bound to date, but is also tight in the strongest possible sense, as a matching upper bound can be obtained by a deterministic data structure with worst-case operational time. This is the first demonstration of a "sharp threshold" phenomenon for dynamic data structures. Our broader motivation is that cell-probe lower bounds for exponentially small success facilitate reductions from dynamic to static data structures. As a proof-of-concept, we show that a slightly strengthened version of our lower bound would imply an Ω((log n/log log n)2) lower bound for the static 3D-ORC problem with O(n logO(1) n) space. Such result would give a near quadratic improvement over the highest known static cell-probe lower bound, and break the long standing Ω(log n) barrier for static data structures.

In this paper, we develop a new communication model to prove a data structure lower bound for the dynamic interval union problem. The problem is to maintain a multiset of intervals I over [0, n] with integer coordinates, supporting the following operations: 1) insert(a, b), add an interval [a, b] to I, provided that a and b are integers in [0, n]; 2) delete(a, b), delete an (existing) interval [a, b] from I; 3) query(), return the total length of the union of all intervals in I.

In low-depth circuit complexity, the polynomial method is a way to prove lower bounds by translating weak circuits into low-degree polynomials, then analyzing properties of these polynomials. Recently, this method found an application to algorithm design: Williams (STOC 2014) used it to compute all-pairs shortest paths in time on dense n-node graphs. In this paper, we extend this methodology to solve a number of problems in combinatorial pattern matching and Boolean algebra, considerably faster than previously known methods. First, we give an algorithm for Boolean Orthogonal Detection, which is to detect among two sets A,B ⊆ {0,1}dof size n if there is an x ∊ A and y ∊ B such that 〈x,y〉 = 0. For vectors of dimension d = c(n) log n, we solve Boolean Orthogonal Detection in n2–1/O(log c(n)) time by a Monte Carlo randomized algorithm. We apply this as a subroutine in several other new algorithms: In Batch Partial Match, we are given n query strings from from {0, 1, ⋆}c(n) log n (⋆ is a “don't care”), n strings from {0, 1}c(n)log n, and wish to determine for each query whether or not there is a string matching the query. We solve this problem in n2–1/O(logc(n)) time by a Monte Carlo randomized algorithm. Let t ≤ ν be integers. Given a DNF F on c log t variables with t terms, and v arbitrary assignments on the variables, F can be evaluated on all ν assignments in ν · t1–1/O(log c) time, with high probability. There is a randomized algorithm that solves the Longest Common Substring with don't cares problem on two strings of length n in time. Given two strings S, T of length n, there is a randomized algorithm that computes the length of the longest substring of S that has Edit-Distance less than k to a substring of T in time. Symmetric Boolean Constraint Satisfaction Problems (CSPs) with n variables and m constraints are solvable in poly(m). 2n(1–1/O(log mn)) time.

We present new algorithms for finding induced four-node subgraphs in a given graph, which run in time roughly that of detecting a clique on three nodes (i.e., a triangle). The best known algorithms for triangle finding in an n-node graph take O(nω) time, where ω < 2.373 is the matrix multiplication exponent. We give a general randomized technique for finding any induced four-node subgraph, except for the clique or independent set on 4 nodes, in Õ (nω) time with high probability. The algorithm can be derandomized in some cases: we show how to detect a diamond (or its complement) in deterministic Õ(nω) time. Our approach substantially improves on prior work. For instance, the previous best algorithm for C4 detection ran in O(n3.3) time, and for diamond detection in O(n3) time. For sparse graphs with m edges, the best known triangle finding algorithm runs in O(m2ω/(ω+1)) ≤ O(m1.41) time. We give a randomized Õ(m2ω/(ω+1)) time algorithm (analogous to the best known for triangle finding) for finding any induced four-node subgraph other than C4, K4 and their complements. In the case of diamond detection, we also design a deterministic Õ(m2ω/(ω+1)) time algorithm. For C4 or its complement, we give randomized Õ(m(4ω–1)/(2ω+1)) ≤ O(m1.48) time finding algorithms. These algorithms substantially improve on prior work. For instance, the best algorithm for diamond detection ran in O(m1.5) time.

Due to the lack of unconditional polynomial lower bounds, it is now in fashion to prove conditional lower bounds in order to advance our understanding of the class P. The vast majority of these lower bounds are based on one of three famous hypotheses: the 3-SUM conjecture, the APSP conjecture, and the Strong Exponential Time Hypothesis. Only circumstantial evidence is known in support of these hypotheses, and no formal relationship between them is known. In hopes of obtaining "less conditional" and therefore more reliable lower bounds, we consider the conjecture that at least one of the above three hypotheses is true. We design novel reductions from 3-SUM, APSP, and CNF-SAT, and derive interesting consequences of this very plausible conjecture, including: Tight n3-o(1) lower bounds for purely-combinatorial problems about the triangles in unweighted graphs. New n1-o(1) lower bounds for the amortized update and query times of dynamic algorithms for single-source reachability, strongly connected components, and Max-Flow. New n1.5-o(1) lower bound for computing a set of n st-maximum-flow values in a directed graph with n nodes and ~O(n) edges. There is a hierarchy of natural graph problems on n nodes with complexity nc for c ∈ (2,3).

Hopcroft's problem in d dimensions asks: given n points and n hyperplanes in ℝd, does any point lie on any hyperplane? Equivalently, if we are given two sets of n vectors each in ℝd+1, is there a pair of vectors (one from each set) that are orthogonal? This problem has a long history and a multitude of applications. It is widely believed that for large d, the problem is subject to the curse of dimensionality: all known algorithms need at least f(d) · n2–1/O(d) time for fast-growing functions f, and at the present time there is little hope that a n2 – ∊ • poly(d) time algorithm will be found. We consider Hopcroft's problem over finite fields and integers modulo composites, leading to both surprising algorithms and hardness reductions. The algorithms arise from studying the communication problem of determining whether two lists of vectors (one list held by Alice, one by Bob) contain an orthogonal pair of vectors over a discrete structure (one from each list). We show the randomized communication complexity of the problem is closely related to the sizes of matching vector families, which have been studied in the design of locally decodable codes. Letting HOPCROFTR denote Hopcroft's problem over a ring ℛ, we give randomized algorithms and almost matching lower bounds (modulo a breakthrough in SAT algorithms) for HOPCROFTR, when ℛ is the ring of integers modulo m or a finite field. Building on the ideas developed here, we give a very simple and efficient output-sensitive algorithm for matrix multiplication that works over any field.