Huacheng Yu

STOC Conference 2025 Conference Paper

Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness

• Elena Gribelyuk
• Honghao Lin
• David P. Woodruff
• Huacheng Yu
• Samson Zhou

We introduce a novel technique for “lifting” dimension lower bounds for linear sketches in the real-valued setting to dimension lower bounds for linear sketches with polynomially-bounded integer entries when the input is a polynomially-bounded integer vector. Using this technique, we obtain the first optimal sketching lower bounds for discrete inputs in a data stream, for classical problems such as approximating the frequency moments, estimating the operator norm, and compressed sensing. Additionally, we lift the adaptive attack of Hardt and Woodruff (STOC, 2013) for breaking any real-valued linear sketch via a sequence of real-valued queries, and show how to obtain an attack on any integer-valued linear sketch using integer-valued queries. This shows that there is no linear sketch in a data stream with insertions and deletions that is adversarially robust for approximating any L p norm of the input, resolving a central open question for adversarially robust streaming algorithms. To do so, we introduce a new pre-processing technique of independent interest which, given an integer-valued linear sketch, increases the dimension of the sketch by only a constant factor in order to make the orthogonal lattice to its row span smooth. This pre-processing then enables us to leverage results in lattice theory on discrete Gaussian distributions and reason that efficient discrete sketches imply efficient continuous sketches. Our work resolves open questions from the Banff ’14 and ’17 workshops on Communication Complexity and Applications, as well as the STOC ’21 and FOCS ’23 workshops on adaptivity and robustness.

SODA Conference 2025 Conference Paper

Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors

• Elena Gribelyuk
• Pachara Sawettamalya
• Hongxun Wu
• Huacheng Yu

STOC Conference 2025 Conference Paper

Optimal Static Dictionary with Worst-Case Constant Query Time

• Yang Hu
• Jingxun Liang
• Huacheng Yu
• Junkai Zhang
• Renfei Zhou

In this paper, we design a new succinct static dictionary with worst-case constant query time. A dictionary data structure stores a set of key-value pairs with distinct keys in [ U ] and values in [σ], such that given a query x ∈ [ U ], it quickly returns if x is one of the input keys, and if so, also returns its associated value. The textbook solution to dictionaries is hash tables. On the other hand, the (information-theoretical) optimal space to encode such a set of key-value pairs is only OPT := log( U n ) + n logσ. We construct a dictionary that uses OPT + n ε bits of space, and answers queries in constant time in worst case . Previously, constant-time dictionaries are only known with OPT + n / poly log n space, or with OPT + n ε space but expected constant query time. We emphasize that most of the extra n ε bits are used to store a lookup table that does not depend on the input, and random bits for hash functions. The “main” data structure only occupies OPT + poly log n bits.

FOCS Conference 2025 Conference Paper

Static Retrieval Revisited: To Optimality and Beyond

• Yang Hu
• William Kuszmaul
• Jingxun Liang
• Huacheng Yu
• Junkai Zhang
• Renfei Zhou

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.

STOC Conference 2025 Conference Paper

Strong XOR Lemma for Information Complexity

• Pachara Sawettamalya
• Huacheng Yu

For any {0,1}-valued function f , its n -folded XOR is the function f ⊕ n where f ⊕ n ( X 1 , …, X n ) = f ( X 1 ) ⊕ ⋯ ⊕ f ( X n ). Given a procedure for computing the function f , one can apply a “naive” approach to compute f ⊕ n by computing each f ( X i ) independently, followed by XORing the outputs. This approach uses n times the resources required for computing f . In this paper, we prove a strong XOR lemma for information complexity in the two-player randomized communication model: if computing f with an error probability of O ( n −1 ) requires revealing I bits of information about the players’ inputs, then computing f ⊕ n with a constant error requires revealing Ω( n ) · ( I − 1 − o n (1)) bits of information about the players’ inputs. Our result demonstrates that the naive protocol for computing f ⊕ n is both information-theoretically optimal and asymptotically tight in error trade-offs.

