ECCC - Reportshttps://example.com/Latest Reports published at https://eccc.weizmann.ac.ilen-usThu, 22 Feb 2018 13:44:54 +0200TR18-038 | Tight Bounds using Hankel Matrix for Arithmetic Circuits with Unique Parse Trees |
Guillaume Lagarde,
Nathanael Fijalkow,
Pierre Ohlmann
https://eccc.weizmann.ac.il/report/2018/038This paper studies lower bounds for arithmetic circuits computing (non-commutative) polynomials. Our conceptual contribution is an exact correspondence between circuits and weighted automata: algebraic branching programs are captured by weighted automata over words, and circuits with unique parse trees by weighted automata over trees.
The key notion for understanding the minimisation question of weighted automata is the Hankel matrix: the rank of the Hankel matrix of a word or tree series is exactly the size of the smallest weighted automaton recognising this series. For automata over words, the correspondence we establish allows us to rephrase Nisan's celebrated tight bounds for algebraic branching programs. We extend this result by considering automata over trees and obtain the first tight bounds for all circuits with unique parse trees.Thu, 22 Feb 2018 13:44:54 +0200https://eccc.weizmann.ac.il/report/2018/038TR18-037 | Inapproximability of Matrix $p \rightarrow q$ Norms |
Vijay Bhattiprolu,
Mrinalkanti Ghosh,
Venkatesan Guruswami,
Euiwoong Lee,
Madhur Tulsiani
https://eccc.weizmann.ac.il/report/2018/037We study the problem of computing the $p\rightarrow q$ norm of a matrix $A \in R^{m \times n}$, defined as \[ \|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac{\|Ax\|_q}{\|x\|_p} \] This problem generalizes the spectral norm of a matrix ($p=q=2$) and the Grothendieck problem ($p=\infty$, $q=1$), and has been widely studied in various regimes. When $p \geq q$, the problem exhibits a dichotomy: constant factor approximation algorithms are known if $2 \in [q,p]$, and the problem is hard to approximate within almost polynomial factors when $2 \notin [q,p]$.
The regime when $p$ is less than $q$, known as hypercontractive norms, is particularly significant for various applications but much less well understood. The case $p = 2$ and $q > 2$ was studied by [Barak et al, STOC'12] who gave sub-exponential algorithms for a promise version of the problem (which captures small-set expansion) and also proved hardness of approximation results based on the Exponential Time Hypothesis. However, no NP-hardness of approximation is known for these problems for any $p < q$.
We study the hardness of approximating matrix norms in both the above cases and prove the following results:
- We show that for any $1< p < q < \infty$ with $2 \notin [p,q]$, $\|A\|_{p\rightarrow q}$ is hard to approximate within $2^{O(\log^{1-\epsilon}\!n)}$ assuming $NP \not\subseteq BPTIME(2^{\log^{O(1)}\!n})$. This suggests that, similar to the case of $p \geq q$, the hypercontractive setting may be qualitatively different when $2$ does not lie between $p$ and $q$.
- For all $p \geq q$ with $2 \in [q,p]$, we show $\|A\|_{p\rightarrow q}$ is hard to approximate within any factor smaller than $1/(\gamma_{p^*} \cdot \gamma_q)$, where $\gamma_r$ denotes the $r^{th}$ norm of the standard Gaussian, and $p^*$ is the dual norm of $p$.Wed, 21 Feb 2018 18:03:46 +0200https://eccc.weizmann.ac.il/report/2018/037TR18-036 | Towards blackbox identity testing of log-variate circuits |
Sumanta Ghosh,
Michael A. Forbes,
Nitin Saxena
https://eccc.weizmann.ac.il/report/2018/036Derandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal,Ghosh,Saxena, STOC'18) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few variables, eg.~logarithm in the size $s$.
We give the first poly($s$)-time blackbox identity test for $n=O(\log s)$ variate size-$s$ circuits that have poly($s$)-dimensional partial derivative space; eg.~depth-$3$ diagonal circuits (or $\Sigma\wedge\Sigma^n$). The former model is well-studied (Nisan,Wigderson, FOCS'95) but no poly$(s2^n)$-time identity test was known before us. We introduce the concept of {\em cone-closed} basis isolation and prove its usefulness in studying log-variate circuits. It subsumes the previous notions of rank-concentration studied extensively in the context of ROABP models.Wed, 21 Feb 2018 16:25:04 +0200https://eccc.weizmann.ac.il/report/2018/036TR18-035 | Bootstrapping variables in algebraic circuits |
Sumanta Ghosh,
Manindra Agrawal,
Nitin Saxena
https://eccc.weizmann.ac.il/report/2018/035We show that for the blackbox polynomial identity testing (PIT) problem it suffices to study circuits that depend only on the first extremely few variables. One only need to consider size-$s$ degree-$s$ circuits that depend on the first $\log^{\circ c} s$ variables (where $c$ is a constant and we are composing $c$ logarithms). Thus, hitting-set generator (hsg) manifests a {\em bootstrapping} behavior--- a partial hsg against very few variables can be efficiently grown to a complete hsg.
A boolean analog, or a pseudorandom generator property of this type, is unheard-of.
Our idea is to use the partial hsg and its annihilator polynomial to efficiently bootstrap the hsg exponentially wrt variables. This is repeated $c$ times in an efficient way.
Pushing the envelope further we show that: {\bf (1)} a quadratic-time blackbox PIT for $6913$-variate degree-$s$ size-$s$ polynomials, will lead to a ``near''-complete derandomization of PIT, and {\bf (2)} a blackbox PIT for $n$-variate degree-$s$ size-$s$ circuits in $s^{n^{\delta}}$-time, for $\delta<1/2$, will lead to a ``near''-complete derandomization of PIT (in contrast, $s^n$-time is trivial).
Our second idea is to study depth-$4$ circuits that depend on constantly many variables. We show that a polynomial-time computable, $O(s^{1.49})$-degree hsg for {\em trivariate} depth-$4$ circuits bootstraps to a quasipolynomial time hsg for general poly-degree circuits, and implies a lower bound that is a bit stronger than Kabanets-Impagliazzo (STOC 2003).Wed, 21 Feb 2018 15:50:12 +0200https://eccc.weizmann.ac.il/report/2018/035TR18-034 | On Symmetric Parallel Repetition : Towards Equivalence of MAX-CUT and UG |
Young Kun Ko
https://eccc.weizmann.ac.il/report/2018/034Unique Games Conjecture (UGC), proposed by [Khot02], lies in the center of many inapproximability results. At the heart of UGC lies approximability of MAX-CUT, which is a special instance of Unique Game.[KhotKMO04, MosselOO05] showed that assuming Unique Games Conjecture, it is NP-hard to distinguish between MAX-CUT instance that has a value $1-\epsilon$ vs. $1-\Omega(\sqrt{\epsilon})$. [CharikarMM06] then showed a matching polynomial time algorithm using Semi-Definite Programming. Towards resolving UGC, it has been long conjectured that inapproximability of MAX-CUT and UGC are equivalent. Assuming the equivalence, it suffices to exhibit lower bounds on MAX-CUT towards resolving UGC.
Towards showing the equivalence of the hardness of MAX-CUT and UGC, we initiate the study of symmetric parallel repetition, which is parallel repetition without coordinate. In particular, we show that symmetric parallel repetition beats strong parallel repetition in certain regimes, that is the value decays $(1-\epsilon^c)^{\Omega(r)}$ with $c < 2$, exhibiting the first separation between symmetric parallel repetition and usual parallel repetition. This is in sharp contrast to the usual parallel repetition as shown by [Holenstein07, Rao08a] where the best upper bound known for the value of the game $\mathcal{G}^{\otimes r}$ is $(1-\epsilon^2 / 2)^{\Omega(r)}$ for projection games. The counterexample shown by [Raz08] gives a lower bound of $\val(\mathcal{G}^{\otimes r}) \geq (1-\epsilon^2)^{O(r)}$ for $r = \Omega(n^2)$ where $n$ is the size of the graph. This also implies that the odd cycle game is not a counterexample for symmetric parallel repetition.
The main technical tool is the analysis of the Birthday Repetition in high intersection regime first introduced in [AIM14] subsequently improved in [MR16]. From a technical perspective we show that (a) if the set size is slightly larger than $\sqrt{n}$, then the value decays strong exponentially (i.e. $(1-\epsilon)^{\tilde{\Omega}(r)}$) in the expected intersection size; (b) if the set becomes large as in the whole vertex set, then the value decays strong exponentially in the number of edges that are checked by the verifier. Then we use prove a translation lemma to translate these technical results to corollaries in symmetric parallel repetition.
This exhibits a dichotomy between the usual parallel repetition and symmetric parallel repetition. In particular, it shows that the avenue of attack for showing the equivalence between the hardness of MAX-CUT and the Unique Games Conjecture using some model of repetition is still open.Sun, 18 Feb 2018 07:41:11 +0200https://eccc.weizmann.ac.il/report/2018/034TR18-033 | The Communication Complexity of Private Simultaneous Messages, Revisited |
Benny Applebaum,
Thomas Holenstein,
Manoj Mishra,
Ofer Shayevitz
https://eccc.weizmann.ac.il/report/2018/033Private Simultaneous Message (PSM) protocols were introduced by Feige, Kilian and Naor (STOC '94) as a minimal non-interactive model for information-theoretic three-party secure computation. While it is known that every function $f:\{0,1\}^k\times \{0,1\}^k \rightarrow \{0,1\}$ admits a PSM protocol with exponential communication of $2^{k/2}$ (Beimel et al., TCC '14), the best known (non-explicit) lower-bound is $3k-O(1)$ bits. To prove this lower-bound, FKN identified a set of simple requirements, showed that any function that satisfies these requirements is subject to the $3k-O(1)$ lower-bound, and proved that a random function is likely to satisfy the requirements.
We revisit the FKN lower-bound and prove the following results:
(Counterexample) We construct a function that satisfies the FKN requirements but has a PSM protocol with communication of $2k+O(1)$ bits, revealing a gap in the FKN proof.
(PSM lower-bounds) We show that, by imposing additional requirements, the FKN argument can be fixed leading to a $3k-O(\log k)$ lower-bound for a random function. We also get a similar lower-bound for a function that can be computed by a polynomial-size circuit (or even polynomial-time Turing machine under standard complexity-theoretic assumptions). This yields the first non-trivial lower-bound for an explicit Boolean function partially resolving an open problem of Data, Prabhakaran and Prabhakaran (Crypto '14, IEEE Information Theory '16). We further extend these results to the setting of imperfect PSM protocols which may have small correctness or privacy error.
(CDS lower-bounds) We show that the original FKN argument applies (as is) to some weak form of PSM protocols which are strongly related to the setting of Conditional Disclosure of Secrets (CDS). This connection yields a simple combinatorial criterion for establishing linear $\Omega(k)$-bit CDS lower-bounds. As a corollary, we settle the complexity of the Inner Product predicate resolving an open problem of Gay, Kerenidis, and Wee (Crypto '15). Fri, 16 Feb 2018 10:23:18 +0200https://eccc.weizmann.ac.il/report/2018/033TR18-032 | Explicit Binary Tree Codes with Polylogarithmic Size Alphabet |
Gil Cohen,
Leonard Schulman,
Bernhard Haeupler
https://eccc.weizmann.ac.il/report/2018/032This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size.
For every constant $\delta < 1$ we give an explicit binary tree code with distance $\delta$ and alphabet size $(\log{n})^{O(1)}$, where $n$ is the depth of the tree. This is the first improvement over a two-decade-old construction that has an exponentially larger alphabet of size $n^{O(1)}$.
As part of the analysis, we prove a bound on the number of positive integer roots a real polynomial can have in terms of its sparsity with respect to the Newton basis - a result of independent interest.
Thu, 15 Feb 2018 23:24:41 +0200https://eccc.weizmann.ac.il/report/2018/032TR18-031 | On the Communication Complexity of Key-Agreement Protocols |
Iftach Haitner,
Noam Mazor,
Rotem Oshman,
Omer Reingold,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2018/031Key-agreement protocols whose security is proven in the random oracle model are an important alternative to the more common public-key based key-agreement protocols. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but they are limited in the number of queries they can make to it. Unfortunately, as shown by Impagliazzo and Rudich [STOC '89] and Barak and Mahmoody [Crypto '09], such protocols can only guarantee limited secrecy: the key of any $\ell$-query protocol can be revealed by an $O(\ell^2)$-query adversary. This quadratic gap between the query complexity of the honest parties and the eavesdropper matches the gap obtained by the Merkle's Puzzles protocol [CACM '78].
In this work we tackle a new aspect of key-agreement protocols in the random oracle model: their communication complexity. In Merkle's Puzzles, to obtain secrecy against an eavesdropper that makes roughly $\ell^2$ queries, the honest parties need to exchange $\Omega(\ell)$ bits. We show that for protocols with certain natural properties, ones that Merkle's Puzzle has, such high communication is unavoidable. Specifically, this is the case if the honest parties' queries are uniformly random, or alternatively if the protocol uses non-adaptive queries and has only two rounds. Our proof for the first setting uses a novel reduction from random-oracle protocols to the set-disjointness problem in two-party communication complexity, which is known to have high communication cost. For the second setting we prove the lower bound directly, using information-theoretic arguments.
Understanding the communication complexity of protocols whose security is proven in the random-oracle model is an important question in the study of practical protocols. Our results and proof techniques are a first step in this direction.Thu, 15 Feb 2018 19:14:19 +0200https://eccc.weizmann.ac.il/report/2018/031TR18-030 | NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits |
Shuichi Hirahara,
Igor Carboni Oliveira,
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2018/030The Minimum Circuit Size Problem (MCSP) asks for the size of the smallest boolean circuit that computes a given truth table. It is a prominent problem in NP that is believed to be hard, but for which no proof of NP-hardness has been found. A significant number of works have demonstrated the central role of this problem and its variations in diverse areas such as cryptography, derandomization, proof complexity, learning theory, and circuit lower bounds.
The NP-hardness of computing the minimum numbers of terms in a DNF formula consistent with a given truth table was proved by W. Masek in 1979. In this work, we make the first progress in showing NP-hardness for more expressive classes of circuits, and establish an analogous result for the MCSP problem for depth-$3$ circuits of the form OR-AND-MOD$_2$. Our techniques extend to an NP-hardness result for MOD$_m$ gates at the bottom layer under inputs from $(\mathbb Z / m \mathbb Z)^n$.Sun, 11 Feb 2018 13:52:54 +0200https://eccc.weizmann.ac.il/report/2018/030TR18-029 | Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs |
Neeraj Kayal,
vineet nair,
Chandan Saha
https://eccc.weizmann.ac.il/report/2018/029Let us call a matrix $X$ as a linear matrix if its entries are affine forms, i.e. degree one polynomials. What is a minimal-sized representation of a given matrix $F$ as a product of linear matrices? Finding such a minimal representation is closely related to finding an optimal way to compute a given polynomial via an algebraic branching program. Here we devise an efficient algorithm for an average-case version of this problem. Specifically, given $w,d,n \in \mathbb{N}$ and blackbox access to the $w^2$ entries of a matrix product $F = X_1 \cdots X_d$ , where each $X_i$ is a $w \times w$ linear matrix over a given finite field $\mathbb{F}_q$, we wish to recover a factorization $F = Y_1 \cdots Y_{d'}$, where every $Y_i$ is also a linear matrix over $\mathbb{F}_q$ (or a small extension of $\mathbb{F}_q$). We show that when the input $F$ is sampled from a distribution defined by choosing random linear matrices $X_1, \ldots, X_d$ over $\mathbb{F}_q$ independently and taking their product and $n \geq 4w^2$ and the characteristic of $\mathbb{F}_q$ is at least $(ndw)^{\Omega(1)}$ then an equivalent factorization $F = Y_1 \cdots Y_d$ can be recovered in (randomized) time $(wdn \log q)^{O(1)}$. We also show that in this situation, if we are instead given a single entry of $F$ rather than its $w^2$ correlated entries then the recovery can be done in (randomized) time $(d^{w^3} n \log q)^{O(1)}$.Fri, 09 Feb 2018 10:11:13 +0200https://eccc.weizmann.ac.il/report/2018/029