ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usTue, 12 Nov 2019 00:26:59 +0200TR19-160 | Tractable Unordered 3-CNF Games |
Md Lutfar Rahman,
Thomas Watson
https://eccc.weizmann.ac.il/report/2019/160The classic TQBF problem can be viewed as a game in which two players alternate turns assigning truth values to a CNF formula's variables in a prescribed order, and the winner is determined by whether the CNF gets satisfied. The complexity of deciding which player has a winning strategy in this game is well-understood: it is NL-complete for 2-CNFs and PSPACE-complete for 3-CNFs.
We continue the study of the unordered variant of this game, in which each turn consists of picking any remaining variable and assigning it a truth value. The complexity of deciding who can win on a given CNF is less well-understood; prior work by the authors showed it is in L for 2-CNFs and PSPACE-complete for 5-CNFs. We conjecture it may be efficiently solvable on 3-CNFs, and we make progress in this direction by proving the problem is in P, indeed in L, for 3-CNFs with a certain restriction, namely that each width-3 clause has at least one variable that appears in no other clause. Another (incomparable) restriction of this problem was previously shown to be tractable by Kutz.Tue, 12 Nov 2019 00:26:59 +0200https://eccc.weizmann.ac.il/report/2019/160TR19-159 | SETH-hardness of Coding Problems |
Noah Stephens-Davidowitz,
Vinod Vaikuntanathan
https://eccc.weizmann.ac.il/report/2019/159We show that assuming the strong exponential-time hypothesis (SETH), there are no non-trivial algorithms for the nearest codeword problem (NCP), the minimum distance problem (MDP), or the nearest codeword problem with preprocessing (NCPP) on linear codes over any finite field. More precisely, we show that there are no NCP, MDP, or NCPP algorithms running in time $q^{(1-\epsilon)n}$ for any constant $\epsilon>0$ for codes with $q^n$ codewords. (In the case of NCPP, we assume non-uniform SETH.)
We also show that there are no sub-exponential-time algorithms for $\gamma$-approximate versions of these problems for some constant $\gamma > 1$, under different versions of the exponential-time hypothesis.Mon, 11 Nov 2019 21:23:19 +0200https://eccc.weizmann.ac.il/report/2019/159TR19-158 | Sorting Can Exponentially Speed Up Pure Dynamic Programming |
Stasys Jukna,
Hannes Seiwert
https://eccc.weizmann.ac.il/report/2019/158Many discrete minimization problems, including various versions of the shortest path problem, can be efficiently solved by dynamic programming (DP) algorithms that are ``pure'' in that they only perform basic operations, as $\min$, $\max$, $+$, but no conditional branchings via if-then-else in their recursion equations. It is known that any pure $(\min,+)$ DP algorithm solving the minimum weight spanning tree problem on undirected $n$-vertex graphs must perform at least $2^{\Omega(\sqrt{n})}$ operations. We show that this problem \emph{can} be solved by a pure $(\min,\max,+)$ DP algorithm performing only $O(n^3)$ operations. The algorithm is essentially a $(\min,\max)$ algorithm: addition operations are only used to output the final values. The presence of both $\min$ and $\max$ operations means that now DP algorithms can sort: this explains the title of the paper.Mon, 11 Nov 2019 20:19:07 +0200https://eccc.weizmann.ac.il/report/2019/158TR19-157 | How QBF Expansion Makes Strategy Extraction Hard |
Judith Clymo,
Leroy Chew
https://eccc.weizmann.ac.il/report/2019/157In this paper we show that the QBF proof checking format QRAT (Quantified Resolution Asymmetric Tautologies) by Heule, Biere and Seidl cannot have polynomial-time strategy extraction unless P=PSPACE. In our proof, the crucial property that makes strategy extraction PSPACE-hard for this proof format is universal expansion, even expansion on a single variable.
While expansion reasoning used in other QBF calculi can admit polynomial time strategy extraction, we find this is conditional on a property studied in proof complexity theory. We show that strategy extraction on expansion based systems can only happen when the underlying propositional calculus has the property of feasible interpolation. Sun, 10 Nov 2019 08:56:13 +0200https://eccc.weizmann.ac.il/report/2019/157TR19-156 | Almost Optimal Testers for Concise Representations |
Nader Bshouty
https://eccc.weizmann.ac.il/report/2019/156We give improved and almost optimal testers for several classes of Boolean functions on $n$ inputs that have concise representation in the uniform and distribution-free model. Classes, such as $k$-Junta, $k$-Linear Function, $s$-Term DNF, $s$-Term Monotone DNF, $r$-DNF, Decision List, $r$-Decision List, size-$s$ Decision Tree, size-$s$ Boolean Formula, size-$s$ Branching Program, $s$-Sparse Polynomial over the binary field and functions with Fourier Degree at most $d$.Thu, 07 Nov 2019 17:44:18 +0200https://eccc.weizmann.ac.il/report/2019/156TR19-155 | Pseudorandomness and the Minimum Circuit Size Problem |
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2019/155We explore the possibility of basing one-way functions on the average-case hardness of the fundamental Minimum Circuit Size Problem (MCSP[$s$]), which asks whether a Boolean function on $n$ bits specified by its truth table has circuits of size $s(n)$.
1. (Pseudorandomness from Zero-Error Average-Case Hardness) We show that for a given size function $s$,
the following are equivalent: Pseudorandom distributions supported on strings describable by $s(O(n))$-size circuits exist; Hitting sets supported on strings describable by $s(O(n))$-size circuits exist; MCSP[$s(O(n))$] is zero-error average-case hard. Using similar techniques, we show that Feige's hypothesis for random $k$-CNFs implies that there is a pseudorandom distribution (with constant error) supported entirely on satisfiable formulas. Underlying our results is a general notion of semantic sampling, which might be of independent interest.
2. (A New Conjecture) In analogy to a known universal construction of succinct hitting sets against arbitrary polynomial-size adversaries, we propose the Universality Conjecture: there is a universal construction of succinct pseudorandom distributions against arbitrary polynomial-size adversaries. We show that under the Universality Conjecture, the following are equivalent: One-way functions exist; Natural proofs useful against sub-exponential size circuits do not exist; Learning polynomial-size circuits with membership queries over the uniform distribution is hard; MCSP[$2^{\epsilon n}$] is zero-error hard on average for some $\epsilon > 0$; Cryptographic succinct hitting set generators exist.
3. (Non-Black-Box Results) We show that for weak circuit classes C against which there are natural proofs [Razborov-Rudich97], pseudorandom functions secure against poly-size circuits in C imply superpolynomial lower bounds in P against poly-size circuits in C. We also show that for a certain natural variant of MCSP, there is a polynomial-time reduction from approximating the problem well in the worst case to solving it on average. These results are shown using non-black-box techniques, and in the first case we show that there is no black-box proof of the result under standard crypto assumptions.
Wed, 06 Nov 2019 18:21:39 +0200https://eccc.weizmann.ac.il/report/2019/155TR19-154 | Ar?kan meets Shannon: Polar codes with near-optimal convergence to channel capacity |
Venkatesan Guruswami,
Andrii Riazanov,
Min Ye
https://eccc.weizmann.ac.il/report/2019/154Let $W$ be a binary-input memoryless symmetric (BMS) channel with Shannon capacity $I(W)$ and fix any $\alpha > 0$. We construct, for any sufficiently small $\delta > 0$, binary linear codes of block length $O(1/\delta^{2+\alpha})$ and rate $I(W)-\delta$ that enable reliable communication on $W$ with quasi-linear time encoding and decoding. Shannon's noisy coding theorem established the existence of such codes (without efficient constructions or decoding) with block length $O(1/\delta^2)$. This quadratic dependence on the gap $\delta$ to capacity is known to be best possible. Our result thus yields a constructive version of Shannon's theorem with near-optimal convergence to capacity as a function of the block length. This resolves a central theoretical challenge associated with the attainment of Shannon capacity. Previously such a result was only known for the erasure channel.
Our codes are a variant of Ar?kanâ€™s polar codes based on multiple carefully constructed local kernels, one for each intermediate channel that arises in the decoding. A crucial ingredient in the analysis is a strong converse of the noisy coding theorem when communicating using random linear codes on arbitrary BMS channels. Our converse theorem shows extreme unpredictability of even a single message bit for random coding at rates slightly above capacity.Wed, 06 Nov 2019 18:01:10 +0200https://eccc.weizmann.ac.il/report/2019/154TR19-153 | Optimally Resilient Codes for List-Decoding from Insertions and Deletions |
Venkatesan Guruswami,
Bernhard Haeupler,
Amirbehshad Shahrasbi
https://eccc.weizmann.ac.il/report/2019/153We give a complete answer to the following basic question: ``What is the maximal fraction of deletions or insertions tolerable by $q$-ary list-decodable codes with non-vanishing information rate?''
This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best known results was that a $\gamma \leq 0.707$ fraction of insertions is tolerable by some binary code family.
For any desired $\epsilon > 0$, we construct a family of binary codes of positive rate which can be efficiently list-decoded from any combination of $\gamma$ fraction of insertions and $\delta$ fraction of deletions as long as $ \gamma + 2\delta \leq 1 -\epsilon$. On the other hand, for any $\gamma, \delta$ with $\gamma + 2\delta = 1$ list-decoding is impossible. Our result thus precisely characterizes the feasibility region of binary list-decodable codes for insertions and deletions.
We further generalize our result to codes over any finite alphabet of size $q$. Surprisingly, our work reveals that the feasibility region for $q>2$ is *not* the natural generalization of the binary bound above. We provide tight upper and lower bounds that precisely pin down the feasibility region, which turns out to have a $(q-1)$-piece-wise linear boundary whose $q$ corner-points lie on a quadratic curve.
The main technical work in our results is proving the existence of code families of sufficiently large *size* with good list-decoding properties for any combination of $\delta,\gamma$ within the claimed feasibility region. We achieve this via an intricate analysis of codes introduced by [Bukh, Ma; SIAM J. Discrete Math; 2014]. Finally we give a simple yet powerful concatenation scheme for list-decodable insertion-deletion codes which transforms any such (non-efficient) code family (with vanishing information rate) into an efficiently decodable code family with constant rate. Wed, 06 Nov 2019 15:44:22 +0200https://eccc.weizmann.ac.il/report/2019/153TR19-152 | Quantum versus Randomized Communication Complexity, with Efficient Players |
Uma Girish,
Ran Raz,
Avishay Tal
https://eccc.weizmann.ac.il/report/2019/152We study a new type of separation between quantum and classical communication complexity which is obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented by small quantum circuits with oracle access to their inputs. More precisely, we give an explicit partial Boolean function that can be computed in the quantum-simultaneous-with-entanglement model of communication, however, every interactive randomized protocol is of exponentially larger cost. Furthermore, all the parties in the quantum protocol can be implemented by quantum circuits of small size with blackbox access to the inputs. Our result qualitatively matches the strongest known separation between quantum and classical communication complexity and is obtained using a quantum protocol where all parties are efficient.Wed, 06 Nov 2019 10:42:22 +0200https://eccc.weizmann.ac.il/report/2019/152TR19-151 | Optimal Inapproximability with Universal Factor Graphs |
Johan Hastad,
Per Austrin,
Jonah Brown-Cohen
https://eccc.weizmann.ac.il/report/2019/151The factor graph of an instance of a constraint satisfaction problem (CSP) is the bipartite graph indicating which variables appear in each constraint. An instance of the CSP is given by the factor graph together with a list of which predicate is applied for each constraint. We establish that many Max-CSPs remains as hard to approximate as in the general case even when the factor graph is fixed (depending only on the size of the instance) and known in advance.
Examples of results obtained for this restricted setting are:
Optimal inapproximability for Max-3-Lin.
Approximation resistance for predicates supporting pairwise independent subgroups.
Hardness of the ``$(2+\epsilon)$-Sat'' problem and other Promise CSPs.
The main technical tool used to establish these results is a new way of folding the long code which we call ``functional folding''.
Tue, 05 Nov 2019 11:01:26 +0200https://eccc.weizmann.ac.il/report/2019/151