ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usFri, 11 Oct 2019 01:51:47 +0300- TR19-140 | Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings. |
Rafael Mendes de Oliveira,
Ankit Garg,
Visu Makam,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2019/140We consider the problem of outputting succinct encodings of lists of generators for invariant rings. Mulmuley conjectured that there are always polynomial sized such encodings for all invariant rings. We provide simple examples that disprove this conjecture (under standard complexity assumptions).Fri, 11 Oct 2019 01:51:47 +0300https://eccc.weizmann.ac.il/report/2019/140
- TR19-139 | Direct sum testing - the general case |
Irit Dinur,
Konstantin Golubev
https://eccc.weizmann.ac.il/report/2019/139
A function f:[n_1] x ... x [n_d]-->F is a direct sum if it is of the form f(a_1,...,a_d) = f_1(a_1) + ... + f_d (a_d) (mod 2) for some d functions f_i:[n_i]-->F_i for all i=1,...,d. We present a 4-query test which distinguishes between direct sums and functions that are far from them. The test relies on the BLR linearity test (Blum, Luby, Rubinfeld, 1993) and on an agreement test which slightly generalizes the direct product test.
In multiplicative {+1,-1} notation, our result reads as follows. A d-dimensional tensor with {+1,-1} entries is called a tensor product if it is a tensor product of d vectors with {+1,-1} entries, or equivalently, if it is of rank 1. The presented tests can be read as tests for distinguishing between tensor products and tensors that are far from being tensor products.
We also present a different test, which queries the function at most (d+2) times, but is easier to analyze.
Tue, 08 Oct 2019 21:27:56 +0300https://eccc.weizmann.ac.il/report/2019/139
- TR19-138 | On the Probabilistic Degrees of Symmetric Boolean functions |
Srikanth Srinivasan,
Utkarsh Tripathi,
S Venkitesh
https://eccc.weizmann.ac.il/report/2019/138The probabilistic degree of a Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is defined to be the smallest $d$ such that there is a random polynomial $\mathbf{P}$ of degree at most $d$ that agrees with $f$ at each point with high probability. Introduced by Razborov (1987), upper and lower bounds on probabilistic degrees of Boolean functions --- specifically symmetric Boolean functions --- have been used to prove explicit lower bounds, design pseudorandom generators, and devise algorithms for combinatorial problems.
In this paper, we characterize the probabilistic degrees of all symmetric Boolean functions up to polylogarithmic factors over all fields of fixed characteristic (positive or zero).Sun, 06 Oct 2019 18:42:51 +0300https://eccc.weizmann.ac.il/report/2019/138
- TR19-137 | Decision list compression by mild random restrictions |
Shachar Lovett,
Kewen Wu,
Jiapeng Zhang
https://eccc.weizmann.ac.il/report/2019/137A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the value corresponding to the first rule whole term is satisfied by the input. Decision lists generalize both CNFs and DNFs, and have been studied both in complexity theory and in learning theory.
The size of a decision list is the number of rules, and its width is the maximal number of variables in a term. We prove that decision lists of small width can always be approximated by decision lists of small size, where we obtain sharp bounds (up to constants). This in particular resolves a conjecture of Gopalan, Meka and Reingold (Computational Complexity, 2013) on DNF sparsification.
An ingredient in our proof is a new random restriction lemma, which allows to analyze how DNFs (and more generally, decision lists) simplify if a small fraction of the variables are fixed. This is in contrast to the more commonly used switching lemma, which requires most of the variables to be fixed.Sun, 06 Oct 2019 14:20:34 +0300https://eccc.weizmann.ac.il/report/2019/137
- TR19-136 | Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead |
Sourav Chakraborty,
Arkadev Chattopadhyay,
Nikhil Mande,
Manaswi Paraashar
https://eccc.weizmann.ac.il/report/2019/136Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function $f : \{-1, 1\}^n \to \{-1, 1\}$ and $\bullet : \{-1, 1\}^2 \to \{-1, 1\}$ the two-party bounded-error quantum communication complexity of $(f \circ \bullet)$ is $O(Q(f) \log n)$, where $Q(f)$ is the bounded-error quantum query complexity of $f$. Note that the bounded-error randomized communication complexity of $(f \circ \bullet)$ is bounded by $O(R(f))$, where $R(f)$ denotes the bounded-error randomized query complexity of $f$. Thus, the BCW simulation has an extra $O(\log n)$ factor appearing that is absent in classical simulation. A natural question is if this factor can be avoided. H{\o}yer and de Wolf (STACS'02) showed that for the Set-Disjointness function, this can be reduced to $c^{\log^* n}$ for some constant $c$, and subsequently Aaronson and Ambainis (FOCS'03) showed that this factor can be made a constant. That is, the quantum communication complexity of the Set-Disjointness function (which is $NOR_n \circ \wedge$) is $O(Q(NOR_n))$.
Perhaps somewhat surprisingly, we show that when $ \bullet = \oplus$, then the extra $\log n$ factor in the BCW simulation is unavoidable. In other words, we exhibit a total function $F : \{-1, 1\}^n \to \{-1, 1\}$ such that $Q^{cc}(F \circ \oplus) = \Theta(Q(F) \log n)$.
To the best of our knowledge, it was not even known prior to this work whether there existed a total function $F$ and 2-bit function $\bullet$, such that $Q^{cc}(F \circ \bullet) = \omega(Q(F))$.
Sun, 06 Oct 2019 12:03:52 +0300https://eccc.weizmann.ac.il/report/2019/136
- TR19-135 | Doubly-Efficient Pseudo-Deterministic Proofs |
Dhiraj Holden,
Shafi Goldwasser,
Michel Goemans
https://eccc.weizmann.ac.il/report/2019/135In [20] Goldwasser, Grossman and Holden introduced pseudo-deterministic interactive proofs for search problems where a powerful prover can convince a probabilistic polynomial time verifier that a solution to a search problem is canonical. They studied search problems for which polynomial time algorithms are not known and for which many solutions are possible. They showed that whereas there exists a constant round pseudo deterministic proof for graph isomorphism where the canonical solution is the lexicographically smallest isomorphism, the existence of pseudo-deterministic interactive proofs for NP-hard problems would imply the collapse of the polynomial time hierarchy.
In this paper, we turn our attention to studying doubly-efficient pseudo-deterministic proofs for polynomial time search problems: pseudo-deterministic proofs with the extra requirement that the prover runtime is polynomial and the verifier runtime to verify that a solution is canonical is significantly lower than the complexity of finding any solution, canonical or otherwise. Naturally this question is particularly interesting for search problems for which a lower bound on its worst case complexity is known or has been widely conjectured.
We show doubly-efficient pseudo-deterministic algorithms for a host of natural problems whose complexity has long been conjectured. In particular:
We show a doubly efficient pseudo-deterministic proof for linear programming where the canonical solution which the prover will provide is the lexicographically greatest optimal solution for the LP. To this end, we show how through perturbing the linear program and strong duality this solution can be both computed efficiently by the prover, and verified by the verifier.
The time of the verifier is $O(d^2 )$ for a linear program with integer data and at most $d$ variables and constraints, whereas the time to solve such linear program is $\tilde{O}(d^{\omega} )$ by randomized algorithms [11] for $\omega$ the exponent for fast matrix multiplication .
We show a doubly efficient pseudo-deterministic proof for 3-SUM and problems reducible to 3-SUM where the prover is a $O(n^2)$ time algorithm and the verifier takes time $\tilde{O}(n^{1.5})$.
We show a doubly-efficient pseudo-deterministic proof for the hitting set problem} where the verifier runs in time $\tilde{O}(m)$ and the prover runs in time $\tilde{O}(m^2)$ where $ m = \sum_{S \in \mathcal{S}} |S| + \sum_{T \in \mathcal{T}} |T|$ for inputs collections of sets $\mathcal{S}, \mathcal{T}$.
We show a doubly-efficient pseudo-deterministic proof for the Zero Weight Triangle problem where the verifier runs in time $\tilde{O}(n^{2 + \omega/3})$ and the prover runs in randomized time $\tilde{O}(n^3)$. The Zero Weight Triangle problem is equivalent to the All-Pairs Shortest Path problem, a well-studied problem that is the foundation of many hardness results in graph algorithms [39,38], under sub-cubic reductions.
Fri, 04 Oct 2019 18:50:06 +0300https://eccc.weizmann.ac.il/report/2019/135
- TR19-134 | Finding monotone patterns in sublinear time |
Omri Ben-Eliezer,
Clement Canonne,
Shoham Letzter,
Erik Waingarten
https://eccc.weizmann.ac.il/report/2019/134We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed $k \in \mathbb{N}$ and $\varepsilon > 0$, we show that the non-adaptive query complexity of finding a length-$k$ monotone subsequence of $f \colon [n] \to \mathbb{R}$, assuming that $f$ is $\varepsilon$-far from free of such subsequences, is $\Theta((\log n)^{\lfloor \log_2 k \rfloor})$. Prior to our work, the best algorithm for this problem, due to Newman, Rabinovich, Rajendraprasad, and Sohler (2017), made $(\log n)^{O(k^2)}$ non-adaptive queries; and the only lower bound known, of $\Omega(\log n)$ queries for the case $k = 2$, followed from that on testing monotonicity due to Erg\"un, Kannan, Kumar, Rubinfeld, and Viswanathan (2000) and Fischer (2004).Fri, 04 Oct 2019 18:42:39 +0300https://eccc.weizmann.ac.il/report/2019/134
- TR19-133 | More on $AC^0[\oplus]$ and Variants of the Majority Function |
Utkarsh Tripathi,
Nutan Limaye,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2019/133In this paper we prove two results about $AC^0[\oplus]$ circuits.
We show that for $d(N) = o(\sqrt{\log N/\log \log N})$ and $N \leq s(N) \leq 2^{dN^{1/d^2}}$ there is an explicit family of functions $\{f_N:\{0,1\}^N\rightarrow \{0,1\}\}$ such that
$f_N$ has uniform $AC^0$ formulas of depth $d$ and size at most $s$;
$f_N$ does not have $AC^0[\oplus]$ formulas of depth $d$ and size $s^{\varepsilon}$, where $\varepsilon$ is a fixed absolute constant.
This gives a quantitative improvement on the recent result of Limaye, Srinivasan, Sreenivasaiah, Tripathi, and Venkitesh, (STOC, 2019), which proved a similar Fixed-Depth Size-Hierarchy theorem but for $d \ll \log \log N$ and $s \ll \exp(N^{1/2^{\Omega(d)}})$.
As in the previous result, we use the Coin Problem to prove our hierarchy theorem. Our main technical result is the construction of uniform size-optimal formulas for solving the coin problem with improved sample complexity $(1/\delta)^{d+4}$ (down from $(1/\delta)^{2^{O(d)}}$ in the previous result).
In our second result, we show that randomness buys depth in the $AC^0[\oplus]$ setting. Formally, we show that for any fixed constant $d\geq 2$, there is a family of Boolean functions that has polynomial-sized randomized uniform $AC^0$ circuits of depth $d$ but no polynomial-sized (deterministic) $AC^0[\oplus]$ circuits of depth $d$.
Previously Viola (Computational Complexity, 2014) showed that an increase in depth (by at least $2$) is essential to avoid superpolynomial blow-up while derandomizing randomized $AC^0$ circuits. We show that an increase in depth (by at least $1$) is essential even for $AC^0[\oplus]$.
As in Viola's result, the separating examples are promise variants of the Majority function on $N$ inputs that accept inputs of weight at least $N/2 + N/(\log N)^{d-1}$ and reject inputs of weight at most $N/2 - N/(\log N)^{d-1}$.
Wed, 02 Oct 2019 14:00:43 +0300https://eccc.weizmann.ac.il/report/2019/133
- TR19-132 | Radio Network Coding Requires Logarithmic Overhead |
Raghuvansh Saxena,
Klim Efremenko,
Gillat Kol
https://eccc.weizmann.ac.il/report/2019/132We consider the celebrated radio network model for abstracting communication in wireless networks. In this model, in any round, each node in the network may broadcast a message to all its neighbors. However, a node is able to hear a message broadcast by a neighbor only if no collision occurred, meaning that it was the only neighbor broadcasting.
While the (noiseless) radio network model received a lot of attention over the last few decades, the effect of noise on radio networks is still not well understood. In this paper, we take a step forward and show that making radio network protocols resilient to noise may require a substantial performance overhead. Specifically, we construct a multi-hop network and a communication protocol over this network that works in $T$ rounds when there is no noise. We prove that any scheme that simulates our protocol and is resilient to stochastic noise, requires $\Omega(T \log n)$ rounds.
This stands in contrast to our previous result (STOC, 2018), showing that protocols over the single-hop (clique) network can be made noise resilient with only a constant overhead. Our result also settles a recent conjecture by Censor{-}Hillel, Haeupler, Hershkowitz, Zuzic (2018).
We complement the above result by giving a scheme to simulate any protocol with a fixed order of transmissions with only an $\mathcal{O}(\log n)$ overhead.Mon, 30 Sep 2019 20:48:38 +0300https://eccc.weizmann.ac.il/report/2019/132
- TR19-131 | A Simple Proof of Vyalyi's Theorem and some Generalizations |
Lieuwe Vinkhuijzen,
AndrĂ© Deutz
https://eccc.weizmann.ac.il/report/2019/131In quantum computational complexity theory, the class QMA models the set of problems efficiently verifiable by a quantum computer the same way that NP models this for classical computation. Vyalyi proved that if $\text{QMA}=\text{PP}$ then $\text{PH}\subseteq \text{QMA}$. In this note, we give a simple, self-contained proof of the theorem, using only the closure properties of the complexity classes in the theorem statement. We then extend the theorem in two directions: (i) we strengthen the consequent, proving that if $\text{QMA}=\text{PP}$ then $\text{QMA}=\text{PH}^{\text{PP}}$, and (ii) we weaken the hypothesis, proving that if $\text{QMA}=\text{coQMA}$ then $\text{PH}\subseteq \text{QMA}$. Lastly, we show that all the above results hold, without loss of generality, for the class QAM instead of QMA. We also formulate a ``Quantum Toda's Conjecture''.Mon, 30 Sep 2019 17:57:20 +0300https://eccc.weizmann.ac.il/report/2019/131