ECCC - Reportshttps://example.com/Latest Reports published at https://eccc.weizmann.ac.ilen-usSun, 21 Jan 2018 13:34:35 +0200TR18-014 | A Composition Theorem via Conflict Complexity |
Swagato Sanyal
https://eccc.weizmann.ac.il/report/2018/014Let $\R(\cdot)$ stand for the bounded-error randomized query complexity. We show that for any relation $f \subseteq \{0,1\}^n \times \mathcal{S}$ and partial Boolean function $g \subseteq \{0,1\}^n \times \{0,1\}$, $\R_{1/3}(f \circ g^n) = \Omega(\R_{4/9}(f) \cdot \sqrt{\R_{1/3}(g)})$. Independently of us, Gavinsky, Lee and Santha \cite{newcomp} proved this result. By an example demonstrated in their work, this bound is optimal. We prove our result by introducing a novel complexity measure called the \emph{conflict complexity} of a partial Boolean function $g$, denoted by $\chi(g)$, which may be of independent interest. We show that $\chi(g) = \Omega(\sqrt{\R(g)})$ and $\R(f \circ g^n) = \Omega(\R(f) \cdot \chi(g))$.Sun, 21 Jan 2018 13:34:35 +0200https://eccc.weizmann.ac.il/report/2018/014TR18-013 | Nondeterminisic Sublinear Time Has Measure 0 in P |
John Hitchcock,
Adewale Sekoni
https://eccc.weizmann.ac.il/report/2018/013The measure hypothesis is a quantitative strengthening of the P $\neq$ NP conjecture which asserts that NP is a nonnegligible subset of EXP. Cai, Sivakumar, and Strauss (1997) showed that the analogue of this hypothesis in P is false. In particular, they showed that NTIME[$n^{1/11}$] has measure 0 in P. We improve on their result to show that the class of all languages decidable in nondeterministic sublinear time has measure 0 in P. Our result is based on DNF width and holds for all four major notions of measure on P.Sun, 21 Jan 2018 13:31:39 +0200https://eccc.weizmann.ac.il/report/2018/013TR18-012 | Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates |
Valentine Kabanets,
Zhenjian Lu
https://eccc.weizmann.ac.il/report/2018/012We show how the classical Nisan-Wigderson (NW) generator [Nisan & Wigderson, 1994] yields a nontrivial pseudorandom generator (PRG) for circuits with sublinearly many polynomial threshold function (PTF) gates. For the special case of a single PTF of degree $d$ on $n$ inputs, our PRG for error $\epsilon$ has the seed size
$$\exp\left(O(\sqrt{d\cdot\log n\cdot \log\log (n/\epsilon)})\right);$$ this can give a super-polynomial stretch even for a sub-exponentially small error parameter $\epsilon=\exp(-n^{\gamma})$, for any $\gamma=o(1)$. In contrast, the best known PRGs for PTFs of [Meka & Zuckerman, 2013; Kane, 2012] cannot achieve such a small error, although they do have a much shorter seed size for any constant error $\epsilon$.
For the case of circuits with degree-$d$ PTF gates on $n$ inputs, our PRG can fool circuits with at most $n^{\alpha/d}$ gates with error $\exp(-n^{\alpha/d})$ and seed length $n^{O(\sqrt{\alpha})}$, for any $\alpha>1$.
While a similar NW PRG construction was observed by Lovett and Srinivasan [Lovett & Srinivasan, 2011] to work for the case of constant-depth (AC$^0$) circuits with few PTF gates, the application of the NW generator to the case of general (unbounded depth) circuits consisting of a sublinear number of PTF gates does not seem to have been explicitly stated before. We do so in this note.Sat, 20 Jan 2018 05:19:07 +0200https://eccc.weizmann.ac.il/report/2018/012TR18-011 | Nonuniform Reductions and NP-Completeness |
John Hitchcock,
Hadi Shafei
https://eccc.weizmann.ac.il/report/2018/011Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP-completeness, obtaining both separations and upper bounds for nonuniform completeness vs uniform completeness in NP.
Under various hypotheses, we obtain the following separations:
1. There is a set complete for NP under nonuniform many-one reductions, but not under uniform many-one reductions. This is true even with a single bit of nonuniform advice.
2. There is a set complete for NP under nonuniform many-one reductions with polynomial-size advice, but not under uniform Turing reductions. That is, polynomial nonuniformity is stronger than a polynomial number of queries.
3. For any fixed polynomial p(n), there is a set complete for NP under uniform 2-truth-table reductions, but not under nonuniform many-one reductions that use p(n) advice. That is, giving a uniform reduction a second query makes it more powerful than a nonuniform reduction with fixed polynomial advice.
4. There is a set complete for NP under nonuniform many-one reductions with polynomial ad- vice, but not under nonuniform many-one reductions with logarithmic advice. This hierarchy theorem also holds for other reducibilities, such as truth-table and Turing.
We also consider uniform upper bounds on nonuniform completeness. Hirahara (2015) showed that unconditionally every set that is complete for NP under nonuniform truth-table reductions that use logarithmic advice is also uniformly Turing-complete. We show that under a derandomization hypothesis, the same statement for truth-table reductions and truth-table completeness also holds.Thu, 18 Jan 2018 15:06:11 +0200https://eccc.weizmann.ac.il/report/2018/011TR18-010 | Algorithmic polynomials |
Alexander A. Sherstov
https://eccc.weizmann.ac.il/report/2018/010The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity.
We develop a first-principles, classical approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems:
- $O\bigl(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}}\bigr)$ for the $k$-element distinctness problem;
- $O(n^{1-\frac{1}{k+1}})$ for the $k$-subset sum problem;
- $O(n^{1-\frac{1}{k+1}})$ for any $k$-DNF or $k$-CNF formula;
- $O(n^{3/4})$ for the surjectivity problem.
In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the $\Theta(n)$ quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree $\Omega(n)$. In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.
Mon, 15 Jan 2018 00:33:24 +0200https://eccc.weizmann.ac.il/report/2018/010TR18-009 | Non-Interactive Delegation for Low-Space Non-Deterministic Computation |
Saikrishna Badrinarayanan,
Yael Kalai,
Dakshita Khurana,
Amit Sahai,
Daniel Wichs
https://eccc.weizmann.ac.il/report/2018/009We construct a delegation scheme for verifying non-deterministic computations, with complexity proportional only to the non-deterministic space of the computation. Specifically, letting $n$ denote the input length, we construct a delegation scheme for any language verifiable in non-deterministic time and space $(T(n);S(n))$ with communication complexity $poly(S(n))$, verifier runtime $n polylog(T(n))+poly(S(n))$, and prover runtime $poly(T(n))$.
Our scheme consists of only two messages and has adaptive soundness, assuming the existence of a sub-exponentially secure private information retrieval (PIR) scheme, which can be instantiated under standard (albeit, sub-exponential) cryptographic assumptions, such as the sub-exponential LWE assumption. Specifically, the verifier publishes a (short) public key ahead of time, and this key can be used by any prover to non-interactively prove the correctness of any adaptively chosen non-deterministic computation. Such a scheme is referred to as a noninteractive delegation scheme. Our scheme is privately verifiable, where the verifier needs the corresponding secret key in order to verify proofs.
Prior to our work, such results were known only in the Random Oracle Model, or under knowledge assumptions. Our results yield succinct non-interactive arguments based on subexponential LWE, for many natural languages believed to be outside of P.Sun, 14 Jan 2018 18:49:06 +0200https://eccc.weizmann.ac.il/report/2018/009TR18-008 | An Entropy Lower Bound for Non-Malleable Extractors |
Tom Gur,
Igor Shinkar
https://eccc.weizmann.ac.il/report/2018/008A (k,\eps)-non-malleable extractor is a function nmExt : {0,1}^n x {0,1}^d -> {0,1} that takes two inputs, a weak source X~{0,1}^n of min-entropy k and an independent uniform seed s in {0,1}^d, and outputs a bit nmExt(X, s) that is \eps-close to uniform, even given the seed s and the value nmExt(X, s') for an adversarially chosen seed s' \neq s. Dodis and Wichs~(STOC 2009) showed the existence of (k, \eps)-non-malleable extractors with seed length d = \log(n-k-1) + 2\log(1/\eps) + 6 that support sources of entropy k > \log(d) + 2 \log(1/\eps) + 8.
We show that the foregoing bound is essentially tight by proving that any (k,\eps)-non-malleable extractor must satisfy the entropy bound k > \log(d) + 2 \log(1/\eps) - \log\log(1/\eps) - CĀ for an absolute constant C. In particular, this implies that non-malleable extractors require min-entropy at least \Omega(\log\log(n)). This is in stark contrast to the existence of strong seeded extractors that support sources of entropy k = O(\log(1/\eps)).
Our techniques strongly rely on coding theory. In particular, we reveal an inherent connection between non-malleable extractors and error correcting codes, by proving a new lemma which shows that any (k,\eps)-non-malleable extractor with seed length d induces a code C \seq {0,1}^{2^k} with relative distance 0.5 - 2\eps and rate (d-1)/(2^k).Thu, 11 Jan 2018 17:25:59 +0200https://eccc.weizmann.ac.il/report/2018/008TR18-007 | A Generalized Turan Problem and its Applications |
Lior Gishboliner,
Asaf Shapira
https://eccc.weizmann.ac.il/report/2018/007Our first theorem in this papers is a hierarchy theorem for the query complexity of testing graph properties with $1$-sided error; more precisely, we show that for every super-polynomial $f$, there is a graph property whose 1-sided-error query complexity is $f(\Theta(1/\varepsilon))$. No result of this type was previously known for any $f$ which is super polynomial. Goldreich [ECCC 2005] asked to exhibit a graph property whose query complexity is $2^{\Theta(1/\varepsilon)}$. Our hierarchy theorem partially resolves this problem by exhibiting a property whose 1-sided-error query complexity is $2^{\Theta(1/\varepsilon)}$. We also use our hierarchy theorem in order to resolve a problem raised by the second author and Alon [STOC 2005] regarding testing relaxed versions of bipartiteness.
Our second theorem states that for any function $f$ there is a graph property whose 1-sided-error query complexity is $f(\Theta(1/\varepsilon))$ while its $2$-sided-error query complexity is only $\poly(1/\varepsilon)$. This is the first indication of the surprising power that 2-sided-error testing algorithms have over 1-sided-error ones, even when restricted to properties that are testable with $1$-sided error. Again, no result of this type was previously known for any $f$ that is super polynomial.
The above two theorems are derived from a graph theoretic result which we think is of independent interest, and might have further applications. Alon and Shikhelman [JCTB 2016] recently introduced the following generalized Turan problem: for fixed graphs $H$ and $T$, and an integer $n$, what is the maximum number of copies of $T$, denoted by $\mbox{ex}(n,T,H)$, that can appear in an $n$-vertex $H$-free graph? This problem received a lot of attention recently, with an emphasis on $\mbox{ex}(n,C_3,C_{2\ell +1})$. Our third theorem in this paper gives tight bounds for $\mbox{ex}(n,C_k,C_{\ell})$ for all the remaining values of $k$ and $\ell$.Thu, 11 Jan 2018 13:27:33 +0200https://eccc.weizmann.ac.il/report/2018/007TR18-006 | Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion |
Subhash Khot,
Dor Minzer,
Muli Safra
https://eccc.weizmann.ac.il/report/2018/006We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes
the proof of the $2$-to-$2$ Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a
contribution from [BKT].
The Grassmann graph $Gr_{global}$ contains induced subgraphs $Gr_{local}$ that are themselves isomorphic to Grassmann graphs of lower orders.
A set is called pseudorandom if its density is $o(1)$ inside all subgraphs $Gr_{local}$ whose order is $O(1)$ lower than that of $Gr_{global}$.
We prove that pseudorandom sets have expansion $1-o(1)$, greatly extending the results and techniques in [DKKMS-2].Wed, 10 Jan 2018 01:45:48 +0200https://eccc.weizmann.ac.il/report/2018/006TR18-005 | Adaptive Boolean Monotonicity Testing in Total Influence Time |
C. Seshadhri,
Deeparnab Chakrabarty
https://eccc.weizmann.ac.il/report/2018/005The problem of testing monotonicity
of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ has received much attention
recently. Denoting the proximity parameter by $\varepsilon$, the best tester is the non-adaptive $\widetilde{O}(\sqrt{n}/\varepsilon^2)$ tester
of Khot-Minzer-Safra (FOCS 2015). Let $I(f)$ denote the total influence
of $f$. We give an adaptive tester whose running time is $I(f)poly(\varepsilon^{-1}\log n)$.Tue, 09 Jan 2018 16:22:35 +0200https://eccc.weizmann.ac.il/report/2018/005