ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usTue, 16 Jul 2019 04:19:56 +0300TR19-094 | Rainbow coloring hardness via low sensitivity polymorphisms |
Venkatesan Guruswami,
Sai Sandeep
https://eccc.weizmann.ac.il/report/2019/094 A $k$-uniform hypergraph is said to be $r$-rainbow colorable if there is an $r$-coloring of its vertices such that every hyperedge intersects all $r$ color classes. Given as input such a hypergraph, finding a $r$-rainbow coloring of it is NP-hard for all $k \ge 3$ and $r \ge 2$. Therefore, one settles for finding a rainbow coloring with fewer colors (which is an easier task). When $r=k$ (the maximum possible value), i.e., the hypergraph is $k$-partite, one can efficiently $2$-rainbow color the hypergraph, i.e., $2$-color its vertices so that there are no monochromatic edges. In this work we consider the next smaller value of $r=k-1$, and prove that in this case it is NP-hard to rainbow color the hypergraph with $q := \lceil \frac{k-2}{2} \rceil$ colors. In particular, for $k \le 6$, it is NP-hard to $2$-color $(k-1)$-rainbow colorable $k$-uniform hypergraphs.
Our proof follows the algebraic approach to promise constraint satisfaction problems. It proceeds by characterizing the polymorphisms associated with the approximate rainbow coloring problem, which are rainbow colorings of some product hypergraphs on vertex set $[r]^n$. We prove that any such polymorphism $f: [r]^n \to [q]$ must be $C$-fixing, i.e., there is a small subset $S$ of $C$ coordinates and a setting $a \in [q]^S$ such that fixing $x_{|S} = a$ determines the value of $f(x)$. The key step in our proof is bounding the sensitivity of certain rainbow colorings, thereby arguing that they must be juntas. Armed with the $C$-fixing characterization, our NP-hardness is obtained via a reduction from smooth Label Cover.Tue, 16 Jul 2019 04:19:56 +0300https://eccc.weizmann.ac.il/report/2019/094TR19-093 | Improved 3LIN Hardness via Linear Label Cover |
Euiwoong Lee,
Subhash Khot,
Prahladh Harsha,
Devanathan Thiruvenkatachari
https://eccc.weizmann.ac.il/report/2019/093We prove that for every constant $c$ and $\epsilon = (\log n)^{-c}$, there is no polynomial time algorithm that when given an instance of 3LIN with $n$ variables where an $(1 - \epsilon)$-fraction of the clauses are satisfiable, finds an assignment that satisfies at least $(\frac{1}{2} + \epsilon)$-fraction of clauses unless $\mathbf{NP} \subseteq \mathbf{BPP}$. The previous best hardness using a polynomial time reduction achieves $\epsilon = (\log \log n)^{-c}$, which is obtained by the Label Cover hardness of Moshkovitz and Raz [J. ACM, 57(5), 2010] followed by the reduction from Label Cover to 3LIN of Hastad [J. ACM, 48(4):798--859, 2001].
Our main idea is to prove a hardness result for Label Cover similar to Moshkovitz and Raz where each projection has a linear structure. This linear structure of Label Cover allows us to use Hadamard codes instead of long codes, making the reduction more efficient. For the hardness of Linear Label Cover, we follow the work of Dinur and Harsha [SIAM J. Comput., 42(6):2452--2486, 2013] that simplified the construction of Moshkovitz and Raz, and observe that running their reduction from a hardness of the problem LIN (of unbounded arity) instead of the more standard problem of solving quadratic equations ensures the linearity of the resultant Label Cover.Tue, 16 Jul 2019 04:10:59 +0300https://eccc.weizmann.ac.il/report/2019/093TR19-092 | Revisiting Alphabet Reduction in Dinur's PCP |
Venkatesan Guruswami,
Jakub Opršal,
Sai Sandeep
https://eccc.weizmann.ac.il/report/2019/092Dinur's celebrated proof of the PCP theorem alternates two main steps in several iterations: gap amplification to increase the soundness gap by a large constant factor (at the expense of much larger alphabet size), and a composition step that brings back the alphabet size to an absolute constant (at the expense of a fixed constant factor loss in the soundness gap). We note that the gap amplification can produce a Label Cover CSP. This allows us to reduce the alphabet size via a direct long-code based reduction from Label Cover to a Boolean CSP. Our composition step thus bypasses the concept of Assignment Testers from Dinur's proof, and we believe it is more intuitive --- it is just a gadget reduction. The analysis also uses only elementary facts (Parseval's identity) about Fourier Transforms over the hypercube. Tue, 09 Jul 2019 19:04:11 +0300https://eccc.weizmann.ac.il/report/2019/092TR19-091 | A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs |
Ryo Ashida,
Tatsuya Imai,
Kotaro Nakagawa,
A. Pavan,
Vinodchandran Variyam,
Osamu Watanabe
https://eccc.weizmann.ac.il/report/2019/091In [12] (CCC 2013), the authors presented an algorithm for the reachability problem over directed planar graphs that runs in polynomial-time and uses $O(n^{1/2+\epsilon})$ space. A critical ingredient of their algorithm is a polynomial-time, $\tldO(\sqrt{n})$-space algorithm to compute a separator of a planar graph. The conference version provided a sketch of the algorithm and many nontrivial details were left unexplained. In this work, we provide a detailed construction of their algorithm.Mon, 08 Jul 2019 02:37:15 +0300https://eccc.weizmann.ac.il/report/2019/091TR19-090 | Quasilinear time list-decodable codes for space bounded channels |
Ronen Shaltiel,
Swastik Kopparty,
Jad Silbak
https://eccc.weizmann.ac.il/report/2019/090We consider codes for space bounded channels. This is a model for communication under noise that was studied by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in one pass, and modifies at most a $p$ fraction of the bits of the codeword.
Guruswami and Smith, and later work by Shaltiel and Silbak (RANDOM 2016), gave constructions of list-decodable codes with rate approaching $1-H(p)$ against channels with space $s=c \log n$, with encoding/decoding time $\poly(2^s)=\poly(n^c)$.
In this paper we show that for every constant $0 \le p 0$, there are codes with rate $R \ge 1-H(p)-\epsilon$, list size $\poly(1/\epsilon)$, and furthermore:
\begin{itemize}
\item Our codes can handle channels with space $s=n^{\Omega(1)}$, which is much larger than $O(\log n)$ achieved by previous work.
\item We give encoding and decoding algorithms that run in time $n \cdot \polylog(n)$. Previous work achieved large and unspecified $\poly(n)$ time (even for space $s=1 \cdot \log n$ channels).
\item We can handle space bounded channels that read the codeword in any order, whereas previous work considered channels that read the codeword in the standard order.
\end{itemize}
Our construction builds on the machinery of Guruswami and Smith (with some key modifications) replacing some nonconstructive codes and pseudorandom objects (that are found in exponential time by brute force) with efficient explicit constructions.
For this purpose we exploit recent results of Haramaty, Lee and Viola (SICOMP 2018) on pseudorandom properties of ``$t$-wise independence + low weight noise'' which we quantitatively improve using techniques by Forbes and Kelly (FOCS 2018).
To make use of such distributions, we give new explicit constructions of binary linear codes that have dual distance of $n^{\Omega(1)}$, and are also polynomial time list-decodable from relative distance $\half-\epsilon$, with list size $\poly(1/\epsilon)$. To the best of our knowledge, no such construction was previously known.
Somewhat surprisingly, we show that Reed-Solomon codes with dimension $k<\sqrt{n}$, have this property if interpreted as binary codes (in some specific interpretation) which we term: ``Raw Reed-Solomon Codes''. A key idea is viewing Reed-Solomon codes as ``bundles'' of certain dual-BCH codewords.
Thu, 27 Jun 2019 14:33:00 +0300https://eccc.weizmann.ac.il/report/2019/090TR19-089 | Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits |
Adam Bene Watts,
Robin Kothari,
Luke Schaeffer,
Avishay Tal
https://eccc.weizmann.ac.il/report/2019/089Recently, Bravyi, Gosset, and König (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (or NC^0 circuits). In other words, they exhibited a search problem in QNC^0 that is not in NC^0.
We strengthen their result by proving that the 2D HLF problem is not contained in AC^0, the class of classical, polynomial-size, constant-depth circuits over the gate set of unbounded fan-in AND and OR gates, and NOT gates. We also supplement this worst-case lower bound with an average-case result: There exists a simple distribution under which any AC^0 circuit (even of nearly exponential size) has exponentially small correlation with the 2D HLF problem. Our results are shown by constructing a new problem in QNC^0, which we call the Relaxed Parity Halving Problem, which is easier to work with. We prove our AC^0 lower bounds for this problem, and then show that it reduces to the 2D HLF problem.
As a step towards even stronger lower bounds, we present a search problem that we call the Parity Bending Problem, which is in QNC^0/qpoly (QNC^0 circuits that are allowed to start with a quantum state of their choice that is independent of the input), but is not even in AC^0[2] (the class AC^0 with unbounded fan-in XOR gates).
All the quantum circuits in our paper are simple, and the main difficulty lies in proving the classical lower bounds. For this we employ a host of techniques, including a refinement of H{\aa}stad's switching lemmas for multi-output circuits that may be of independent interest, the Razborov-Smolensky AC^0[2] lower bound, Vazirani's XOR lemma, and lower bounds for non-local games.Sun, 23 Jun 2019 07:09:25 +0300https://eccc.weizmann.ac.il/report/2019/089TR19-088 | On the Complexity of Estimating the Effective Support Size |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2019/088Loosely speaking, the effective support size of a distribution is the size of the support of a distribution that is close to it (in totally variation distance).
We study the complexity of estimating the effective support size of an unknown distribution when given samples of the distributions as well as an evaluation oracle (which returns the probability that the queried element appears in the distribution).
In this context, we present several algorithms that exhibit a trade-off between the quality of the approximation and the complexity of obtaining it, and leave open the question of their optimality.
Sun, 16 Jun 2019 18:33:01 +0300https://eccc.weizmann.ac.il/report/2019/088TR19-087 | Coin Theorems and the Fourier Expansion |
Rohit Agrawal
https://eccc.weizmann.ac.il/report/2019/087In this note we compare two measures of the complexity of a class $\mathcal F$ of Boolean functions studied in (unconditional) pseudorandomness: $\mathcal F$'s ability to distinguish between biased and uniform coins (the coin problem), and the norms of the different levels of the Fourier expansion of functions in $\mathcal F$ (the Fourier growth). We show that for coins with low bias $\varepsilon = o(1/n)$, a function's distinguishing advantage in the coin problem is essentially equivalent to $\varepsilon$ times the sum of its level $1$ Fourier coefficients, which in particular shows that known level $1$ and total influence bounds for some classes of interest (such as constant-width read-once branching programs) in fact follow as a black-box from the corresponding coin theorems, thereby simplifying the proofs of some known results in the literature. For higher levels, it is well-known that Fourier growth bounds on all levels of the Fourier spectrum imply coin theorems, even for large $\varepsilon$, and we discuss here the possibility of a converse.Tue, 11 Jun 2019 17:34:45 +0300https://eccc.weizmann.ac.il/report/2019/087TR19-086 | Perfect zero knowledge for quantum multiprover interactive proofs |
Alex Bredariol Grilo,
William Slofstra,
Henry Yuen
https://eccc.weizmann.ac.il/report/2019/086In this work we consider the interplay between multiprover interactive proofs, quantum
entanglement, and zero knowledge proofs — notions that are central pillars of complexity theory,
quantum information and cryptography. In particular, we study the relationship between the
complexity class MIP$^*$ , the set of languages decidable by multiprover interactive proofs with
quantumly entangled provers, and the class PZK-MIP$^*$ , which is the set of languages decidable
by MIP$^*$ protocols that furthermore possess the perfect zero knowledge property.
Our main result is that the two classes are equal, i.e., MIP$^*$ = PZK-MIP$^*$ . This result provides
a quantum analogue of the celebrated result of Ben-Or, Goldwasser, Kilian, and Wigderson (STOC
1988) who show that MIP = PZK-MIP (in other words, all classical multiprover interactive
protocols can be made zero knowledge). We prove our result by showing that every MIP$^*$
protocol can be efficiently transformed into an equivalent zero knowledge MIP$^*$ protocol in a
manner that preserves the completeness-soundness gap. Combining our transformation with
previous results by Slofstra (Forum of Mathematics, Pi 2019) and Fitzsimons, Ji, Vidick and
Yuen (STOC 2019), we obtain the corollary that all co-recursively enumerable languages (which
include undecidable problems as well as all decidable problems) have zero knowledge MIP$^*$
protocols with vanishing promise gap.Sun, 09 Jun 2019 13:46:57 +0300https://eccc.weizmann.ac.il/report/2019/086TR19-085 | Approximate Degree-Weight and Indistinguishability |
Emanuele Viola,
Xuangui Huang
https://eccc.weizmann.ac.il/report/2019/085We prove that the Or function on $n$ bits can be point-wise approximated with error $\eps$ by a polynomial of degree $O(k)$ and weight $2^{O(n \log (1/\eps)/k)}$, for any $k \geq \sqrt{n \log 1/\eps}$. This result is tight for all $k$. Previous results were either not tight or had $\eps = \Omega(1)$. In general we obtain an approximation result for any symmetric function, also tight. Building on this we also obtain an approximation result for bounded-width CNF. For these two classes no such result was known.
One motivation for such results comes from the study of indistinguishability.
Two distributions $P$, $Q$ over $n$-bit strings are $(k,\delta)$-indistinguishable if their projections on any $k$ bits have statistical distance at most $\delta$.
The above approximations give values of $(k,\delta)$ that suffice to fool symmetric functions and bounded-width CNF, and the first result is tight.
Finally, we show that any two $(k, \delta)$-indistinguishable distributions are $O(n)^{k/2}\delta$-close to two distributions that are $(k,0)$-indistinguishable, improving the previous bound of $O(n)^k \delta$.
Fri, 07 Jun 2019 02:40:41 +0300https://eccc.weizmann.ac.il/report/2019/085