FOCS Conference 2024 Conference Paper

A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches

• Elena Gribelyuk
• Honghao Lin
• David P. Woodruff
• Huacheng Yu
• Samson Zhou

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.

SODA Conference 2024 Conference Paper

Dynamic Dictionary with Subconstant Wasted Bits per Key

• Tianxiao Li
• Jingxun Liang
• Huacheng Yu
• Renfei Zhou

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]. In this paper, we study the regime where the number of redundant bits is R = o ( n ), and show that when R is at least n /poly log n, all operations can be supported in O (log* n + log( n / R )) time, matching the lower bound in this regime [16]. We present two data structures based on which range R is in. The data structure for R < n /log 0. 1 n utilizes a generalization of adapters studied in [5, 15]. The data structure for R ≥ n /log 0. 1 n is based on recursively hashing into buckets with logarithmic sizes.

FOCS Conference 2023 Conference Paper

Dynamic "Succincter"

• Tianxiao Li
• Jingxun Liang
• Huacheng Yu
• Renfei Zhou

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.

FOCS Conference 2023 Conference Paper

Super-Logarithmic Lower Bounds for Dynamic Graph Problems

• Kasper Green Larsen
• Huacheng Yu

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.

FOCS Conference 2023 Conference Paper

Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries

• Tianxiao Li
• Jingxun Liang
• Huacheng Yu
• Renfei Zhou

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.

SODA Conference 2023 Conference Paper

Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut

• Lijie Chen 0001
• Gillat Kol
• Dmitry Paramonov
• Raghuvansh R. Saxena
• Zhao Song 0002
• Huacheng Yu

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.

FOCS Conference 2022 Conference Paper

Strong XOR Lemma for Communication with Bounded Rounds: (extended abstract)

• Huacheng Yu

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.

STOC Conference 2021 Conference Paper

Almost optimal super-constant-pass streaming lower bounds for reachability

• Lijie Chen 0001
• Gillat Kol
• Dmitry Paramonov
• Raghuvansh R. Saxena
• Zhao Song 0002
• Huacheng Yu

We give an almost quadratic n 2− o (1) lower bound on the space consumption of any o (√log n )-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. Our main technical contribution is the definition and construction of set hiding graphs, that may be of independent interest: we give a general way of encoding a set S ⊆ [ k ] as a directed graph with n = k 1 + o ( 1 ) vertices, such that deciding whether i ∈ S boils down to deciding if t i is reachable from s i , for a specific pair of vertices ( s i , t i ) in the graph. Furthermore, we prove that our graph “hides” S , in the sense that no low-space streaming algorithm with a small number of passes can learn (almost) anything about S .

SODA Conference 2021 Conference Paper

Tight Distributed Sketching Lower Bound for Connectivity

