ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usSun, 24 Mar 2019 09:12:18 +0200TR19-043 | Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity |
Toniann Pitassi,
Morgan Shirley,
Thomas Watson
https://eccc.weizmann.ac.il/report/2019/043We study the Boolean Hierarchy in the context of two-party communication complexity, as well as the analogous hierarchy defined with one-sided error randomness instead of nondeterminism. Our results provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove a query-to-communication lifting theorem for all levels of the Boolean Hierarchy and use it to resolve an open problem stated in the paper by Halstenberg and Reischuk (CCC 1988) which initiated this topic.Sun, 24 Mar 2019 09:12:18 +0200https://eccc.weizmann.ac.il/report/2019/043TR19-042 | Determinant equivalence test over finite fields and over $\mathbf{Q}$ |
Ankit Garg,
Nikhil Gupta,
Neeraj Kayal,
Chandan Saha
https://eccc.weizmann.ac.il/report/2019/042The determinant polynomial $Det_n(\mathbf{x})$ of degree $n$ is the determinant of a $n \times n$ matrix of formal variables. A polynomial $f$ is equivalent to $Det_n$ over a field $\mathbf{F}$ if there exists a $A \in GL(n^2,\mathbf{F})$ such that $f = Det_n(A \cdot \mathbf{x})$. Determinant equivalence test over $\mathbf{F}$ is the following algorithmic task: Given black-box access to a $f \in \mathbf{F}[\mathbf{x}]$, check if $f$ is equivalent to $Det_n$ over $\mathbf{F}$, and if so then output a transformation matrix $A \in GL(n^2,\mathbf{F})$. In Kayal (2012), a randomized polynomial time determinant equivalence test was given over $\mathbf{C}$. But, to our knowledge, the complexity of the problem over finite fields and over rationals was not well understood.
In this work, we give a randomized $poly(n,\log |\mathbf{F}|)$ time determinant equivalence test over finite fields $\mathbf{F}$ (under mild restrictions on the characteristic and size of $\mathbf{F}$). Over rationals, we give an efficient randomized reduction from factoring square-free integers to determinant equivalence test for quadratic forms (i.e. the $n=2$ case), assuming GRH. This shows that designing a polynomial-time determinant equivalence test over rationals is a challenging task. Nevertheless, we show that determinant equivalence test over rationals is decidable: For bounded $n$, there is a randomized polynomial-time determinant equivalence test over rationals with access to an oracle for integer factoring. Moreover, for any $n$, there is a randomized polynomial-time algorithm that takes input black-box access to a rational polynomial $f$ and if $f$ is equivalent to $Det_n$ over rationals then it returns a $A \in GL(n^2,\mathbf{L})$ such that $f = Det_n(A \cdot \mathbf{x})$, where $\mathbf{L}$ is an extension field of $\mathbf{Q}$ of degree at most $n$.
The above algorithms over finite fields and over rationals are obtained by giving a polynomial-time randomized reduction from determinant equivalence test to another problem, namely the full matrix algebra isomorphism problem. We also show a reduction in the converse direction which is efficient if $n$ is bounded. These reductions, which hold over any $\mathbf{F}$ (under mild restrictions on the characteristic and size of $\mathbf{F}$), establish a close connection between the complexity of the two problems. This then lead to our results via applications of known results on the full algebra isomorphism problem over finite fields and over $\mathbf{Q}$.
Mon, 18 Mar 2019 14:28:35 +0200https://eccc.weizmann.ac.il/report/2019/042TR19-041 | Quantum hardness of learning shallow classical circuits |
Srinivasan Arunachalam,
Alex Bredariol Grilo,
Aarthi Sundaram
https://eccc.weizmann.ac.il/report/2019/041In this paper we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results.
1) Hardness of learning $AC^0$ and $TC^0$ under the uniform distribution. Our first result concerns the concept class $TC^0$ (resp. $AC^0$), the class of constant depth and polynomial-sized circuits with unbounded fan-in majority gates (resp. AND, OR, NOT gates). We show that if there exists no quantum polynomial time (resp. sub-exponential time) algorithm to solve the Learning with Errors (LWE) problem, then there exists no polynomial time quantum learning algorithm for $TC^0$ (resp. $AC^0$) under the uniform distribution (even with access to quantum membership queries). The main technique in this result uses explicit pseudo-random generators that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution.
2) Hardness of learning $TC^0_2$ in the PAC setting. Our second result shows that if there exists no quantum polynomial time algorithm for the LWE problem, then there exists no polynomial time quantum PAC learning algorithm for the class $TC^0_2$, i.e., depth-$2$ $TC^0$ circuits. The main technique in this result is to establish a connection between the quantum security of public-key cryptosystems and the learnability of a concept class that consists of decryption functions of the cryptosystem.
This gives a strong conditional negative answer to one of the "Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson, who asked if $AC^0$ and $TC^0$ can be PAC-learned in quantum polynomial time.Sun, 17 Mar 2019 09:55:06 +0200https://eccc.weizmann.ac.il/report/2019/041TR19-040 | The Complexity of Finding {$S$}-factors in Regular Graphs |
Sanjana Kolisetty,
Linh Le,
Ilya Volkovich,
Mihalis Yannakakis
https://eccc.weizmann.ac.il/report/2019/040A graph $G$ has an \emph{$S$-factor} if there exists a spanning subgraph $F$ of $G$ such that for all $v \in V: \deg_F(v) \in S$.
The simplest example of such factor is a $1$-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational complexity of finding $S$-factors in regular graphs.
Our techniques combine some classical as well as recent tools from graph theory.Tue, 12 Mar 2019 19:07:28 +0200https://eccc.weizmann.ac.il/report/2019/040TR19-039 | Planarity, Exclusivity, and Unambiguity |
Eric Allender,
Archit Chauhan,
Samir Datta,
Anish Mukherjee
https://eccc.weizmann.ac.il/report/2019/039We provide new upper bounds on the complexity of the s-t-connectivity problem in planar graphs, thereby providing additional evidence that this problem is not complete for NL. This also yields a new upper bound on the complexity of computing edit distance. Building on these techniques, we provide new upper bounds on the complexity of several other computational problems on planar graphs. All of these problems are shown to be solvable in logarithmic time on a concurrent-read exclusive-write (CREW) PRAM. The new upper bounds are provided by making use of a known characterization of CREW algorithms in terms of "unambiguous" AC$^1$ circuits. This seems to be the first occasion where this characterization has been used in order to provide new upper bounds on natural problems.Tue, 12 Mar 2019 06:11:48 +0200https://eccc.weizmann.ac.il/report/2019/039TR19-038 | Statistical Difference Beyond the Polarizing Regime |
Itay Berman,
Akshay Degwekar,
Ron D. Rothblum,
Prashant Nalini Vasudevan
https://eccc.weizmann.ac.il/report/2019/038The polarization lemma for statistical distance ($\mathrm{SD}$), due to Sahai and Vadhan (JACM, 2003), is an efficient transformation taking as input a pair of circuits $(C_0,C_1)$ and an integer $k$ and outputting a new pair of circuits $(D_0,D_1)$ such that if $\mathrm{SD}(C_0,C_1)\geq\alpha$ then $\mathrm{SD}(D_0,D_1) \geq 1-2^{-k}$ and if $\mathrm{SD}(C_0,C_1) \leq \beta$ then $\mathrm{SD}(D_0,D_1) \leq 2^{-k}$. The polarization lemma is known to hold for any constant values $\beta < \alpha^2$, but extending the lemma to the regime in which $\alpha^2 \leq \beta < \alpha$ has remained elusive. The focus of this work is in studying the latter regime of parameters. Our main results are:
1. Polarization lemmas for different notions of distance, such as Triangular Discrimination ($\mathrm{TD}$) and Jensen-Shannon Divergence ($\mathrm{JS}$), which enable polarization for some problems where the statistical distance satisfies $\alpha^2 < \beta < \alpha$. We also derive a polarization lemma for statistical distance with any inverse-polynomially small gap between $\alpha^2$ and $\beta$ (rather than a constant).
2. The average-case hardness of the statistical difference problem (i.e., determining whether the statistical distance between two given circuits is at least $\alpha$ or at most $\beta$), for any values of $\beta < \alpha$, implies the existence of one-way functions. Such a result was previously only known for $\beta < \alpha^2$.
3. A (direct) constant-round interactive proof for estimating the statistical distance between any two distributions (up to any inverse polynomial error) given circuits that generate them.Sun, 10 Mar 2019 10:50:14 +0200https://eccc.weizmann.ac.il/report/2019/038TR19-037 | Closure of VP under taking factors: a short and simple proof |
Mrinal Kumar,
Chi-Ning Chou,
Noam Solomon
https://eccc.weizmann.ac.il/report/2019/037In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an n variate degree $d$ polynomial f can be computed by an arithmetic circuit of size s, then each of its factors can be computed by an arithmetic circuit of size at most poly(s, n, d).
However, unlike Kaltofen's argument, our proof does not directly give an efficient algorithm for computing the circuits for the factors of f.
Wed, 06 Mar 2019 07:52:21 +0200https://eccc.weizmann.ac.il/report/2019/037TR19-036 | On the complexity of computing a random Boolean function over the reals |
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2019/036We say that a first-order formula $A(x_1,\dots,x_n)$ over $\mathbb{R}$ defines a Boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, if for every $x_1,\dots,x_n\in\{0,1\}$, $A(x_1,\dots,x_n)$ is true iff $f(x_1,\dots,x_n)=1$. We show that:
(i) every $f$ can be defined by a formula of size $O(n)$,
(ii) if $A$ is required to have at most $k\geq 1$ quantifier alternations, there exists an $f$ which requires a formula of size $2^{\Omega(n/k)}$.
The latter result implies several previously known as well as some new lower bounds in computational complexity. We note that (i) holds over any field of characteristic zero, and (ii) holds for any real closed or algebraically closed field. Tue, 05 Mar 2019 16:26:34 +0200https://eccc.weizmann.ac.il/report/2019/036TR19-035 | PIT for depth-4 circuits and Sylvester-Gallai theorem for polynomials |
Alexey Milovanov
https://eccc.weizmann.ac.il/report/2019/035
This text is a development of a preprint of Ankit Gupta.
We present an approach for devising a deterministic polynomial time whitekbox identity testing (PIT) algorithm for depth-$4$ circuits with bounded top fanin.
This approach is similar to Kayal-Saraf approach for depth-$3$ circuits. Kayal and Saraf based their algorithm on Sylvester-Gallai-type theorem about linear polynomials. We show how it is possible to generalize this approach to depth-$4$ circuits. However we failed to implement this plan completely. We succeeded to construct a polynomial time deterministic algorithm for depth-$4$ circuits with bounded top fanin and its correctness requires a hypothesis. Also we present a polynomial-time (unconditional) algorithm for some subclass of depth-$4$ circuits with bounded top fanin.Tue, 05 Mar 2019 16:25:03 +0200https://eccc.weizmann.ac.il/report/2019/035TR19-034 | On $\epsilon$-sensitive monotone computations |
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2019/034We show that strong-enough lower bounds on monotone arithmetic circuits or the non-negative rank of a matrix imply unconditional lower bounds in arithmetic or Boolean circuit complexity. First, we show that if a polynomial $f\in {\mathbb {R}}[x_1,\dots, x_n]$ of degree $d$ has an arithmetic circuit of size $s$ then $(x_1+\dots+x_n+1)^d+\epsilon f$ has a monotone arithmetic circuit of size $O(sd^2+n\log n)$, for some $\epsilon>0$. Second, if $f:\{0,1\}^n\rightarrow \{0,1\}$ is a Boolean function, we associate with $f$ an explicit exponential-size matrix $M(f)$ such that the Boolean circuit size of $f$ is at least $\Omega(\min_{\epsilon >0}(\hbox{rk}_+(M(f)-\epsilon J))- 2n)$, where $J$ is the all-ones matrix and $\hbox{rk}_+$ denotes the non-negative rank of a matrix. In fact, the quantity $\min_{\epsilon >0}(\hbox{rk}_+(M(f)-\epsilon J))$ characterizes how hard is it to distinguish rejecting and accepting inputs of $f$ by means of a linear program.
Finally, we introduce a proof system resembling the Boolean monotone calculus and show that similar $\epsilon$-sensitive lower bounds on monotone arithmetic circuits imply lower bounds on proof-size in the system. Tue, 05 Mar 2019 15:06:08 +0200https://eccc.weizmann.ac.il/report/2019/034