Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > HUACHENG YU:
All reports by Author Huacheng Yu:

TR22-166 | 23rd November 2022
Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu

Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly

We study boolean constraint satisfaction problems (CSPs) $\mathrm{Max}\text{-}\mathrm{CSP}^f_n$ for all predicates $f: \{ 0, 1 \} ^k \to \{ 0, 1 \}$. In these problems, given an integer $v$ and a list of constraints over $n$ boolean variables, each obtained by applying $f$ to a sequence of literals, we wish ... more >>>


TR22-161 | 9th November 2022
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu

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

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, ... more >>>


TR22-118 | 23rd August 2022
Huacheng Yu

Strong XOR Lemma for Communication with Bounded Rounds

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 ... more >>>


TR21-027 | 24th February 2021
Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu

Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability

We give an almost quadratic $n^{2-o(1)}$ lower bound on the space consumption of any $o(\sqrt{\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 ... more >>>


TR18-129 | 13th July 2018
Jelani Nelson, Huacheng Yu

Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation

Revisions: 1

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 ... more >>>


TR17-066 | 20th April 2017
Josh Alman, Joshua Wang, Huacheng Yu

Cell-Probe Lower Bounds from Online Communication Complexity

Revisions: 1

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 it presents Bob with the next piece. ... more >>>


TR17-047 | 10th March 2017
Kasper Green Larsen, Omri Weinstein, Huacheng Yu

Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic \emph{boolean} (a.k.a. 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 a $\tilde{\Omega}(\log^{1.5} ... more >>>


TR16-054 | 11th April 2016
Omri Weinstein, Huacheng Yu

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

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 $\Omega(n\left(\log n/\log\log n\right)^2)$ cell-probe ... more >>>




ISSN 1433-8092 | Imprint