ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usSat, 25 Jan 2020 19:34:54 +0200TR20-007 | Practical Relativistic Zero-Knowledge for NP |
Claude Crépeau,
Arnaud Massenet,
Louis Salvail,
Lucas Stinchcombe,
Nan Yang
https://eccc.weizmann.ac.il/report/2020/007In this work we consider the following problem: in a Multi-Prover environment, how close can we get to prove the validity of an NP statement in Zero-Knowledge ? We exhibit a set of two novel Zero-Knowledge protocols for the 3-COLorability problem that use two (local) provers or three (entangled) provers and only require them to reply two trits each. This greatly improves the ability to prove Zero-Knowledge statements on very short distances with very minimal equipment.
Sat, 25 Jan 2020 19:34:54 +0200https://eccc.weizmann.ac.il/report/2020/007TR20-006 | The Communication Complexity of the Exact Gap-Hamming Problem |
Anup Rao,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2020/006We prove a sharp lower bound on the distributional communication complexity of the exact gap-hamming problem.Wed, 22 Jan 2020 05:47:09 +0200https://eccc.weizmann.ac.il/report/2020/006TR20-005 | Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution |
Olaf Beyersdorff,
Joshua Blinkhorn,
Meena Mahajan
https://eccc.weizmann.ac.il/report/2020/005We provide a tight characterisation of proof size in resolution for quantified Boolean formulas (QBF) by circuit complexity. Such a characterisation was previously obtained for a hierarchy of QBF Frege systems (Beyersdorff & Pich, LICS 2016), but leaving open the most important case of QBF resolution. Different from the Frege case, our characterisation uses a new version of decision lists as its circuit model, which is stronger than the CNFs the system works with. Our decision list model is well suited to compute countermodels for QBFs.
Our characterisation works for both Q-Resolution and QU-Resolution, which we show to be polynomially equivalent for QBFs of bounded quantifier alternation.
Using our characterisation we obtain a size-width relation for QBF resolution in the spirit of the celebrated result for propositional resolution (Ben-Sasson & Wigderson, J. ACM 2001). However, our result is not just a replication of the propositional relation - intriguingly ruled out for QBF in previous research (Beyersdorff et al., ACM ToCL 2018) - but shows a different dependence between size, width, and quantifier complexity.
We demonstrate that our new technique elegantly reproves known QBF hardness results and unifies previous lower-bound techniques in the QBF domain.Sun, 19 Jan 2020 12:37:28 +0200https://eccc.weizmann.ac.il/report/2020/005TR20-004 | The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs |
Joshua Brakensiek,
Venkatesan Guruswami,
Marcin Wrochna,
Stanislav Zivny
https://eccc.weizmann.ac.il/report/2020/004In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not being able to satisfy all the weak constraints. The most commonly cited example of a promise CSP is the approximate graph coloring problem--which has recently seen exciting progress [BKO19, WZ20] benefiting from a systematic algebraic approach to promise CSPs based on "polymorphisms," operations that map tuples in the strict form of each constraint to tuples in the corresponding weak form.
In this work, we present a simple algorithm which in polynomial time solves the decision problem for all promise CSPs that admit infinitely many symmetric polymorphisms, that is the coordinates are permutation invariant. This generalizes previous work of the first two authors [BG19]. We also extend this algorithm to a more general class of block-symmetric polymorphisms. As a corollary, this single algorithm solves all polynomial-time tractable Boolean CSPs simultaneously. These results give a new perspective on Schaefer's classic dichotomy theorem and shed further light on how symmetries of polymorphisms enable algorithms. Finally, we show that block symmetric polymorphisms are not only sufficient but also necessary for this algorithm to work, thus establishing its precise power.
Fri, 17 Jan 2020 04:50:12 +0200https://eccc.weizmann.ac.il/report/2020/004TR20-003 | Tight Static Lower Bounds for Non-Adaptive Data Structures |
Giuseppe Persiano,
Kevin Yeo
https://eccc.weizmann.ac.il/report/2020/003In this paper, we study the static cell probe complexity of non-adaptive data structures that maintain a subset of $n$ points from a universe consisting of $m=n^{1+\Omega(1)}$ points. A data structure is defined to be non-adaptive when the memory locations that are chosen to be accessed during a query depend only on the query inputs and not on the contents of memory. We prove an $\Omega(\log m / \log (sw/n\log m))$ static cell probe complexity lower bound for non-adaptive data structures that solve the fundamental dictionary problem where $s$ denotes the space of the data structure in the number of cells and $w$ is the cell size in bits. Our lower bounds hold for all word sizes including the bit probe model ($w = 1$) and are matched by the upper bounds of Boninger et al. [FSTTCS'17].
Our results imply a sharp dichotomy between dictionary data structures with one round of adaptive and at least two rounds of adaptivity. We show that $O(1)$, or $O(\log^{1-\epsilon}(m))$, overhead dictionary constructions are only achievable with at least two rounds of adaptivity. In particular, we show that many $O(1)$ dictionary constructions with two rounds of adaptivity such as cuckoo hashing are optimal in terms of adaptivity. On the other hand, non-adaptive dictionaries must use significantly more overhead.
Finally, our results also imply static lower bounds for the non-adaptive predecessor problem. Our static lower bounds peak higher than the previous, best known lower bounds of $\Omega(\log m / \log w)$ for the dynamic predecessor problem by Boninger et al. [FSTTCS'17] and Ramamoorthy and Rao [CCC'18] in the natural setting of linear space $s = \Theta(n)$ where each point can fit in a single cell $w = \Theta(\log m)$. Furthermore, our results are stronger as they apply to the static setting unlike the previous lower bounds that only applied in the dynamic setting.Wed, 15 Jan 2020 16:42:20 +0200https://eccc.weizmann.ac.il/report/2020/003TR20-002 | Sensitivity lower bounds from linear dependencies |
Sophie Laplante,
Reza Naserasr,
Anupa Sunny
https://eccc.weizmann.ac.il/report/2020/002Recently, using spectral techniques, H. Huang proved that every subgraph of the hypercube of dimension n induced on more than half the vertices has maximum degree at least the square root of n. Combined with some earlier work, this completed a proof of the sensitivity conjecture. In this work we show how to derive a proof of Huang’s result using only linear dependency and independence of vectors associated with the vertices of the hypercube. Our approach leads to several improvements of the result. In particular we prove that in any induced subgraph of the hypercube with more than half the number of vertices, there are two vertices, one of odd parity and the other of even parity, each with at least n vertices at distance at most 2. As an application we show that for any Boolean function f, the polynomial degree of f is bounded above by the product of the 0- and 1-sensitivities, a strictly stronger statement which implies the sensitivity conjecture.Sun, 12 Jan 2020 07:01:29 +0200https://eccc.weizmann.ac.il/report/2020/002TR20-001 | Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling |
Or Meir,
Susanna de Rezende,
Jakob Nordström,
Robert Robere
https://eccc.weizmann.ac.il/report/2020/001We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph $G$ can be reversibly pebbled in time $t$ and space $s$ if and only if there is a Nullstellensatz refutation of the pebbling formula over $G$ in size $t+1$ and degree $s$ (independently of the field in which the Nullstellensatz refutation is made). We use this correspondence to prove a number of strong size-degree trade-offs for Nullstellensatz, which to the best of our knowledge are the first such results for this proof system.Wed, 01 Jan 2020 09:53:22 +0200https://eccc.weizmann.ac.il/report/2020/001TR19-186 | Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity |
Or Meir,
Susanna de Rezende,
Jakob Nordström,
Robert Robere,
Toniann Pitassi
https://eccc.weizmann.ac.il/report/2019/186We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We apply our generalized theorem to solve two open problems:
* We present the first result that demonstrates a separation in proof power for cutting planes with unbounded versus polynomially bounded coefficients.
Specifically, we exhibit CNF formulas that can be refuted in quadratic length and constant line space in cutting planes with unbounded coefficients, but for which there are no refutations in subexponential length and subpolynomial line space if coefficients are restricted to be of polynomial magnitude.
* We give the first explicit separation between monotone Boolean formulas and monotone real formulas. Specifically, we give an explicit family of functions that can be computed with monotone real formulas of nearly linear size but require monotone Boolean formulas of exponential size. Previously only a non-explicit separation was known.
An important technical ingredient, which may be of independent interest, is that we show that the Nullstellensatz degree of refuting the pebbling formula over a DAG $G$ over any field coincides exactly with the reversible pebbling price of $G$.
In particular, this implies that the standard decision tree complexity and the parity decision tree complexity of the corresponding falsified clause search problem are equal.Tue, 31 Dec 2019 18:41:23 +0200https://eccc.weizmann.ac.il/report/2019/186TR19-185 | Strategy-Stealing is Non-Constructive |
Greg Bodwin,
Ofer Grossman
https://eccc.weizmann.ac.il/report/2019/185In many combinatorial games, one can prove that the first player wins under best play using a simple but non-constructive argument called strategy-stealing.
This work is about the complexity behind these proofs: how hard is it to actually find a winning move in a game, when you know by strategy-stealing that one exists?
We prove that this problem is PSPACE-Complete already for Minimum Poset Games and Symmetric Maker-Maker Games, which are simple classes of games that capture two of the main types of strategy-stealing arguments in the current literature.Sun, 29 Dec 2019 07:25:12 +0200https://eccc.weizmann.ac.il/report/2019/185TR19-184 | Extractors for Adversarial Sources via Extremal Hypergraphs |
Eshan Chattopadhyay,
Jesse Goodman,
Vipul Goyal,
Xin Li
https://eccc.weizmann.ac.il/report/2019/184Randomness extraction is a fundamental problem that has been studied for over three decades. A well-studied setting assumes that one has access to multiple independent weak random sources, each with some entropy. However, this assumption is often unrealistic in practice. In real life, natural sources of randomness can produce samples with no entropy at all or with unwanted dependence. Motivated by this and applications from cryptography, we initiate a systematic study of randomness extraction for the class of adversarial sources defined as follows.
A weak source $\mathbf{X}$ of the form $\mathbf{X}_1,...,\mathbf{X}_N$, where each $\mathbf{X}_i$ is on $n$ bits, is an $(N,K,n,k)$-source of locality $d$ if the following hold:
(1) Somewhere good sources: at least $K$ of the $\mathbf{X}_i$'s are independent, and each contains min-entropy at least $k$. We call these $\mathbf{X}_i$'s good sources, and their locations are unknown. (2) Bounded dependence: each remaining (bad) source can depend arbitrarily on at most $d$ good sources.
We focus on constructing extractors with negligible error, in the regime where most of the entropy is contained within a few sources instead of across many (i.e., $k$ is at least polynomial in $K$). In this setting, even for the case of $0$-locality, very little is known prior to our work. For $d \geq 1$, essentially no previous results are known. We present various new extractors for adversarial sources in a wide range of parameters, and some of our constructions work for locality $d = K^{\Omega(1)}$. As an application, we also give improved extractors for small-space sources.
The class of adversarial sources generalizes several previously studied classes of sources, and our explicit extractor constructions exploit tools from recent advances in extractor machinery, such as two-source non-malleable extractors and low-error condensers. Thus, our constructions can be viewed as a new application of non-malleable extractors. In addition, our constructions combine the tools from extractor theory in a novel way through various sorts of explicit extremal hypergraphs. These connections leverage recent progress in combinatorics, such as improved bounds on cap sets and explicit constructions of Ramsey graphs, and may be of independent interest.
Sun, 22 Dec 2019 09:10:31 +0200https://eccc.weizmann.ac.il/report/2019/184