ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usSun, 23 Feb 2020 07:37:13 +0200TR20-023 | Non-Malleability against Polynomial Tampering |
Eshan Chattopadhyay,
Jyun-Jie Liao,
Marshall Ball,
Tal Malkin,
Li-Yang Tan
https://eccc.weizmann.ac.il/report/2020/023We present the first explicit construction of a non-malleable code that can handle tampering functions that are bounded-degree polynomials.
Prior to our work, this was only known for degree-1 polynomials (affine tampering functions), due to Chattopadhyay and Li (STOC 2017). As a direct corollary, we obtain an explicit non-malleable code that is secure against tampering by bounded-size arithmetic circuits.
We show applications of our non-malleable code in constructing non-malleable secret sharing schemes that are robust against bounded-degree polynomial tampering. In fact our result is stronger: we can handle adversaries that can adaptively choose the polynomial tampering function based on initial leakage of a bounded number of shares.
Our results are derived from explicit constructions of seedless non-malleable extractors that can handle bounded-degree polynomial tampering functions. Prior to our work, no such result was known even for degree-2 (quadratic) polynomials.Sun, 23 Feb 2020 07:37:13 +0200https://eccc.weizmann.ac.il/report/2020/023TR20-022 | Interactive Error Resilience Beyond $\frac{2}{7}$ |
Klim Efremenko,
Gillat Kol,
Raghuvansh Saxena
https://eccc.weizmann.ac.il/report/2020/022Interactive error correcting codes can protect interactive communication protocols against a constant fraction of adversarial errors, while incurring only a constant multiplicative overhead in the total communication. What is the maximum fraction of errors that such codes can protect against?
For the non-adaptive channel, where the parties must agree in advance on the order in which they communicate, Braverman and Rao prove that the maximum error resilience is~$\frac{1}{4}$ (STOC, 2011). Ghaffari, Haeupler, and Sudan (STOC, 2014) consider the {\em adaptive} channel, where the order in which the parties communicate may not be fixed, and give a clever protocol that is resilient to a $\frac{2}{7}$ fraction of errors. This was believed to be optimal.
We revisit this result, and show how to overcome the $\frac{2}{7}$ barrier. Specifically, we show that, over the adaptive channel, every two-party communication protocol can be converted to a protocol that is resilient to $\frac{7}{24} > \frac{2}{7}$ fraction of errors with only a constant multiplicative overhead to the total communication. The protocol is obtained by a novel implementation of a feedback mechanism over the adaptive channel.
Sat, 22 Feb 2020 04:29:22 +0200https://eccc.weizmann.ac.il/report/2020/022TR20-021 | NP-Hardness of Circuit Minimization for Multi-Output Functions |
Rahul Ilango,
Bruno Loff,
Igor Carboni Oliveira
https://eccc.weizmann.ac.il/report/2020/021Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an explicitly given function is ${NP}$-complete. While this is known to hold in restricted models such as DNFs, making progress with respect to more expressive classes of circuits has been elusive.
In this work, we establish the first ${NP}$-hardness result for circuit minimization of total functions in the setting of general (unrestricted) Boolean circuits. More precisely, we show that computing the minimum circuit size of a given multi-output Boolean function $f \colon \{0,1\}^n \to \{0,1\}^m$ is ${NP}$-hard under many-one polynomial-time randomized reductions. Our argument builds on a simpler ${NP}$-hardness proof for the circuit minimization problem for (single-output) Boolean functions under an extended set of generators.
Complementing these results, we investigate the computational hardness of minimizing communication. We establish that several variants of this problem are ${NP}$-hard under deterministic reductions. In particular, unless ${P} = {NP}$, no polynomial-time computable function can approximate the deterministic two-party communication complexity of a partial Boolean function up to a polynomial. This has consequences for the class of structural results that one might hope to show about the communication complexity of partial functions. Fri, 21 Feb 2020 17:13:20 +0200https://eccc.weizmann.ac.il/report/2020/021TR20-020 | Improved Approximate Degree Bounds For $k$-distinctness |
Shuchen Zhu,
Justin Thaler,
Nikhil Mande
https://eccc.weizmann.ac.il/report/2020/020An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the $k$-distinctness function on inputs of size $N$. While the case of $k=2$ (also called Element Distinctness) is well-understood, there is a polynomial gap between the known upper and lower bounds for all constants $k>2$. Specifically, the best known upper bound is $O(N^{(3/4)-1/(2^{k+2}-4)})$ (Belovs, FOCS 2012), while the best known lower bound for $k >= 2$ is $\Omega(N^{2/3} + N^{(3/4)-1/(2k)})$ (Aaronson and Shi, J.~ACM 2004; Bun, Kothari, and Thaler, STOC 2018).
For any constant $k >= 4$, we improve the lower bound to $\Omega(N^{(3/4)-1/(4k)})$. This yields, for example, the first proof that $4$-distinctness is strictly harder than Element Distinctness. Our lower bound applies more generally to approximate degree.
As a secondary result, we give a simple construction of an approximating polynomial of degree $O(N^{3/4})$ that applies whenever $k <= polylog(N)$.Fri, 21 Feb 2020 15:58:40 +0200https://eccc.weizmann.ac.il/report/2020/020TR20-019 | A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet |
Siddharth Bhandari,
Prahladh Harsha
https://eccc.weizmann.ac.il/report/2020/019Recently, Cohen, Haeupler and Schulman gave an explicit construction of binary tree codes over polylogarithmic-sized output alphabet based on Pudl\'{a}k's construction of maximum-distance-separable (MDS) tree codes using totally-non-singular triangular matrices. In this short note, we give a unified and simpler presentation of Pudl\'{a}k and Cohen-Haeupler-Schulman's constructions. Wed, 19 Feb 2020 17:04:50 +0200https://eccc.weizmann.ac.il/report/2020/019TR20-018 | Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates |
Valentine Kabanets,
Sajin Koroth,
Zhenjian Lu,
Dimitrios Myrisiotis,
Igor Oliveira
https://eccc.weizmann.ac.il/report/2020/018The class $FORMULA[s] \circ \mathcal{G}$ consists of Boolean functions computable by size-$s$ de Morgan formulas whose leaves are any Boolean functions from a class $\mathcal{G}$. We give lower bounds and (SAT, Learning, and PRG) algorithms for $FORMULA[n^{1.99}]\circ \mathcal{G}$, for classes $\mathcal{G}$ of functions with low communication complexity. Let $R^{(k)}(\mathcal{G})$ be the maximum $k$-party number-on-forehead randomized communication complexity of a function in $\mathcal{G}$. Among other results, we show:
(1) The Generalized Inner Product function $GIP^k_n$ cannot be computed in $FORMULA[s]\circ \mathcal{G}$ on more than $1/2+\varepsilon$ fraction of inputs for
$$
s = o \! \left ( \frac{n^2}{ \left(k \cdot 4^k \cdot {R}^{(k)}(\mathcal{G}) \cdot \log (n/\varepsilon) \cdot \log (1/\varepsilon) \right)^{2}} \right).
$$
This significantly extends the lower bounds against bipartite formulas obtained by [Tal17]. As a corollary, we get an average-case lower bound for $GIP^k_n$ against $FORMULA[n^{1.99}]\circ PTF^{k-1}$, i.e., sub-quadratic-size de Morgan formulas with degree-$(k-1)$ PTF (polynomial threshold function) gates at the bottom. Previously, only sub-linear lower bounds were known [Nis94, Vio15] for circuits with PTF gates.
(2) There is a PRG of seed length $n/2 + O\left( \sqrt{s} \cdot R^{(2)}(\mathcal{G}) \cdot\log(s/\varepsilon) \cdot \log (1/\varepsilon) \right)$ that $\varepsilon$-fools $FORMULA[s] \circ \mathcal{G}$. For the special case of $FORMULA[s] \circ LTF$, i.e., size-$s$ formulas with LTF (linear threshold function) gates at the bottom, we get the better seed length $O\left(n^{1/2}\cdot s^{1/4}\cdot \log(n)\cdot \log(n/\varepsilon)\right)$. In particular, this provides the first non-trivial PRG (with seed length $o(n)$) for intersections of $n$ half-spaces in the regime where $\varepsilon \leq 1/n$, complementing a recent result of [OST19].
(3) There exists a randomized $2^{n-t}$-time $\#$SAT algorithm for $FORMULA[s] \circ \mathcal{G}$, where
$$
t = \Omega\left(\frac{n}{\sqrt{s} \cdot \log^2(s)\cdot R^{(2)}(\mathcal{G})}\right)^{1/2}.
$$
In particular, this implies a nontrivial #SAT algorithm for $FORMULA[n^{1.99}]\circ LTF$.
(4) The Minimum Circuit Size Problem is not in $FORMULA[n^{1.99}] \circ XOR$; thereby making progress on hardness magnification, in connection with results from [OPS19, CJW19]. On the algorithmic side, we show that the concept class $FORMULA[n^{1.99}] \circ XOR$ can be PAC-learned in time $2^{O(n/\log n)}$.
Tue, 18 Feb 2020 20:28:25 +0200https://eccc.weizmann.ac.il/report/2020/018TR20-017 | Multiparty Karchmer-Wigderson Games and Threshold Circuits |
Alexander Kozachinskiy,
Vladimir Podolskii
https://eccc.weizmann.ac.il/report/2020/017We suggest a generalization of Karchmer-Wigderson communication games to the multiparty setting. Our generalization turns out to be tightly connected to circuits consisting of threshold gates. This allows us to obtain new explicit constructions of such circuits for several functions. In particular, we provide an explicit (polynomial-time computable) log-depth monotone formula for Majority function, consisting only of 3-bit majority gates and variables. This resolves a conjecture of Cohen et al. (CRYPTO 2013). Tue, 18 Feb 2020 20:24:22 +0200https://eccc.weizmann.ac.il/report/2020/017TR20-016 | Hitting Sets Give Two-Sided Derandomization of Small Space |
Kuan Cheng,
William Hoza
https://eccc.weizmann.ac.il/report/2020/016A hitting set is a "one-sided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have one-sided error. We study the problem of using a given hitting set to derandomize algorithms that have two-sided error, focusing on space-bounded algorithms. For our first result, we show that if there is a log-space hitting set for polynomial-width read-once branching programs (ROBPs), then not only does $\mathbf{L} = \mathbf{RL}$, but $\mathbf{L} = \mathbf{BPL}$ as well. This answers a question raised by Hoza and Zuckerman (FOCS 2018).
Next, we consider constant-width ROBPs. We show that if there are log-space hitting sets for constant-width ROBPs, then given black-box access to a constant-width ROBP $f$, it is possible to deterministically estimate $\mathbb{E}[f]$ to within $\pm \varepsilon$ in space $O(\log(n/\varepsilon))$. Unconditionally, we give a deterministic algorithm for this problem with space complexity $O(\log^2 n + \log(1/\varepsilon))$, slightly improving over previous work.
Finally, we investigate the limits of this line of work. Perhaps the strongest reduction along these lines one could hope for would say that for every explicit hitting set, there is an explicit PRG with similar parameters. In the setting of constant-width ROBPs over a large alphabet, we prove that establishing such a strong reduction is at least as difficult as constructing a good PRG outright. Quantitatively, we prove that if the strong reduction holds, then for every constant $\alpha > 0$, there is an explicit PRG for constant-width ROBPs with seed length $O(\log^{1 + \alpha} n)$. Along the way, unconditionally, we construct an improved hitting set for ROBPs over a large alphabet.Tue, 18 Feb 2020 19:48:26 +0200https://eccc.weizmann.ac.il/report/2020/016TR20-015 | New lower bounds for probabilistic degree and AC0 with parity gates |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2020/015We prove new lower bounds for computing some functions $f:\{0,1\}^{n}\to\{0,1\}$ in $E^{NP}$ by polynomials modulo $2$, constant-depth circuits with parity gates ($AC^{0}[\oplus]$), and related classes. Results include:
(1) $\Omega(n/\log^{2}n)$ lower bounds probabilistic degree. This is optimal up to a factor $O(\log^{2}n)$. The previous best lower bound was $\Omega(\sqrt{n})$ proved in the 80's by Razborov and Smolensky.
(2) $\exp(\Omega(n/\log^{2}n)^{1/(h-1)})$ lower bounds on the size of depth-$h$ $AC^{0}[\oplus]$ circuits, for any $h$. This almost matches the $\exp(\Omega(n^{1/(h-1)}))$ lower bounds for $AC^{0}$ by Hastad. The previous best lower bound was $\exp(\Omega(n^{1/(h+1)}))$ by Rajgopal, Santhanam, and Srinivasan who recently improved Razborov and Smolensky's $\exp(\Omega(n^{1/(2h-2)}))$ bound.
(3) $(1/2-(\log^{O(h)}s)/n)$ average-case hardness for size-$s$ depth-$h$ $AC^{0}[\oplus]$ circuits under the uniform distribution, for say polynomial or quasi-polynomial $s$, and any fixed $h$. The previous best was $(1/2-(\log^{O(h)}s)/\sqrt{n})$.
(4) any majority of $t$ $AC^{0}[\oplus]$ circuits, $MAJ_{^{t}}\circ AC^{0}[\oplus]$, of size $s$ and depth $h$, has $t\ge n^{2}/\log^{O(h)}(s)$, for any $s,h$. The previous best was $t\ge n/\log^{O(h)}(s)$.
(5) any $AC^{0}[\oplus]\circ LTF_{t}\circ AC^{0}[\oplus]\circ LTF$ circuit, where $LTF$ are threshold functions, has $t\ge n/\log^{O(h)}(s)$, for any $s,h$. The previous best was $t\ge\sqrt{n}/\log^{O(h)}(s)$ recently proved by Alman and Chen.
The mentioned previous best lower bounds in (1), (3), and (4) held for the Majority function. Each of the new lower bounds in this paper is false for Majority. For (2) and (5) the previous best held for $E^{NP}$.
The proofs build on Williams' "guess-and-SAT" method. For (1) we show how to use a PCP by Ben-Sasson and Viola towards probabilistic-degree lower bounds. Results (2), (4), and (5) are then more or less automatic, as is (3) under a non-uniform distribution. To strengthen (3) to hold under the uniform distribution we use a different argument which combines the recent work by Alman and Chen with hardness amplification.
A concurrent work by Chen and Ren obtains a result stronger than (3).
Tue, 18 Feb 2020 19:11:55 +0200https://eccc.weizmann.ac.il/report/2020/015TR20-014 | Palette-Alternating Tree Codes |
Gil Cohen,
Shahar Samocha
https://eccc.weizmann.ac.il/report/2020/014A tree code is an edge-coloring of the complete infinite binary tree such that every two nodes of equal depth have a fraction--bounded away from $0$--of mismatched colors between the corresponding paths to their least common ancestor. Tree codes were introduced in a seminal work by Schulman (STOC 1993) and serve as a key ingredient in almost all deterministic interactive coding schemes. The number of colors effects the coding scheme's rate.
It is shown that $4$ is precisely the least number of colors for which tree codes exist. Thus, tree-code-based coding schemes cannot achieve rate larger than $1/2$. To overcome this barrier, a relaxed notion called palette-alternating tree codes is introduced, in which the number of colors can depend on the layer. We prove the existence of such constructs in which most layers use $2$ colors--the bare minimum. The distance-rate tradeoff we obtain matches the Gilbert-Varshamov bound.
Based on palette-alternating tree codes, we devise a deterministic interactive coding scheme against adversarial errors that approaches capacity. To analyze our protocol, we prove a structural result on the location of failed communication-rounds induced by the error pattern enforced by the adversary. Our coding scheme is efficient given an explicit palette-alternating tree codes and serves as an alternative to the scheme obtained by Gelles et al. (SODA 2016)Tue, 18 Feb 2020 17:46:07 +0200https://eccc.weizmann.ac.il/report/2020/014