• Huacheng Yu

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 Ω(log 3 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 Ω(log 3 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.

SODA Conference 2020 Conference Paper

Faster Update Time for Turnstile Streaming Algorithms

• Josh Alman
• Huacheng Yu

SODA Conference 2020 Conference Paper

How to Store a Random Walk

• Emanuele Viola
• Omri Weinstein
• Huacheng Yu

Motivated by storage applications, we study the following data structure problem: an encoder wishes to store a collection of jointly-distributed files: = ( X 1, X 2, …, X n ) ∼ µ which are correlated ( H µ ( ) ≤ Σ i H µ ( X i )), using as little (expected) memory as possible, such that each individual file X i 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 X i 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 lg 2 κ ( 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 lg 2 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.

STOC Conference 2020 Conference Paper

Lower bound for succinct range minimum query

• Mingmou Liu
• Huacheng Yu

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 2 n + n /(log n / t ) t +Õ( n 3/4 ) bits and answers queries in O ( t ) time, assuming the word-size is w =Θ(log n ). In particular, it uses 2 n + n / poly log n bits of space as long as the query time is a constant. In this paper, we prove the first lower bound for this problem, showing that 2 n + n / poly log n space is necessary for constant query time. In general, we show that if the data structure has query time O ( t ), then it must use at least 2 n + n /(log n ) Õ( t 2 ) space, in the cell-probe model with word-size w =Θ(log n ).

FOCS Conference 2020 Conference Paper

Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems

• Sepehr Assadi
• Gillat Kol
• Raghuvansh R. Saxena
• Huacheng Yu

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 n 1-Ω(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 n 1-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.

STOC Conference 2020 Conference Paper

Nearly optimal static Las Vegas succinct dictionary

• Huacheng Yu

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 := ⌈lg 2 ( U n )+ n lg 2 |Σ|⌉ bits, which could be much less. In this paper, we design a randomized dictionary data structure using OPT +lg n + O (lglglglglg U ) bits of space, and it has expected constant query time, assuming the query algorithm can access an external lookup table of size n 0.001 . The lookup table depends only on U , n and |Σ|, and not the input. Previously, even for membership queries and U ≤ n O (1) , the best known data structure with constant query time requires OPT + n /lg n bits of space by Pagh (SIAM J. Comput. 2001) and Pǎtraşcu (FOCS 2008); the best known using OPT + n 0.999 space has query time O (lg n ); the only known non-trivial data structure with OPT + n 0.001 space has O (lg n ) query time and requires a lookup table of size ≥ n 2.99 (!). Our new data structure answers open questions by Pǎtraşcu and Thorup.

SODA Conference 2019 Conference Paper

Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation

• Jelani Nelson
• Huacheng Yu

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 log 3 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 Ω(log 3 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 − n 1−∊.

STOC Conference 2019 Conference Paper

Optimal succinct rank data structure via approximate nonnegative tensor decomposition

• Huacheng Yu

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 =0 u −1 A [ i ]. In this paper, we design a new succinct rank data structure with r = n /(log n ) Ω( t ) + n 1− c and query time O ( t ) for some constant c >0, improving the previous best-known by Pǎtraşcu, which has r = n /(log n / t ) Ω( t ) +Õ( n 3/4 ) bits of redundancy. For r > n 1− 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 /(log n ) O ( t ) . Moreover, one can avoid an n 1− c -bit lookup table when the data structure is implemented in the cell-probe model, achieving r =⌈ n /(log n ) Ω( t ) ⌉. It matches the lower bound for the full range of parameters. En route to our new data structure design, we establish an interesting connection between succinct data structures and approximate nonnegative tensor decomposition. Our connection shows that for specific problems, to construct a space-efficient data structure, it suffices to approximate a particular tensor by a sum of (few) nonnegative rank-1 tensors. For the rank problem, we explicitly construct such an approximation, which yields an explicit construction of the data structure.

I&C Journal 2018 Journal Article

An improved combinatorial algorithm for Boolean matrix multiplication

• Huacheng Yu

We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in O ˆ ( n 3 / log 4 ⁡ n ) time, where the O ˆ notation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan that runs in O ˆ ( n 3 / log 3 ⁡ n ) time. Our algorithm generalizes the divide-and-conquer strategy of Chan's algorithm. Moreover, we propose a general framework for detecting triangles in graphs and computing Boolean matrix multiplication. Roughly speaking, if we can find the “easy parts” of a given instance efficiently, we can solve the whole problem faster than n 3.

STOC Conference 2018 Conference Paper

Cell-probe lower bounds from online communication complexity

• Josh Alman
• Joshua R. Wang
• Huacheng Yu

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. We first present a tight lower bound for the online set intersection problem in the online communication model, demonstrating a general approach for proving online communication lower bounds. The online communication model prevents a batching trick that classic communication complexity allows, and yields a stronger lower bound. We then apply the online communication model to prove data structure lower bounds for two dynamic data structure problems: the Group Range problem and the Dynamic Connectivity problem for forests. Both of the problems admit a worst case O (log n )-time data structure. Using online communication complexity, we prove a tight cell-probe lower bound for each: spending o (log n ) (even amortized) time per operation results in at best an exp(−δ 2 n ) probability of correctly answering a (1/2+δ)-fraction of the n queries.

STOC Conference 2018 Conference Paper

Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds

• Kasper Green Larsen
• Omri Weinstein
• Huacheng Yu

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.

SODA Conference 2017 Conference Paper

Beating Brute Force for Systems of Polynomial Equations over Finite Fields

• Daniel Lokshtanov
• Ramamohan Paturi
• Suguru Tamaki
• R. Ryan Williams
• Huacheng Yu

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 = p d 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 ( q n ) time algorithm in the worst case. We present two algorithms, a randomized algorithm with running time q n + o ( n ) · q − n / O ( k ) time if q < 2 4 ekd, and otherwise, where e = 2. 718… is Napier's constant, and a deterministic algorithm for counting solutions with running time q n + o ( n ) · q − n / O ( kq 6/7 d ). For the important special case of quadratic equations in F 2, our randomized algorithm has running time O (2 0. 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 2 n-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 )).

STOC Conference 2017 Conference Paper

DecreaseKeys are expensive for external memory priority queues

• Kasper Eenberg
• Kasper Green Larsen
• Huacheng Yu

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 )lg M / 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 ) lg 2 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 ) lg lg N 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.

FOCS Conference 2016 Conference Paper

Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication

• Omri Weinstein
• Huacheng Yu

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.

STOC Conference 2016 Conference Paper

Cell-probe lower bounds for dynamic problems via a new communication model

• Huacheng Yu

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 . It is related to the two-dimensional case of Klee’s measure problem. We prove that there is a distribution over sequences of operations with O ( n ) insertions and deletions, and O ( n 0.01 ) queries, for which any data structure with any constant error probability requires Ω( n log n ) time in expectation. Interestingly, we use the sparse set disjointness protocol of Håstad and Wigderson to speed up a reduction from a new kind of nondeterministic communication games, for which we prove lower bounds. For applications, we prove lower bounds for several dynamic graph problems by reducing them from dynamic interval union.

SODA Conference 2015 Conference Paper

Finding Four-Node Subgraphs in Triangle Time

• Virginia Vassilevska Williams
• Joshua R. Wang
• R. Ryan Williams
• Huacheng Yu

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 C 4 detection ran in O ( n 3. 3 ) time, and for diamond detection in O ( n 3 ) time. For sparse graphs with m edges, the best known triangle finding algorithm runs in O ( m 2 ω / ( ω +1) ) ≤ O ( m 1. 41 ) time. We give a randomized Õ ( m 2 ω /( ω +1) ) time algorithm (analogous to the best known for triangle finding) for finding any induced four-node subgraph other than C 4, K 4 and their complements. In the case of diamond detection, we also design a deterministic Õ ( m 2 ω /( ω +1) ) time algorithm. For C 4 or its complement, we give randomized Õ ( m (4 ω– 1)/(2 ω +1) ) ≤ O ( m 1. 48 ) time finding algorithms. These algorithms substantially improve on prior work. For instance, the best algorithm for diamond detection ran in O ( m 1. 5 ) time.

STOC Conference 2015 Conference Paper

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture

• Amir Abboud
• Virginia Vassilevska Williams
• Huacheng Yu

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 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 ~O(n) edges. There is a hierarchy of natural graph problems on n nodes with complexity n c for c ∈ (2,3). Only slightly non-trivial 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.

SODA Conference 2015 Conference Paper

More Applications of the Polynomial Method to Algorithm Design

• Amir Abboud
• R. Ryan Williams
• Huacheng Yu

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 B oolean O rthogonal D etection, which is to detect among two sets A, B ⊆ {0, 1} d of 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 B oolean O rthogonal D etection in n 2–1/ O (log c ( n )) time by a Monte Carlo randomized algorithm. We apply this as a subroutine in several other new algorithms: In B atch P artial M atch, 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 n 2–1 / O (log c ( 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 ν · t 1–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 ). 2 n (1–1/ O (log mn )) time.

SODA Conference 2014 Conference Paper

Finding orthogonal vectors in discrete structures

• R. Ryan Williams
• Huacheng Yu