Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR22-168 | 23rd November 2022
Zubayir Kazi

A Proof of the Generalized Union-Closed Set Conjecture assuming the Union-Closed Set Conjecture

Revisions: 2

Abstract The Union Closed Set Conjecture states that if a set system X\subseteq\mathcal{P}([n]) is closed under pairwise unions, then there exists a\in[n] in at least half of the sets of X. We show that there is a very natural generalization of the union closed set conjecture which gives a lower ... more >>>


TR22-167 | 23rd November 2022
Mark Braverman, Subhash Khot, Dor Minzer

Parallel Repetition for the GHZ Game: Exponential Decay

We show that the value of the $n$-fold repeated GHZ game is at most $2^{-\Omega(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics.

more >>>

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



previous PreviousNext next


ISSN 1433-8092 | Imprint