ECCC - Reportshttps://example.com/Latest Reports published at https://eccc.weizmann.ac.ilen-usSun, 16 Sep 2018 14:43:58 +0300TR18-162 | A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates |
Swapnam Bajpai,
Vaibhav Krishan,
Deepanshu Kush,
Nutan Limaye,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2018/162We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit $C$ made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to $C$ in significantly better than brute-force time.
Formally, for any constants $d,k$, there is an $\epsilon > 0$ such that the algorithm counts the number of satisfying assignments to a given depth-$d$ circuit $C$ made up of $k$-PTF gates such that $C$ has size at most $n^{1+\epsilon}$. The algorithm runs in time $2^{n-n^{\Omega(\epsilon)}}$.
Before our result, no algorithm for beating brute-force search was known even for a single degree-$2$ PTF (which is a depth-$1$ circuit of linear size).
The main new tool is the use of a learning algorithm for learning degree-$1$ PTFs (or Linear Threshold Functions) using comparison queries due to Kane, Lovett, Moran and Zhang (FOCS 2017). We show that their ideas fit nicely into a memoization approach that yields the #SAT algorithms.Sun, 16 Sep 2018 14:43:58 +0300https://eccc.weizmann.ac.il/report/2018/162TR18-161 | Delegating Computations with (almost) Minimal Time and Space Overhead |
Ron Rothblum,
Justin Holmgren
https://eccc.weizmann.ac.il/report/2018/161The problem of verifiable delegation of computation considers a setting in which a client wishes to outsource an expensive computation to a powerful, but untrusted, server. Since the client does not trust the server, we would like the server to certify the correctness of the result. Delegation has emerged as a central problem in cryptography, with a flurry of recent activity in both theory and practice. In all of these works, the main bottleneck is the overhead incurred by the server, both in time and in space.
Assuming (sub-exponential) LWE, we construct a one-round argument-system for proving the correctness of any time $T$ and space $S$ RAM computation, in which both the verifier and prover are highly efficient. The verifier runs in time $n \cdot polylog(T)$ and space $polylog(T)$, where $n$ is the input length. Assuming $S \geq \max(n,polylog(T))$, the prover runs in time $\tilde{O}(T)$ and space $S + o(S)$, and in many natural cases even $S+polylog(T)$. Our solution uses somewhat homomorphic encryption but, surprisingly, only requires homomorphic evaluation of arithmetic circuits having multiplicative depth (which is a main bottleneck in homomorphic encryption) $\log_2\log(T)+O(1)$.
Prior works based on standard assumptions had a $T^c$ time prover, where $c \geq 3$ (at the very least). As for the space usage, we are unaware of any work, even based on non-standard assumptions, that has space usage $S+polylog(T)$.
Along the way to constructing our delegation scheme, we introduce several technical tools that we believe may be useful for future work.Thu, 13 Sep 2018 16:04:53 +0300https://eccc.weizmann.ac.il/report/2018/161TR18-160 | Cubic Formula Size Lower Bounds Based on Compositions with Majority |
Anna Gal,
Avishay Tal,
Adrian Trejo Nuñez
https://eccc.weizmann.ac.il/report/2018/160We define new functions based on the Andreev function and prove that they require $n^{3}/polylog(n)$ formula size to compute. The functions we consider are generalizations of the Andreev function using compositions with the majority function. Our arguments apply to composing a hard function with any function that agrees with the majority function (or its negation) on the middle slices of the Boolean cube, as well as iterated compositions of such functions.
As a consequence, we obtain $n^{3}/polylog(n)$ lower bounds on the (non-monotone) formula size of an explicit monotone function by combining the monotone address function with the majority function. To the best of our knowledge, previously, super-quadratic formula size lower bounds for explicit functions have been obtained only for non-monotone functions.Wed, 12 Sep 2018 09:30:58 +0300https://eccc.weizmann.ac.il/report/2018/160TR18-159 | Expander-Based Cryptography Meets Natural Proofs |
Roei Tell,
Rahul Santhanam,
Igor Carboni Oliveira
https://eccc.weizmann.ac.il/report/2018/159We introduce new forms of attack on expander-based cryptography, and in particular on Goldreich's pseudorandom generator and one-way function. Our attacks exploit low circuit complexity of the underlying expander's neighbor function and/or of the local predicate. Our two key conceptual contributions are:
* The security of Goldreich's PRG and OWF hinges, at least in some settings, on the circuit complexity of the underlying expander's neighbor function and of the local predicate. This sharply diverges from previous works, which focused on the expansion properties of the underlying expander and on the algebraic properties of the predicate.
* We uncover new connections between long-standing open problems: Specifically, we tie the security of Goldreich's PRG and OWF both to the existence of unbalanced lossless expanders with low-complexity neighbor function, and to limitations on circuit lower bounds (i.e., natural proofs).
We prove two types of technical results that support the above conceptual messages. First, we unconditionally break Goldreich's PRG when instantiated with a specific expander (whose existence we prove), for a class of predicates that match the parameters of the currently-best ``hard'' candidates, in the regime of quasi-polynomial stretch. Secondly, conditioned on the existence of expanders whose neighbor functions have extremely low circuit complexity, we present attacks on Goldreich's generator in the regime of polynomial stretch. As one corollary, conditioned on the existence of the foregoing expanders, we show that either the parameters of natural properties for several constant-depth circuit classes cannot be improved, even mildly; or Goldreich's generator is insecure in the regime of a large polynomial stretch, regardless of the predicate used.
In particular, our results further motivate the investigation of average-case lower bounds against DNF-XOR circuits of exponential size, and of the parameters that can be achieved by affine/local unbalanced expanders.Wed, 12 Sep 2018 00:03:10 +0300https://eccc.weizmann.ac.il/report/2018/159TR18-158 | Hardness magnification near state-of-the-art lower bounds |
Igor Carboni Oliveira,
Ján Pich,
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2018/158This work continues the development of hardness magnification. The latter proposes a strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be successful.
We consider gap versions of the meta-computational problems MKtP and MCSP, where one needs to distinguish instances (strings or truth-tables) of complexity $\leq s_1(N)$ from instances of complexity $\geq s_2(N)$, and $N = 2^n$ denotes the input length. In MCSP, complexity is measured by circuit size, while in MKtP one considers Levin's notion of time-bounded Kolmogorov complexity. (In our results, the parameters $s_1(N)$ and $s_2(N)$ are asymptotically quite close, and the problems almost coincide with their standard formulations without a gap.) We establish that for Gap-MKtP$[s_1,s_2]$ and Gap-MCSP$[s_1,s_2]$, a marginal improvement over the state-of-the-art in unconditional lower bounds in a variety of computational models would imply explicit super-polynomial lower bounds.
Theorem. There exists a universal constant $c \geq 1$ for which the following hold. If there exists $\varepsilon > 0$ such that for every small enough $\beta > 0$
1. Gap-MCSP$[2^{\beta n}/c n, 2^{\beta n}] \notin$Circuit$[N^{1 + \varepsilon}]$, then NP is not contained in Circuit[poly].
2. Gap-MKtP$[2^{\beta n},\, 2^{\beta n } + cn] \notin$TC$^0[N^{1 + \varepsilon}]$, then EXP is not contained in TC$^0$[poly].
3. Gap-MKtP$[2^{\beta n},\, 2^{\beta n} + cn] \notin B_2$-Formula$[N^{2 + \varepsilon}]$, then EXP is not contained in Formula[poly].
4. Gap-MKtP$[2^{\beta n},\, 2^{\beta n} + cn] \notin U_2$-Formula$[N^{3 + \varepsilon}]$, then EXP is not contained in Formula[poly].
5. Gap-MKtP$[2^{\beta n},\, 2^{\beta n} + cn] \notin$BP$[N^{2 + \varepsilon}]$, then EXP is not contained in BP[poly].
6. Gap-MKtP$[2^{\beta n},\, 2^{\beta n} + cn] \notin$(AC$^0[6])[N^{1 + \varepsilon}]$, then EXP is not contained in AC$^0[6]$.
These results are complemented by lower bounds for Gap-MCSP and Gap-MKtP against different models. For instance, the lower bound assumed in (1) holds for $U_2$-formulas of near-quadratic size, and lower bounds similar to (3)-(5) hold for various regimes of parameters.
Going beyond the standard boolean devices, we identify a natural computational model under which the hardness magnification threshold for Gap-MKtP lies below existing lower bounds: $U_2$-formulas that can compute parity functions at the leaves (instead of just literals). As a consequence, if one managed to adapt the existing lower bound techniques against such formulas to work with Gap-MKtP, then EXP is not contained in NC$^1$ would follow via hardness magnification.Tue, 11 Sep 2018 17:48:03 +0300https://eccc.weizmann.ac.il/report/2018/158TR18-157 | The Coin Problem in Constant Depth: Sample Complexity and Parity gates |
Nutan Limaye,
Karteek Sreenivasiah,
Srikanth Srinivasan,
Utkarsh Tripathi,
S Venkitesh
https://eccc.weizmann.ac.il/report/2018/157The $\delta$-Coin Problem is the computational problem of distinguishing between coins that are heads with probability $(1+\delta)/2$ or $(1-\delta)/2,$ where $\delta$ is a parameter that is going to $0$. We study the complexity of this problem in the model of constant-depth Boolean circuits and prove the following results.
1. Upper bounds. For any constant $d\geq 2$, we show that there are explicit monotone $\mathrm{AC}^0$ formulas (i.e. made up of AND and OR gates only) solving the $\delta$-coin problem that have depth $d$, size $\exp(O(d(1/\delta)^{1/(d-1)}))$, and sample complexity (i.e. number of inputs) $\mathrm{poly}(1/\delta).$ This matches previous upper bounds of O'Donnell and Wimmer (ICALP 2007) and Amano (ICALP 2009) in terms of size (which is optimal) and improves the sample complexity from $\exp(O(d(1/\delta)^{1/(d-1)}))$ to $\mathrm{poly}(1/\delta)$.
2. Lower bounds. We show that the above upper bounds are nearly tight (in terms of size) even for the significantly stronger model of $\mathrm{AC}^0[\oplus]$ formulas (which are also allowed NOT and Parity gates): formally, we show that any $\mathrm{AC}^0[\oplus]$ formula solving the $\delta$-coin problem must have size $\exp(\Omega(d(1/\delta)^{1/(d-1)})).$ This strengthens a result of Cohen, Ganor and Raz (APPROX-RANDOM 2014), who prove a similar result for $\mathrm{AC}^0$, and a result of Shaltiel and Viola (SICOMP 2010), which implies a superpolynomially weaker (though still exponential) lower bound.
The above yields the first class of explicit functions where we have nearly (up to a polynomial factor) matching upper and lower bounds for the class of $\mathrm{AC}^0[\oplus]$ formulas. In particular, this yields the first Fixed-depth Size-Hierarchy Theorem for the uniform version of this class: our results imply that for any fixed $d$, the class $\mathcal{C}_{d,k}$ of functions that have uniform $\mathrm{AC}^0[\oplus]$ formulas of depth $d$ and size $n^k$ form an infinite hierarchy.
The proofs use many ideas. The upper bound is a derandomization involving a novel use of Janson's inequality (from probabilistic combinatorics) in this context and classical combinatorial designs. The lower bound is a modification of the Razborov-Smolensky polynomial method; in particular, we prove an optimal (up to a constant factor) degree lower bound for multivariate polynomials over $\mathbb{F}_2$ solving the $\delta$-coin problem, which may be independently interesting.Mon, 10 Sep 2018 19:21:37 +0300https://eccc.weizmann.ac.il/report/2018/157TR18-156 | Quantum algorithms and approximating polynomials for composed functions with shared inputs |
Mark Bun,
Robin Kothari,
Justin Thaler
https://eccc.weizmann.ac.il/report/2018/156We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be a Boolean function and consider a function $F$ obtained by applying $f$ to conjunctions of possibly overlapping subsets of $n$ variables. If $f$ has quantum query complexity $Q(f)$, we give an algorithm for evaluating $F$ using $\tilde{O}(\sqrt{Q(f) \cdot n})$ quantum queries. This improves on the bound of $O(Q(f) \cdot \sqrt{n})$ that follows by treating each conjunction independently, and is tight for worst-case choices of $f$. Using completely different techniques, we prove a similar tight composition theorem for the approximate degree of $f$.
By recursively applying our composition theorems, we obtain a nearly optimal $\tilde{O}(n^{1-2^{-d}})$ upper bound on the quantum query complexity and approximate degree of linear-size depth-$d$ AC$^0$ circuits. As a consequence, such circuits can be PAC learned in subexponential time, even in the challenging agnostic setting. Prior to our work, a subexponential-time algorithm was not known even for linear-size depth-3 AC$^0$ circuits. We also show that any substantially faster learning algorithm will require fundamentally new techniques.Sun, 09 Sep 2018 16:58:35 +0300https://eccc.weizmann.ac.il/report/2018/156TR18-155 | Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates |
Eshan Chattopadhyay,
Avishay Tal,
Shachar Lovett,
Pooya Hatami
https://eccc.weizmann.ac.il/report/2018/155A recent work of Chattopadhyay et al. (CCC 2018) introduced a new framework for the design of pseudorandom generators for Boolean functions. It works under the assumption that the Fourier tails of the Boolean functions are uniformly bounded for all levels by an exponential function. In this work, we design an alternative pseudorandom generator that only requires bounds on the second level of the Fourier tails. It is based on a derandomization of the work of Raz and Tal (ECCC 2018) who used the above framework to obtain an oracle separation between BQP and PH.
As an application, we give a concrete conjecture for bounds on the second level of the Fourier tails for low degree polynomials over the finite field $\mathbb{F}_2$. If true, it would imply an efficient pseudorandom generator for $\text{AC}^0[\oplus]$, a well-known open problem in complexity theory. As a stepping stone towards resolving this conjecture, we prove such bounds for the first level of the Fourier tails.Sat, 08 Sep 2018 15:40:48 +0300https://eccc.weizmann.ac.il/report/2018/155TR18-154 | Lower Bounds for Circuits of Bounded Negation Width |
Stasys Jukna,
Andrzej Lingas
https://eccc.weizmann.ac.il/report/2018/154We consider Boolean circuits over $\{\lor,\land,\neg\}$ with negations applied only to input variables. To measure the ``amount of negation'' in such circuits, we introduce the concept of their ``negation width.'' In particular, a circuit computing a monotone Boolean function $f(x_1,\ldots,x_n)$ has negation width $w$ if no nonzero term produced (purely syntactically) by the circuit contains more than $w$ distinct negated variables. Circuits of negation width $w=0$ are equivalent to monotone circuits, while those of negation width $w=n$ have no restrictions. Our motivation is that already circuits of moderate negation width $w=n^{\epsilon}$ for an arbitrarily small constant $\epsilon>0$ can be even exponentially stronger than monotone circuits.
We show that the size of any circuit of negation width $w$ computing $f$ is roughly at least the minimum size of a monotone circuit computing $f$ divided by $K=\min\{w^m,m^w\}$, where $m$ is the maximum length of a prime implicant of $f$. We also show that the depth of any circuit of negation width $w$ computing $f$ is roughly at least the minimum depth of a monotone circuit computing $f$ minus $\log K$. Finally, we show that formulas of bounded negation width can be balanced without increasing their negation width.Fri, 07 Sep 2018 16:55:54 +0300https://eccc.weizmann.ac.il/report/2018/154TR18-153 | New Bounds for Energy Complexity of Boolean Functions |
Krishnamoorthy Dinesh,
Jayalal Sarma,
Samir Otiv
https://eccc.weizmann.ac.il/report/2018/153For a Boolean function $f:\{0,1\}^n \to \{0,1\}$ computed by a circuit $C$ over a finite basis $\cal{B}$, the energy complexity of $C$ (denoted by $\mathbf{EC}_{{\cal B}}(C)$) is the maximum over all inputs $\{0,1\}^n$ the numbers of gates of the circuit $C$ (excluding the inputs) that output a one. Energy Complexity of a Boolean function over a finite basis ${\cal B}$ denoted by $\mathbf{EC}_{\cal B}(f):= \min_C \mathbf{EC}_{{\cal B}}(C)$ where $C$ is a circuit over ${\cal B}$ computing $f$.
We study the case when ${\cal B} = \{\land_2, \lor_2, \lnot\}$, the standard Boolean basis. It is known that any Boolean function can be computed by a circuit (with potentially large size) with an energy of at most $3n(1+\epsilon(n))$ for a small $ \epsilon(n)$(which we observe is improvable to $3n-1$). We show several new results and connections between energy complexity and other well-studied parameters of Boolean functions.
1. For all Boolean functions $f$, $\mathbf{EC}(f) \le O({DT}(f)^3)$ where ${DT}(f)$ is the optimal decision tree depth of $f$.
2. We define a parameter {positive sensitivity} (denoted by $\mathbf{psens}$), a quantity that is smaller than sensitivity and defined in a similar way, and show that for any Boolean circuit $C$ computing a Boolean function $f$, $ \mathbf{EC}(C) \ge \mathbf{psens}(f)/3$.
3. For a monotone function $f$, we show that $\mathbf{EC}(f) = \Omega(\mathbf{KW}^+(f))$ where $\mathbf{KW}^+(f)$ is the cost of monotone Karchmer-Wigderson game of $f$.
4. Restricting the above notion of energy complexity to Boolean formulas, we show $\mathbf{EC}(F) = \Omega\left (\sqrt{L(F)}-depth(F)\right )$ where $L(F)$ is the size and $depth(F)$ is the depth of a formula $F$.
Sun, 02 Sep 2018 07:38:07 +0300https://eccc.weizmann.ac.il/report/2018/153