ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usSat, 25 May 2019 21:06:09 +0300TR19-075 | Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems |
Lijie Chen,
Dylan McKay,
Cody Murray,
Ryan Williams
https://eccc.weizmann.ac.il/report/2019/075Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems
A frontier open problem in circuit complexity is to prove P^NP is not in SIZE[n^k] for all k; this is a necessary intermediate step towards NP is not in P/poly. Previously, for several classes containing P^NP, including NP^NP, ZPP^NP, and S_2 P, such lower bounds have been proved via Karp-Lipton-style Theorems: to prove C is not in SIZE[n^k] for all k, we show that C subset Ppoly implies a ``collapse'' D = C for some larger class D, where we already know D is not in SIZE[n^k] for all k.
It seems obvious that one could take a different approach to prove circuit lower bounds for P^NP that does not require proving any Karp-Lipton-style theorems along the way. We show this intuition is wrong: (weak) Karp-Lipton-style theorems for P^NP are equivalent to fixed-polynomial size circuit lower bounds for P^NP. That is, P^NP not subset SIZE[n^k] for all k if and only if (NP is in P/poly implies PH is in i.o.-P^NP/n).
Next, we present new consequences of the assumption NP is in P/poly, towards proving similar results for NP circuit lower bounds. We show that under the assumption, fixed-polynomial circuit lower bounds for NP, nondeterministic polynomial-time derandomizations, and various fixed-polynomial time simulations of NP are all equivalent. Applying this equivalence, we show that circuit lower bounds for NP imply better Karp-Lipton collapses. That is, if NP is not in SIZE[n^k] for all k, then for all C in { ParP, PP, PSPACE, EXP }, C is in P/poly implies C is in i.o.-NP/n^eps for all eps > 0. Note that unconditionally, the collapses are only to MA and not NP.
We also explore consequences of circuit lower bounds for a sparse language in NP. Among other results, we show if a polynomially-sparse NP language does not have n^(1+eps)-size circuits, then MA is in i.o.-NP/O(log n), MA is in i.o.-P^{NP[O(log n)]}, and NEXP is not in SIZE[2^o(m)]. Finally, we observe connections between these results and the ``hardness magnification'' phenomena described in recent works.Sat, 25 May 2019 21:06:09 +0300https://eccc.weizmann.ac.il/report/2019/075TR19-074 | Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir |
Chethan Kamath,
Arka Rai Choudhuri,
Pavel Hubacek,
Krzysztof Pietrzak,
Alon Rosen,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2019/074 The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocolâ€™s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.
We show that solving the End-of-Metered-Line problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD.
Our main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n).
Combining our construction with a hash family proposed by Canetti et al. [STOC 2019] gives rise to a distribution in the class CLS, which is provably hard under the assumption that any one of a class of fully homomorphic encryption (FHE) schemes has almost-optimal security against quasi-polynomial time adversaries, and under the additional worst-case assumption that there is no polynomial time algorithm for counting the number of satisfying assignments for formulas over a polylogarithmic number of variables. Wed, 22 May 2019 21:28:29 +0300https://eccc.weizmann.ac.il/report/2019/074TR19-073 | Parity helps to compute Majority |
Igor Carboni Oliveira,
Rahul Santhanam,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2019/073We study the complexity of computing symmetric and threshold functions by constant-depth circuits with Parity gates, also known as AC$^0[\oplus]$ circuits. Razborov (1987) and Smolensky (1987, 1993) showed that Majority requires depth-$d$ AC$^0[\oplus]$ circuits of size $2^{\Omega(n^{1/2(d-1)})}$. By using a divide-and-conquer approach, it is easy to show that Majority can be computed with depth-$d$ AC$^0[\oplus]$ circuits of size $2^{\widetilde{O}(n^{1/(d-1)})}$. This gap between upper and lower bounds has stood for nearly three decades.
Somewhat surprisingly, we show that neither the upper bound nor the lower bound above is tight for large $d$. We show for $d \geq 5$ that any symmetric function can be computed with depth-$d$ AC$^0[\oplus]$ circuits of size $\exp({\widetilde{O} (n^{\frac{2}{3} \cdot \frac{1}{(d - 4)}} )})$. Our upper bound extends to threshold functions (with a constant additive loss in the denominator of the double exponent). We improve the Razborov-Smolensky lower bound to show that for $d \geq 3$ Majority requires depth-$d$ AC$^0[\oplus]$ circuits of size $2^{\Omega(n^{1/(2d-4)})}$. For depths $d \leq 4$, we are able to refine our techniques to get almost-optimal bounds: the depth-$3$ AC$^0[\oplus]$ circuit size of Majority is $2^{\widetilde{\Theta}(n^{1/2})}$, while its depth-$4$ AC$^0[\oplus]$ circuit size is $2^{\widetilde{\Theta}(n^{1/4})}$.Sat, 18 May 2019 00:48:44 +0300https://eccc.weizmann.ac.il/report/2019/073TR19-072 | Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators |
Lijie Chen,
Ofer Grossman
https://eccc.weizmann.ac.il/report/2019/072Consider the multiparty communication complexity model where there are n processors, each receiving as input a row of an n by n matrix M with entries in {0, 1}, and in each round each party can broadcast a single bit to all other parties (this is known as the BCAST(1) model). There are many lower bounds known for the number of rounds necessary for certain problems in this model, but they are all worst case lower bounds which apply only for very specifically constructed input distributions. We develop a framework for showing lower bounds in this setting for more natural input distributions, and apply the framework to show:
A lower bound for finding planted cliques in random inputs (i.e., each entry of the matrix is random, except there is a random subset a_1,..., a_k in [n] where M_{a_i,a_j} = 1 for all i and j). Specifically, we show that if k = n^(1/4 - eps), this problem requires a number of rounds polynomial in n.
A pseudo-random generator which fools the BCAST(1) model. That is, we show a distribution which is efficiently samplable using few random bits, and which is indistinguishable from uniform by a low-round BCAST(1) protocol. This allows us to show that every t = Omega(log n) round randomized algorithm in which each processor uses up to n random bits can be efficiently transformed into an O(t)-round randomized algorithm in which each processor uses only up to O(t) random bits, while maintaining a high success probability.
As a corollary of the pseudo-random generator, we also prove the first average case lower bound for the model (specifically, for the problem of determining whether the input matrix is full rank), as well as an average-case time hierarchy. Fri, 17 May 2019 22:38:02 +0300https://eccc.weizmann.ac.il/report/2019/072TR19-071 | Time-Space Lower Bounds for Two-Pass Learning |
Sumegha Garg,
Ran Raz,
Avishay Tal
https://eccc.weizmann.ac.il/report/2019/071A line of recent works showed that for a large class of learning problems, any learning algorithm requires either super-linear memory size or a super-polynomial number of samples [Raz16,KRT17,Raz17,MM18,BOGY18,GRT18]. For example, any algorithm for learning parities of size $n$ requires either a memory of size $\Omega(n^{2})$ or an exponential number of samples [Raz16].
All these works modeled the learner as a one-pass branching program, allowing only one pass over the stream of samples. In this work, we prove the first memory-samples lower bounds (with a super-linear lower bound on the memory size and super-polynomial lower bound on the number of samples) when the learner is allowed two passes over the stream of samples. For example, we prove that any two-pass algorithm for learning parities of size $n$ requires either a memory of size $\Omega(n^{1.5})$ or at least $2^{\Omega(\sqrt{n})}$ samples.
More generally, a matrix $M: A \times X \rightarrow \{-1,1\}$ corresponds to the following learning problem: An unknown element $x \in X$ is chosen uniformly at random. A learner tries to learn $x$ from a stream of samples, $(a_1, b_1), (a_2, b_2) \ldots$, where for every $i$, $a_i \in A$ is chosen uniformly at random and $b_i = M(a_i,x)$.
Assume that $k,l, r$ are such that any submatrix of $M$ of at least $2^{-k} \cdot |A|$ rows and at least $2^{-l} \cdot |X|$ columns, has a bias of at most $2^{-r}$. We show that any two-pass learning algorithm for the learning problem corresponding to $M$ requires either a memory of size at least $\Omega\left(k \cdot \min\{k,\sqrt{l}\} \right)$, or at least $2^{\Omega(\min\{k,\sqrt{l},r\})}$ samples.
Tue, 14 May 2019 19:35:18 +0300https://eccc.weizmann.ac.il/report/2019/071TR19-070 | On Local Testability in the Non-Signaling Setting |
Alessandro Chiesa,
Peter Manohar,
Igor Shinkar
https://eccc.weizmann.ac.il/report/2019/070Non-signaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of local-to-global phenomena for non-signaling functions.
We present general results about the local testability of linear codes in the non-signaling setting. Our contributions include formulating natural definitions that capture the condition that a non-signaling function "belongs" to a given code, and characterizing the sets of local constraints that imply membership in the code. We prove these results by relating the Fourier spectrum of non-signaling functions to Cayley hypergraphs induced by local constraints.
We apply the above results to show a separation between locally testable codes in the classical and non-signaling setting by proving that bivariate low-degree testing fails spectacularly in the non-signaling setting. Specifically, we show that there exist non-signaling functions that pass bivariate low-degree tests with probability 1, and yet are maximally far from low-degree.Tue, 14 May 2019 08:26:11 +0300https://eccc.weizmann.ac.il/report/2019/070TR19-069 | Bounded-depth Frege complexity of Tseitin formulas for all graphs |
Artur Riazanov,
Dmitry Itsykson,
Nicola Galesi,
Anastasia Sofronova
https://eccc.weizmann.ac.il/report/2019/069We prove that there is a constant $K$ such that \emph{Tseitin} formulas for an undirected graph $G$ requires proofs of
size $2^{\mathrm{tw}(G)^{\Omega(1/d)}}$ in depth-$d$ Frege systems for $d<\frac{K \log n}{\log \log n}$, where $\tw(G)$ is the treewidth of $G$. This extends H{\aa}stad recent lower bound for the grid graph to any graph. Furthermore, we prove tightness of our bound up to a multiplicative constant in the top exponent.
Namely, we show that if a Tseitin formula for a graph $G$ has size $s$, then for all large enough $d$, it has a depth-$d$ Frege proof of size $2^{\mathrm{tw}(G)^{\O(1/d)}} \mathrm{poly}(s)$.
Through this result we settle the question posed by M. Alekhnovich and A. Razborov of showing that the class of Tseitin formulas is quasi-automatizable for resolution.Sun, 12 May 2019 12:21:17 +0300https://eccc.weizmann.ac.il/report/2019/069TR19-068 | LARGE CLIQUE IS HARD ON AVERAGE FOR RESOLUTION |
Shuo Pang
https://eccc.weizmann.ac.il/report/2019/068We prove resolution lower bounds for $k$-Clique on the Erdos-Renyi random graph $G(n,n^{-{2\xi}\over{k-1}})$ (where $\xi>1$ is constant). First we show for $k=n^{c_0}$, $c_0\in(0,1/3)$, an $\exp({\Omega(n^{(1-\epsilon)c_0})})$ average lower bound on resolution where $\epsilon$ is arbitrary constant.
We then propose the model of $a$-irregular resolution. Extended from regular resolution, this model is interesting in that the power of general-over-regular resolution from all {\it known} exponential separations is below it. We prove an $n^{\Omega(k)}$ average lower bound of $k$-Clique for this model, for {\it any} $k<n^{1/3-\Omega(1)}$.Thu, 09 May 2019 19:39:36 +0300https://eccc.weizmann.ac.il/report/2019/068TR19-067 | Sign rank vs Discrepancy |
Hamed Hatami,
Kaave Hosseini,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2019/067Sign-rank and discrepancy are two central notions in communication complexity. The seminal work of Babai, Frankl, and Simon from 1986 initiated an active line of research that investigates the gap between these two notions.
In this article, we establish the strongest possible separation by constructing a Boolean matrix whose sign-rank is only $3$, and yet its discrepancy is $2^{-\Omega(n)}$. We note that every matrix of sign-rank $2$ has discrepancy $n^{-O(1)}$.
Our result in particular implies that there are Boolean functions with $O(1)$ unbounded error randomized communication complexity while having $\Omega(n)$ weakly unbounded error randomized communication complexity.
Tue, 07 May 2019 12:52:08 +0300https://eccc.weizmann.ac.il/report/2019/067TR19-066 | A Lower Bound for Sampling Disjoint Sets |
Thomas Watson
https://eccc.weizmann.ac.il/report/2019/066Suppose Alice and Bob each start with private randomness and no other input, and they wish to engage in a protocol in which Alice ends up with a set $x\subseteq[n]$ and Bob ends up with a set $y\subseteq[n]$, such that $(x,y)$ is uniformly distributed over all pairs of disjoint sets. We prove that for some constant $\varepsilon>0$, this requires $\Omega(n)$ communication even to get within statistical distance $\varepsilon$ of the target distribution. Previously, Ambainis, Schulman, Ta-Shma, Vazirani, and Wigderson (FOCS 1998) proved that $\Omega(\sqrt{n})$ communication is required to get within $\varepsilon$ of the uniform distribution over all pairs of disjoint sets of size $\sqrt{n}$.Fri, 03 May 2019 03:14:32 +0300https://eccc.weizmann.ac.il/report/2019/066