ECCC - Reportshttps://example.com/Latest Reports published at https://eccc.weizmann.ac.ilen-usWed, 22 Feb 2017 09:18:30 +0200TR17-034 | On algebraic branching programs of small width |
Karl Bringmann,
Christian Ikenmeyer,
Jeroen Zuiddam
https://eccc.weizmann.ac.il/report/2017/034In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the class of polynomials that can be approximated arbitrarily closely by polynomials in VP_e. We describe VP_e-bar with a strikingly simple complete polynomial (in characteristic different from 2) whose recursive definition is similar to the Fibonacci numbers. Further understanding this polynomial seems to be a promising route to new formula lower bounds.
Our methods are rooted in the study of ABPs of small constant width. In 1992 Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction lead to the aforementioned characterization of VP_e-bar.
As a natural continuation of this work we prove that the class VNP can be described as the class of families that admit a hypercube summation of polynomially bounded dimension over a product of polynomially many affine linear forms. This gives the first separations of algebraic complexity classes from their nondeterministic analogs.Wed, 22 Feb 2017 09:18:30 +0200https://eccc.weizmann.ac.il/report/2017/034TR17-033 | Labeling the complete bipartite graph with no zero cycles |
Daniel Kane,
Shachar Lovett,
Sankeerth Rao
https://eccc.weizmann.ac.il/report/2017/033Assume that the edges of the complete bipartite graph $K_{n,n}$ are labeled with elements of $\mathbb{F}_2^d$, such that the sum over
any simple cycle is nonzero. What is the smallest possible value of $d$? This problem was raised by Gopalan et al. [SODA 2017] as it characterizes the alphabet size needed for maximally recoverable codes in grid topologies.
We show that the answer is that $d$ is linear in $n$. The upper bound is an explicit construction which improves upon the random construction. The lower bound is more technical, and relies on the study of independent sets in certain Cayley graphs of the permutation group.
Sun, 19 Feb 2017 20:38:32 +0200https://eccc.weizmann.ac.il/report/2017/033TR17-032 | Formulas with Large Weight: a New Technique for Genuine QBF Lower Bounds |
Joshua Blinkhorn,
Olaf Beyersdorff
https://eccc.weizmann.ac.il/report/2017/032We devise a new technique to prove lower bounds for the proof size in resolution-type calculi for quantified Boolean formulas (QBF). The new technique applies to the strong expansion system IR-calc and thereby also to the most studied QBF system Q-Resolution.
Our technique exploits a clear semantic paradigm, showing the hardness of a QBF family by demonstrating that
(1) the formulas require large witnessing functions for the universal variables, and (2) in the game semantics of QBF, the universal player is forced to make many responses on a set of variables that we identify as critical.
Based on these two conditions, our technique yields a weight for a QBF formula, which provides an absolute lower bound for the size of its IR-calc proofs (and hence also its Q-Resolution proofs).
We exemplify our technique on a couple of known and new instances, among them the prominent formulas of Kleine Büning et al. (Inform. Comput. 1995), for which our method provides a hardness proof that is considerably simpler than previous approaches.
Our technique also provides the first separations for QBF dependency calculi. In particular, we construct a simple class of formulas that are hard for Q-Resolution, but easy in Q-Resolution parameterized by the reflexive resolution path dependency scheme, thus answering a question posed by Slivovsky and Szeider (SAT 2014).Sun, 19 Feb 2017 09:29:14 +0200https://eccc.weizmann.ac.il/report/2017/032TR17-031 | Quadratic Simulations of Merlin-Arthur Games |
Thomas Watson
https://eccc.weizmann.ac.il/report/2017/031The known proofs of $\text{MA}\subseteq\text{PP}$ incur a quadratic overhead in the running time. We prove that this quadratic overhead is necessary for black-box simulations; in particular, we obtain an oracle relative to which $\text{MA-TIME}(t)\not\subseteq\text{P-TIME}(o(t^2))$. We also show that 2-sided-error Merlin--Arthur games can be simulated by 1-sided-error Arthur--Merlin games with quadratic overhead. We also present a simple, query complexity based proof (provided by Mika G\"o\"os) that there is an oracle relative to which $\text{MA}\not\subseteq\text{NP}^{\text{BPP}}$ (which was previously known to hold by a proof using generics).
Sun, 19 Feb 2017 09:28:19 +0200https://eccc.weizmann.ac.il/report/2017/031TR17-030 | An Improved Dictatorship Test with Perfect Completeness |
Amey Bhangale,
Subhash Khot,
Devanathan Thiruvenkatachari
https://eccc.weizmann.ac.il/report/2017/030A Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is called a dictator if it depends on exactly one variable i.e $f(x_1, x_2, \ldots, x_n) = x_i$ for some $i\in [n]$. In this work, we study a $k$-query dictatorship test. Dictatorship tests are central in proving many hardness results for constraint satisfaction problems.
The dictatorship test is said to have {\em perfect completeness} if it accepts any dictator function. The {\em soundness} of a test is the maximum probability with which it accepts any function far from a dictator. Our main result is a $k$-query dictatorship test with perfect completeness and soundness $ \frac{2k + 1}{2^k}$, where $k$ is of the form $2^t -1$ for any integer $t > 2$. This improves upon the result of \cite{TY15} which gave a dictatorship test with soundness $ \frac{2k + 3}{2^k}$.Sat, 18 Feb 2017 17:23:23 +0200https://eccc.weizmann.ac.il/report/2017/030TR17-029 | An Adaptivity Hierarchy Theorem for Property Testing |
Tom Gur,
Clement Canonne
https://eccc.weizmann.ac.il/report/2017/029Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of \emph{adaptive} testing algorithms, wherein each query may be determined by the answers received to prior queries, and their \emph{non-adaptive} counterparts, in which all queries are independent of answers obtained from previous queries.
In this work, we investigate the role of adaptivity in property testing at a finer level. We first quantify the degree of adaptivity of a testing algorithm by considering the number of ``rounds of adaptivity'' it uses. More accurately, we say that a tester is $k$-(round) adaptive if it makes queries in $k+1$ rounds, where the queries in the $i$'th round may depend on the answers obtained in the previous $i-1$ rounds. Then, we ask the following question:
Does the power of testing algorithms smoothly grow with the number of rounds of adaptivity?
We provide a positive answer to the foregoing question by proving an adaptivity hierarchy theorem for property testing. Specifically, our main result shows that for every $n\in \N$ and $0 \le k \le n^{0.99}$ there exists a property $\mathcal{P}_{n,k}$ of functions for which (1) there exists a $k$-adaptive tester for $\mathcal{P}_{n,k}$ with query complexity $\tildeO{k}$, yet (2) any $(k-1)$-adaptive tester for $\mathcal{P}_{n,k}$ must make $\Omega(n)$ queries. In addition, we show that such a qualitative adaptivity hierarchy can be witnessed for testing natural properties of graphs.
Sat, 18 Feb 2017 17:19:14 +0200https://eccc.weizmann.ac.il/report/2017/029TR17-028 | A quadratic lower bound for homogeneous algebraic branching programs |
Mrinal Kumar
https://eccc.weizmann.ac.il/report/2017/028An algebraic branching program (ABP) is a directed acyclic graph, with a start vertex $s$, and end vertex $t$ and each edge having a weight which is an affine form in $\F[x_1, x_2, \ldots, x_n]$. An ABP computes a polynomial in a natural way, as the sum of weights of all paths from $s$ to $t$, where the weight of a path is the product of the weights of the edges in the path. An ABP is said to be homogeneous if the polynomial computed at every vertex is homogeneous. In this paper, we show that any homogeneous algebraic branching which computes the polynomial $x_1^n + x_2^n + \ldots + x_n^n$ has at least $\Omega(n^2)$ vertices (and hence edges).
To the best of our knowledge, this seems to be the first non-trivial super-linear lower bound on the number of vertices for a general \emph{homogeneous} ABP and slightly improves the known lower bound of $\Omega(n\log n)$ on the number of edges of in a general (possibly \emph{non-homogeneous}) ABP, which follows from the classical results of Strassen~\cite{Strassen73} and Baur \& Strassen~\cite{BS83}.
On the way, we also get an alternate and essentially unified proof of an $\Omega(n\log n)$ lower bound on the size of a \emph{homogeneous} arithmetic circuit (follows from~\cite{Strassen73, BS83}), and an $n/2$ lower bound ($n$ over $\mathbb{R}$) on the determinantal complexity of an explicit polynomial~\cite{mr04, CCL10, Yabe15}. These are currently the best lower bounds known for these problems for any explicit polynomial, and were originally proved nearly two decades apart using seemingly different proof techniques.
Fri, 17 Feb 2017 18:44:14 +0200https://eccc.weizmann.ac.il/report/2017/028TR17-027 | A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate |
Dean Doron,
Avraham Ben-Aroya,
Amnon Ta-Shma,
Eshan Chattopadhyay,
Xin Li
https://eccc.weizmann.ac.il/report/2017/027We show a reduction from the existence of explicit t-non-malleable
extractors with a small seed length, to the construction of explicit
two-source extractors with small error for sources with arbitrarily
small constant rate. Previously, such a reduction was known either
when one source had entropy rate above half [Raz05] or for
general entropy rates but only for large error [CZ16].
As in previous reductions we start with the Chattopadhyay and
Zuckerman approach [CZ16], where an extractor is applied on one
source to create a table, and the second source is used to sample a
sub-table. In previous work, a resilient function was applied on the
sub-table and the use of resilient functions immediately implied
large error. In this work we replace the resilient function with the
parity function (that is not resilient). We prove correctness by
showing that doing the sampling properly, the sample size can be
made so small that it is smaller then the non-malleability parameter
t of the first extractor, which is enough for the correctness.
The parameters we require from the non-malleable construction hold
(quite comfortably) in a non-explicit construction, but currently it
is not known how to explicitly construct such graphs. As a result we
do not give an unconditional construction of an explicit low-error
two-source extractor. However, the reduction shows a new connection
between non-malleable and two-source extractors, and also shows
resilient functions do not play a crucial role in the two-source
construction framework suggested in [CZ16]. Furthermore, the
reduction highlights a barrier in constructing non-malleable
extractors, and reveals its importance. We hope this work would lead
to further developments in explicit constructions of both
non-malleable and two-source extractors.Fri, 17 Feb 2017 16:20:08 +0200https://eccc.weizmann.ac.il/report/2017/027TR17-026 | A Polynomial Restriction Lemma with Applications |
Valentine Kabanets,
Daniel Kane,
Zhenjian Lu
https://eccc.weizmann.ac.il/report/2017/026A polynomial threshold function (PTF) of degree $d$ is a boolean function of the form $f=\mathrm{sgn}(p)$, where $p$ is a degree-$d$ polynomial, and $\mathrm{sgn}$ is the sign function. The main result of the paper is an almost optimal bound on the probability that a random restriction of a PTF is not close to a constant function, where a boolean function $g$ is called $\delta$-close to constant if, for some $v\in\{1,-1\}$, we have $g(x)=v$ for all but at most $\delta$ fraction of inputs. We show for every PTF $f$ of degree $d\geq 1$, and parameters $0<\delta, r\leq 1/16$, that \[\mathbf{Pr}_{\rho\sim R_r} [f_{\rho} \text{ is not } \delta \text{-close to constant}] \leq (\sqrt{r} + \delta)\cdot (\log (1/r) \cdot \log (1/\delta))^{O(d^2)},\] where $\rho\sim R_r$ is a random restriction leaving each variable, independently, free with probability $r$, and otherwise assigning it $1$ or $-1$ uniformly at random. In fact, we show a more general result for random block restrictions: given an arbitrary partitioning of input variables into $m$ blocks, a random block restriction picks a uniformly random block $\ell\in [m]$ and assigns $1$ or $-1$, uniformly at random, to all variable outside the chosen block $\ell$. We prove the Block Restriction Lemma saying that a PTF $f$ of degree $d$ becomes $\delta$-close to constant when hit with a random block restriction, except with probability at most $(m^{-1/2}+\delta)\cdot (\log m\cdot \log (1/\delta))^{O(d^2)}$.
As an application of our Restriction Lemma, we prove lower bounds against constant-depth circuits with PTF gates of any degree $1\leq d\ll \sqrt{\log n/\log\log n}$, generalizing the recent bounds against constant-depth circuits with linear threshold gates (LTF gates) proved by Kane and Williams (STOC, 2016) and Chen, Santhanam, and Srinivasan (CCC, 2016). In particular, we show that there is an $n$-variate boolean function $F_n \in \mathrm{P}$ such that every depth-2 circuit with PTF gates of degree $d\geq 1$ that computes $F_n$ must have at least $\left(n^{\frac{3}{2}+\frac{1}{d}}\right)\cdot (\log n)^{-O(d^2)}$ wires. For constant depths greater than $2$, we also show average-case lower bounds for such circuits with super-linear number of wires. These are the first super-linear bounds on the number of wires for circuits with PTF gates. We also give short proofs of the optimal-exponent average sensitivity bound for degree-$d$ PTFs due to Kane (Computational Complexity, 2014), and the Littlewood-Offord type anticoncentration bound for degree-$d$ multilinear polynomials due to Meka, Nguyen, and Vu (Theory of Computing, 2016).
Finally, we give derandomized versions of our Block Restriction Lemma and Littlewood-Offord type anticoncentration bounds, using a pseudorandom generator for PTFs due to Meka and Zuckerman (SICOMP, 2013).Fri, 17 Feb 2017 03:45:57 +0200https://eccc.weizmann.ac.il/report/2017/026TR17-025 | Pseudorandom Generators for Low-Sensitivity Functions |
Pooya Hatami,
Avishay Tal
https://eccc.weizmann.ac.il/report/2017/025A Boolean function is said to have maximal sensitivity $s$ if $s$ is the largest number of Hamming neighbors of a point which differ from it in function value. We construct a pseudorandom generator with seed-length $2^{O(\sqrt{s})} \cdot \log(n)$ that fools Boolean functions on $n$ variables with maximal sensitivity at most $s$. Prior to our work, the best pseudorandom generators for this class of functions required seed-length $2^{O(s)} \cdot \log(n)$.Thu, 16 Feb 2017 18:27:26 +0200https://eccc.weizmann.ac.il/report/2017/025