ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usWed, 18 Sep 2019 02:59:55 +0300TR19-125 | Hardness Amplification of Optimization Problems |
Elazar Goldenberg,
Karthik C. S.
https://eccc.weizmann.ac.il/report/2019/125In this paper, we prove a general hardness amplification scheme for optimization problems based on the technique of direct products.
We say that an optimization problem $\Pi$ is direct product feasible if it is possible to efficiently aggregate any $k$ instances of $\Pi$ and form one large instance of $\Pi$ such that given an optimal feasible solution to the larger instance, we can efficiently find optimal feasible solutions to all the $k$ smaller instances. Given a direct product feasible optimization problem $\Pi$, our hardness amplification theorem may be informally stated as follows:
If there is a distribution $\mathcal{D}$ over instances of $\Pi$ of size $n$ such that every randomized algorithm running in time $t(n)$ fails to solve $\Pi$ on $\frac{1}{\alpha(n)}$ fraction of inputs sampled from $\mathcal{D}$, then, assuming some relationships on $\alpha(n)$ and $t(n)$, there is a distribution $\mathcal{D}'$ over instances of $\Pi$ of size $O(n\cdot \alpha(n))$ such that every randomized algorithm running in time $\frac{t(n)}{poly(\alpha(n))}$ fails to solve $\Pi$ on $\frac{99}{100}$ fraction of inputs sampled from $\mathcal{D}'$.
As a consequence of the above theorem, we show hardness amplification of problems in various classes such as NP-hard problems like Max-Clique, Knapsack, and Max-SAT, problems in P such as Longest Common Subsequence, Edit Distance, Matrix Multiplication, and even problems in TFNP such as Factoring and computing Nash equilibrium.Wed, 18 Sep 2019 02:59:55 +0300https://eccc.weizmann.ac.il/report/2019/125TR19-124 | Testing Odd Direct Sums Using High Dimensional Expanders |
Roy Gotlib,
Tali Kaufman
https://eccc.weizmann.ac.il/report/2019/124In this work, using methods from high dimensional expansion, we show that the property of $k$-direct-sum is testable for odd values of $k$ . Previous work of Kaufman and Lubotzky could inherently deal only with the case that $k$ is even, using a reduction to linearity testing.
Interestingly, our work is the first to combine the topological notion of high dimensional expansion (called co-systolic expansion) with the combinatorial/spectral notion of high dimensional expansion (called colorful expansion) to obtain the result.
The classical $k$-direct-sum problem applies to the complete complex; Namely it considers a function defined over all $k$-subsets of some $n$ sized universe. Our result here applies to any collection of $k$-subsets of an $n$-universe, assuming this collection of subsets forms a high dimensional expander.Tue, 17 Sep 2019 03:04:22 +0300https://eccc.weizmann.ac.il/report/2019/124TR19-123 | On the Hardness of Robust Classification |
Pascale Gourdeau,
Varun Kanade,
Marta Kwiatkowska,
James Worrell
https://eccc.weizmann.ac.il/report/2019/123It is becoming increasingly important to understand the vulnerability of machine learning models to adversarial attacks. In this paper we study the feasibility of robust learning from the perspective of computational learning theory, considering both sample and computational complexity. In particular, our definition of robust learnability requires polynomial sample complexity. We start with two negative results. We show that no non-trivial concept class can be robustly learned in the distribution-free setting against an adversary who can perturb just a single input bit. We show moreover that the class of monotone conjunctions cannot be robustly learned under the uniform distribution against an adversary who can perturb $\omega(\log n)$ input bits. However if the adversary is restricted to perturbing $O(\log n)$ bits, then the class of monotone conjunctions can be robustly learned with respect to a general class of distributions (that includes the uniform distribution). Finally, we provide a simple proof of the computational hardness of robust learning on the boolean hypercube. Unlike previous results of this nature, our result does not rely on another computational model (e.g. the statistical query model) nor on any hardness assumption other than the existence of a hard learning problem in the PAC framework.Tue, 17 Sep 2019 03:00:40 +0300https://eccc.weizmann.ac.il/report/2019/123TR19-122 | LDPC Codes Achieve List-Decoding Capacity |
Jonathan Mosheiff,
Nicolas Resch,
Noga Ron-Zewi,
Shashwat Silas,
Mary Wootters
https://eccc.weizmann.ac.il/report/2019/122We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieve list-decoding capacity. These are the first graph-based codes shown to have this property. Previously, the only codes known to achieve list-decoding capacity were completely random codes, random linear codes, and codes constructed by algebraic (rather than combinatorial) techniques. This result opens up a potential avenue towards truly linear-time list-decodable codes which achieve list-decoding capacity.
Our result on list decoding follows from a much more general result: any local property satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallager's distribution. Local properties are properties characterized by the exclusion of small sets of codewords, and include list-decoding, list-recovery and average-radius list-decoding. Along the way, we give a characterization of sets of codewords that are likely to appear in a random linear code, which may be of independent interest.Tue, 17 Sep 2019 02:58:26 +0300https://eccc.weizmann.ac.il/report/2019/122TR19-121 | Vanishing-Error Approximate Degree and QMA Complexity |
Justin Thaler,
Alexander A. Sherstov
https://eccc.weizmann.ac.il/report/2019/121The $\epsilon$-approximate degree of a function $f\colon X \to \{0, 1\}$ is the least degree of a multivariate real polynomial $p$ such that $|p(x)-f(x)| \leq \epsilon$ for all $x \in X$. We determine the $\epsilon$-approximate degree of the element distinctness function, the surjectivity function, and the permutation testing problem, showing they are $\Theta(n^{2/3} \log^{1/3}(1/\epsilon))$, $\tilde\Theta(n^{3/4} \log^{1/4}(1/\epsilon))$, and $\Theta(n^{1/3} \log^{2/3}(1/\epsilon))$, respectively. Previously, these bounds were known only for constant $\epsilon.$
We also derive a connection between vanishing-error approximate degree and quantum Merlin--Arthur (QMA) query complexity. We use this connection to show that the QMA complexity of permutation testing is $\Omega(n^{1/4})$. This improves on the previous best lower bound of $\Omega(n^{1/6})$ due to Aaronson (Quantum Information & Computation, 2012), and comes somewhat close to matching a known upper bound of $O(n^{1/3})$.Tue, 17 Sep 2019 02:55:59 +0300https://eccc.weizmann.ac.il/report/2019/121TR19-120 | Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation |
Or Meir
https://eccc.weizmann.ac.il/report/2019/120One of the major open problems in complexity theory is proving super-logarithmic
lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5, 3/4) suggested to approach this problem by proving that depth complexity behaves "as expected" with respect to the composition of functions $f \diamond g$. They showed that the validity of this conjecture would imply that $\mathbf{P}\not\subseteq\mathbf{NC}^1$.
As a way to realize this program, Edmonds et. al. (Computational Complexity 10, 3) suggested to study the "multiplexor relation" $MUX$, which is a simplification of functions. In this note, we present two results regarding this relation:
- The multiplexor relation is "complete" for the approach of Karchmer et. al.
in the following sense: if we could prove (a variant of) their conjecture
for the composition $f \diamond MUX$ for every function $f$, then this would
imply $\mathbf{P}\not\subseteq\mathbf{NC}^1$.
- A simpler proof of a lower bound for the multiplexor relation due
to Edmonds et. al. Our proof has the additional benefit of fitting
better with the machinery used in previous works on the subject.Sun, 15 Sep 2019 17:52:07 +0300https://eccc.weizmann.ac.il/report/2019/120TR19-119 | On Hitting-Set Generators for Polynomials that Vanish Rarely |
Dean Doron,
Amnon Ta-Shma,
Roei Tell
https://eccc.weizmann.ac.il/report/2019/119We study the following question: Is it easier to construct a hitting-set generator for polynomials $p:\mathbb{F}^n\rightarrow\mathbb{F}$ of degree $d$ if we are guaranteed that the polynomial vanishes on at most an $\epsilon>0$ fraction of its inputs? We will specifically be interested in tiny values of $\epsilon\ll d/|\mathbb{F}|$. This question was first asked by Goldreich and Wigderson (STOC 2014), who studied a specific setting geared for an application, and another specific setting was later studied by the third author (CCC 2017).
In this work our main interest is a *systematic study of the problem itself*, in its general form, and we prove results that significantly extend and improve the two previously-known results. Our contributions are of two types:
1. Over fields of size $2\le|\mathbb{F}|\le poly(n)$, we show that the seed length of any hitting-set generator for polynomials of degree $d\le n^{.49}$ that vanish on at most $\epsilon=|\mathbb{F}|^{-t}$ of their inputs is at least $\Omega\left((d/t)\cdot\log(n)\right)$.
2. Over $\mathbb{F}_2$, we show that there exists a (non-explicit) hitting-set generator for polynomials of degree $d\le n^{.99}$ that vanish on at most $\epsilon=|\mathbb{F}|^{-t}$ of their inputs with seed length $O\left((d-t)\cdot\log(n)\right)$. We also show a polynomial-time computable hitting-set generator with seed length $O\left( (d-t)\cdot\left(2^{d-t}+\log(n)\right) \right)$.
In addition, we prove that the problem we study is closely related to the following question: ``Does there exist a small set $S\subseteq\mathbb{F}^n$ whose degree-$d$ closure is very large?'', where the degree-$d$ closure of $S$ is the variety induced by the set of degree-$d$ polynomials that vanish on $S$. We then use our lower bounds on hitting-sets for polynomials that vanish rarely to deduce lower bounds for this question.Sun, 15 Sep 2019 17:51:52 +0300https://eccc.weizmann.ac.il/report/2019/119TR19-118 | Hardness Magnification for all Sparse NP Languages |
Lijie Chen,
Ce Jin,
Ryan Williams
https://eccc.weizmann.ac.il/report/2019/118In the Minimum Circuit Size Problem (MCSP[s(m)]), we ask if there is a circuit of size s(m) computing a given truth-table of length n = 2^m. Recently, a surprising phenomenon termed as hardness magnification by [Oliveira and Santhanam, FOCS 2018] was discovered for MCSP[s(m)] and the related problem MKtP of computing time-bounded Kolmogorov complexity. In [Oliveira and Santhanam, FOCS 2018], [Oliveira, Pich, and Santhanam, CCC 2019], and [McKay, Murray, and Williams, STOC 2019], it was shown that minor (n^{1+eps}-style) lower bounds for MCSP[2^o(m)] or MKtP[2^o(m)] would imply breakthrough circuit lower bounds such as NP is not in P/poly, NP is not in NC^1, or EXP is not in P/poly.
We consider the question: What is so special about MCSP and MKtP? Why do they admit this striking phenomenon? One simple property is that all variants of MCSP (and MKtP) considered in prior work are sparse languages. For example, MCSP[s(m)] has 2^{O(s(m))} yes-instances of length n=2^m, so MCSP[2^o(m)] is 2^{n^o(1)}-sparse.
We show that there is a hardness magnification phenomenon for all equally-sparse NP languages. Formally, suppose there is an eps > 0 and a language L in NP which is 2^{n^o(1)}-sparse, and L is not in Circuit[n^{1+eps}]. Then NP does not have n^k-size circuits for all k. We prove analogous theorems for De Morgan formulas, B_2-formulas, branching programs, AC^0[6] and TC^0 circuits, and more: improving the state of the art in NP lower bounds against any of these models by an eps factor in the exponent would already imply NP lower bounds for all fixed polynomials. In fact, in our proofs it is not necessary to prove a (say) n^{1+eps} circuit size lower bound for L: one only has to prove a lower bound against n^{1+eps}-time n^eps-space deterministic algorithms with n^eps advice bits. Such lower bounds are well-known for non-sparse problems.
Building on our techniques, we also show interesting new hardness magnifications for search-MCSP and search-MKtP (where one must output small circuits or short representations of strings), showing consequences such as Parity-P (or PP, PSPACE, and EXP) is not contained in P/poly (or NC^1, AC^0[6], or branching programs of polynomial size). For instance, if there is an eps > 0 such that search-MCSP[2^{beta m}] does not have De Morgan formulas of size n^{3+eps} for all constants beta > 0, then Parity-P is not in NC^1.Sun, 15 Sep 2019 17:51:37 +0300https://eccc.weizmann.ac.il/report/2019/118TR19-117 | Locally Testable Non-Malleable Codes |
Silas Richelson,
Sourya Roy
https://eccc.weizmann.ac.il/report/2019/117In this work we adapt the notion of non-malleability for codes or Dziembowski, Pietrzak and Wichs (ICS 2010) to locally testable codes. Roughly speaking, a locally testable code is non-malleable if any tampered codeword which passes the local test with good probability is close to a valid codeword which either encodes the original, or an unrelated message.
We instantiate our definition by proving that a Reed-Muller-type code is non-malleable in the following sense: any adversary who independently tampers the coordinates of the code so that the tampered code passes the test with good probability, is tampering the underlying polynomial according to an affine transformation.
To the best of our knowledge, prior to this work, polynomial codes were not known to possess any non-malleability guarantees. Our analysis builds on the sampler-based decoding techniques common to several recent works.Tue, 10 Sep 2019 15:26:11 +0300https://eccc.weizmann.ac.il/report/2019/117TR19-116 | $d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors |
Venkatesan Guruswami,
Sai Sandeep
https://eccc.weizmann.ac.il/report/2019/116The $d$-to-$1$ conjecture of Khot asserts that it is hard to satisfy an $\epsilon$ fraction of constraints of a satisfiable $d$-to-$1$ Label Cover instance, for arbitrarily small $\epsilon > 0$. We prove that the $d$-to-$1$ conjecture for any fixed $d$ implies the hardness of coloring a $4$-colorable graph with $C$ colors for arbitrarily large integers $C$. Earlier, this implication was only known under the $2$-to-$1$ conjecture, which is the strongest in the family of $d$-to-$1$ conjectures.Mon, 09 Sep 2019 23:29:16 +0300https://eccc.weizmann.ac.il/report/2019/116