ECCC - Reportshttps://example.com/Latest Reports published at https://eccc.weizmann.ac.ilen-usSun, 24 Jun 2018 17:17:21 +0300TR18-120 | The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard |
Alexandros Hollender,
Paul Goldberg
https://eccc.weizmann.ac.il/report/2018/120The complexity class PPAD is usually defined in terms of the END-OF-LINE problem, in which we are given a concise representation of a large directed graph having indegree and outdegree at most 1, and a known source, and we seek some other degree-1 vertex. We show that variants where we are given multiple sources and seek one solution or multiple solutions are PPAD-complete. Our proof also shows that a multiple source SINK problem where we look for multiple sinks instead of one is equivalent to SINK (i.e. PPADS-complete). Using our result, we provide a full proof of PPAD-completeness of IMBALANCE. Finally, we use these results together with earlier work on the 2D-Brouwer problem to investigate the complexity of a new total search problem inspired by the mutilated chessboard tiling puzzle.Sun, 24 Jun 2018 17:17:21 +0300https://eccc.weizmann.ac.il/report/2018/120TR18-119 | A Tight Lower Bound for Entropy Flattening |
YiHsiu Chen,
Mika G\"o{\"o}s,
Salil Vadhan,
Jiapeng Zhang
https://eccc.weizmann.ac.il/report/2018/119We study \emph{entropy flattening}: Given a circuit $\mathcal{C}_X$ implicitly describing an $n$-bit source $X$ (namely, $X$ is the output of $\mathcal{C}_X$ on a uniform random input), construct another circuit $\mathcal{C}_Y$ describing a source $Y$ such that (1) source $Y$ is nearly \emph{flat} (uniform on its support), and (2) the Shannon entropy of $Y$ is monotonically related to that of $X$. The standard solution is to have $\mathcal{C}_Y$ evaluate $\mathcal{C}_X$ altogether $\Theta(n^2)$ times on independent inputs and concatenate the results (correctness follows from the asymptotic equipartition property). In this paper, we show that this is optimal among \emph{black-box} constructions: Any circuit $\mathcal{C}_Y$ for entropy flattening that repeatedly queries $\mathcal{C}_X$ as an oracle requires $\Omega(n^2)$ queries.
Entropy flattening is a component used in the constructions of pseudorandom generators and other cryptographic primitives from one-way functions. It is also used in reductions between problems complete for statistical zero-knowledge. The $\Theta(n^2)$ query complexity is often the main efficiency bottleneck. Our lower bound can be viewed as a step towards proving that the current best construction of pseudorandom generator from arbitrary one-way functions by Vadhan and Zheng (STOC 2012) has optimal efficiency.Sun, 24 Jun 2018 17:14:35 +0300https://eccc.weizmann.ac.il/report/2018/119TR18-118 | Hardness of improper one-sided learning of conjunctions for all uniformly falsifiable CSPs |
Alexander Durgin,
Brendan Juba
https://eccc.weizmann.ac.il/report/2018/118We consider several closely related variants of PAC-learning in which false-positive and false-negative errors are treated differently. In these models we seek to guarantee a given, low rate of false-positive errors and as few false-negative errors as possible given that we meet the false-positive constraint. Bshouty and Burroughs first observed that learning conjunctions in such models would enable PAC-learning of DNF in the usual distribution-free model; in turn, results of Daniely and Shalev-Shwartz establish that learning of DNF would imply algorithms for refuting random k-SAT using far fewer constraints than believed possible. Such algorithms would violate a slight strengthening of Feige's R3SAT assumption, and would violate the RCSP hypothesis of Barak et al. We show here that actually, an algorithm for learning conjunctions in this model would have much more far-reaching consequences: it gives refutation algorithms for all predicates that are falsified by one of the uniform constant strings. To our knowledge, this is the first hardness result of improper learning for such a large class of natural average-case problems with natural distributions.Sun, 24 Jun 2018 17:11:35 +0300https://eccc.weizmann.ac.il/report/2018/118TR18-117 | Resolution with Counting: Lower Bounds over Different Moduli |
Fedor Part,
Iddo Tzameret
https://eccc.weizmann.ac.il/report/2018/117Resolution over linear equations (introduced in [RT08]) emerged recently as an important object of study. This refutation system, denoted Res(lin$_R$), operates with disjunction of linear equations over a ring $R$. On the one hand, the system captures a natural ``minimal'' extension of resolution in which efficient counting can be achieved; while on the other hand, as observed by, e.g., Krajicek [Kra16] (cf. [IS14,KO18,GK17]), when considered over prime fields, and specifically $\mathbf{F}_2$, super-polynomial lower bounds on (dag-like) Res(lin$_{\mathbf{F}_2}$) is a first step towards the long-standing open problem of establishing constant-depth Frege with counting gates (AC$^0[2]$-Frege) lower bounds.
In this work we develop new lower bound techniques for resolution over linear equations and extend existing ones to work over different rings. We obtain a host of new lower bounds, separations and upper bounds, while calibrating the relative strength of different sub-systems. We first establish, over fields of characteristic zero, exponential-size *dag-like* lower bounds against resolution over linear equations refutations of instances with large coefficients. Specifically, we demonstrate that the subset sum principle $\alpha_1 x_1 +\ldots +\alpha_n x_n = \beta$, for $\beta$ not in the image of the linear form, requires refutations proportional to the size of the image. Moreover, for instances with small coefficients, we separate the tree and dag-like versions of Res(lin$_{\mathbf{F}}$), when $\mathbf{F}$ is of characteristic zero, by employing the notion of immunity from Alekhnovich-Razborov [AR01], among other techniques.
We then study resolution over linear equations over different *finite* fields, extending the work of Itsykson and Sokolov [IS14] who developed tree-like Res(lin$_{\mathbf{F}_2}$) lower bounds techniques. We obtain new lower bounds and separations as follows: (i) exponential-size lower bounds for tree-like Res(lin$_{\mathbf{F}_p}$) Tseitin mod $q$ formulas, for every pair of distinct primes $p, q$. As a corollary we obtain an exponential-size separation between tree-like Res(lin$_{\mathbf{F}_p}$) and tree-like Res(lin$_{\mathbf{F}_q}$); (ii) exponential-size lower bounds for tree-like Res(lin$_{\mathbf{F}_p}$) refutations of random $k$-CNF formulas, for every prime $p$ and constant $k$; and (iii) exponential-size lower bounds for tree-like Res(lin$_{\mathbf{F}}$) refutations of the pigeonhole principle, for *every* field $\mathbf{F}$.Sat, 23 Jun 2018 17:07:33 +0300https://eccc.weizmann.ac.il/report/2018/117TR18-116 | Existence of Simple Extractors |
Xue Chen,
David Zuckerman
https://eccc.weizmann.ac.il/report/2018/116We show that a small subset of seeds of any strong extractor also gives a strong extractor with similar parameters when the number of output bits is a constant. Specifically, if $Ext: \{0,1\}^n \times \{0,1\}^t \to \{0,1\}^m$ is a strong $(k,\epsilon)$-extractor, then for at least 99% of choices of $\tilde{O}(n \cdot 2^m/\epsilon^2)$ seeds, $Ext$ restricted to these seeds is a $(k,3\epsilon)$-extractor. Note that the degree of this restricted extractor is essentially optimal for $m=O(1)$. By combining this with the Leftover Hash Lemma, we deduce that there are strong extractors outputting a constant number of bits with essentially optimal degree where each seed is a linear function, or even a Toeplitz matrix, or a simply-implementable hash function. Although linear extractors were known, such as the one by Trevisan \cite{Trevisan}, it didn't have close to optimal degree (although it did output more bits), and it wasn't known that most sets of linear functions give extractors.
While a simple application of the basic probabilistic method shows the existence of ordinary strong extractors, this approach fails to show the existence of the restricted extractors we seek, or even linear extractors. We therefore adopt a more sophisticated approach, using chaining as used by Rudra and Wootters \cite{RW} and others, combined with the Beck-Fiala theorem from discrepancy theory.
Mon, 18 Jun 2018 16:25:05 +0300https://eccc.weizmann.ac.il/report/2018/116TR18-115 | Satisfiability and Derandomization for Small Polynomial Threshold Circuits |
Valentine Kabanets,
Zhenjian Lu
https://eccc.weizmann.ac.il/report/2018/115A polynomial threshold function (PTF) is defined as the sign of a polynomial $p\colon\bool^n\to\mathbb{R}$. A PTF circuit is a Boolean circuit whose gates are PTFs. We study the problems of exact and (promise) approximate counting for PTF circuits of constant depth.
Satisfiability (#SAT). We give the first zero-error randomized algorithm faster than exhaustive search that counts the number of satisfying assignments of a given constant-depth circuit with a super-linear number of wires whose gates are $s$-sparse PTFs, for $s$ almost quadratic in the input size of the circuit; here a PTF is called $s$-sparse if its underlying polynomial has at most $s$ monomials. More specifically, we show that, for any large enough constant $c$, given a depth-$d$ circuit with $(n^{2-1/c})$-sparse PTF gates that has at most $n^{1+\varepsilon_d}$ wires, where $\varepsilon_d$ depends only on $c$ and $d$, the number of satisfying assignments of the circuit can be computed in randomized time $2^{n-n^{\varepsilon_d}}$ with zero error. This generalizes the result by Chen, Santhanam and Srinivasan (CCC, 2016) who gave a SAT algorithm for constant-depth circuits of super-linear wire complexity with linear threshold function (LTF) gates only.
Quantified derandomization. The quantified derandomization problem, introduced by Goldreich and Wigderson (STOC, 2014), asks to compute the majority value of a given Boolean circuit, under the promise that the minority-value inputs to the circuit are very few. We give a quantified derandomization algorithm for constant-depth PTF circuits with a super-linear number of wires that runs in quasi-polynomial time. More specifically, we show that for any sufficiently large constant $c$, there is an algorithm that, given a degree-$\Delta$ PTF circuit $C$ of depth $d$ with $n^{1+1/c^d}$ wires such that $C$ has at most $2^{n^{1-1/c}}$ minority-value inputs, runs in quasi-polynomial time $\exp\left((\log n)^{O\left(\Delta^2\right)}\right)$ and determines the majority value of $C$. (We obtain a similar quantified derandomization result for PTF circuits with $n^{\Delta}$-sparse PTF gates.) This extends the recent result of Tell (STOC, 2018) for constant-depth LTF circuits of super-linear wire complexity.
Pseudorandom generators. We show how the classical Nisan-Wigderson (NW) generator (JCSS, 1994) yields a nontrivial pseudorandom generator for PTF circuits (of unrestricted depth) with sub-linearly many gates. As a corollary, we get a PRG for degree-$\Delta$ PTFs with the seed length $\exp\left(\sqrt{\Delta\cdot\log n}\right)\cdot\log^2(1/\epsilon)$.
Mon, 11 Jun 2018 06:48:51 +0300https://eccc.weizmann.ac.il/report/2018/115TR18-114 | Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials |
Paul Beame,
Shayan Oveis Gharan,
Xin Yang
https://eccc.weizmann.ac.il/report/2018/114We develop an extension of recent analytic methods for obtaining time-space tradeoff lower bounds for problems of learning from uniformly random labelled examples. With our methods we can obtain bounds for learning concept classes of finite functions from random evaluations even when the sample space of random inputs can be significantly smaller than the concept class of functions and the function values can be from an arbitrary finite set.
At the core of our results, we reduce the time-space complexity of learning from random evaluations to the question of how much the corresponding evaluation matrix amplifies the 2-norms of “almost uniform” probability distributions. To analyze the latter, we formulate it as a semidefinite program, and we analyze its dual. In order to handle function values from arbitrary finite sets, we apply this norm amplification analysis to complex matrices.
As applications that follow from our new techniques, we show that any algorithm that learns $n$-variate polynomial functions of degree at most $d$ over $\mathbb{F}_2$ with success at least $2^{-O(n)}$ from evaluations on randomly chosen inputs either requires space $\Omega(nm/d)$ or $2^{\Omega(n/d)}$ time where $m = (n/d)^{\Theta(d)}$ is the dimension of the space of such polynomials. These bounds are asymptotically optimal for polynomials of arbitrary constant degree since they match the tradeoffs achieved by natural learning algorithms for the problems. We extend these results to learning polynomials of degree at most $d$ over any odd prime field $\mathbb{F}_p$ where we show that $\Omega((mn/d) \log p)$ space or time $p^{\Omega(n/d)}$ is required.
To derive our bounds for learning polynomials over finite fields, we show that an analysis of the dual of the corresponding semidefinite program follows from an understanding of the distribution of the bias of all degree d polynomials with respect to uniformly random inputs.Wed, 06 Jun 2018 22:12:04 +0300https://eccc.weizmann.ac.il/report/2018/114TR18-113 | PPSZ for $k \geq 5$: More Is Better |
Dominik Scheder
https://eccc.weizmann.ac.il/report/2018/113We show that for $k \geq 5$, the PPSZ algorithm for $k$-SAT runs exponentially faster if there is an exponential number of satisfying assignments. More precisely, we show that for every $k\geq 5$, there is a strictly increasing function $f: [0,1] \rightarrow \mathbb{R}$ with $f(0) = 0$ that has the following property. If $F$ is a $k$-CNF formula over $n$ variables and $|{\rm sat}(F)| = 2^{\delta n}$ solutions, then PPSZ finds a satisfying assignment with probability at least $2^{-c_k n -o(n) + f(\delta) n}$. Here, $2^{-c_k n - o(n)}$ is the success probability proved by Paturi, Pudlak, Saks, and Zane for $k$-CNF formulas with a unique satisfying assignment.
Our proof rests on a combinatorial lemma: given a set $S \subseteq \{0,1\}^n$, we can partition $\{0,1\}^n$ into subcubes such that each subcube $B$ contains exactly one element of $S$. Such a partition $\mathcal{B}$ induces a distribution on itself, via $\Pr[B] = |B| / 2^n$ for each $B \in \mathcal{B}$. We are interested in partitions that induce a distribution of high entropy. We show that, in a certain sense, the worst case ($\min_{S: |S| = s} \max_{\mathcal{B}} H(\mathcal{B})$) is achieved if $S$ is a Hamming ball. This lemma implies that every set $S$ of exponential size allows a partition of linear entropy. This in turn leads to an exponential improvement of the success probability of PPSZ.
Wed, 06 Jun 2018 21:54:28 +0300https://eccc.weizmann.ac.il/report/2018/113TR18-112 | Pseudorandom Generators for Width-3 Branching Programs |
Raghu Meka,
Omer Reingold,
Avishay Tal
https://eccc.weizmann.ac.il/report/2018/112We construct pseudorandom generators of seed length $\tilde{O}(\log(n)\cdot \log(1/\epsilon))$ that $\epsilon$-fool ordered read-once branching programs (ROBPs) of width $3$ and length $n$. For unordered ROBPs, we construct pseudorandom generators with seed length $\tilde{O}(\log(n) \cdot \mathrm{poly}(1/\epsilon))$. This is the first improvement for pseudorandom generators fooling width $3$ ROBPs since the work of Nisan [Combinatorica, 1992].
Our constructions are based on the ``iterated milder restrictions'' approach of Gopalan et al. [FOCS, 2012] (which further extends the Ajtai-Wigderson framework [FOCS, 1985]), combined with the INW-generator [STOC, 1994] at the last step (as analyzed by Braverman et al. [SICOMP, 2014]). For the unordered case, we combine iterated milder restrictions with the generator of Chattopadhyay et al. [CCC, 2018].
Our main technical contributions are:
(1) A relabeling technique allowing us to analyze a relabeled version of the given branching program, which turns out to be much easier.
(2) Treating the number of colliding layers in a branching program as a progress measure and showing that it reduces significantly under pseudorandom restrictions.
In addition, we achieve nearly optimal seed-length $\tilde{O}(\log(n/\epsilon))$ for the classes of: (1) read-once polynomials on $n$ variables, (2) locally-monotone ROBPs of length $n$ and width $3$ (generalizing read-once CNFs and DNFs), and (3) constant-width ROBPs of length $n$ having a layer of width $2$ in every consecutive $\mathrm{poly}\log(n)$ layers.Wed, 06 Jun 2018 02:25:01 +0300https://eccc.weizmann.ac.il/report/2018/112TR18-111 | Beating Brute Force for Polynomial Identity Testing of General Depth-3 Circuits |
Rajit Datta,
Partha Mukhopadhyay,
Abhranil Chatterjee,
Vikraman Arvind
https://eccc.weizmann.ac.il/report/2018/111Let $C$ be a depth-3 $\Sigma\Pi\Sigma$ arithmetic circuit of size $s$,
computing a polynomial $f \in \mathbb{F}[x_1,\ldots, x_n]$ (where $\mathbb{F}$ = $\mathbb{Q}$ or
$\mathbb{C}$) with fan-in of product gates bounded by $d$. We give a
deterministic time $2^d \text{poly}(n,s)$ polynomial identity testing
algorithm to check whether $f \equiv 0$ or not.
In the case of finite fields, for $\text{Char}(\mathbb{F}) > d$ we obtain a
deterministic algorithm of running time $2^{\gamma\cdot d}\text{poly}(n,s)$,
whereas for $\text{Char}(\mathbb{F})\leq d$, we obtain a deterministic algorithm of
running time $2^{(\gamma+ 2)\cdot d \log d}\text{poly}(n,s)$ where
$\gamma\leq 5$.Mon, 04 Jun 2018 22:16:26 +0300https://eccc.weizmann.ac.il/report/2018/111