Author(s): Holger Dell (U Wisconsin, Madison), Valentine Kabanets (Simon Fraser U.), Dieter van Melkebeek (U Wisconsin, Madison), Osamu Watanabe (Tokyo Institute of Technology).
Abstract: The Valiant-Vazirani Isolation Lemma [TCS, vol. 47, pp. 85{93, 1986] provides an efficient procedure for isolating a satisfying assignment of a given satisfiable circuit: given a Boolean circuit C on n input variables, the procedure outputs a new circuit C' on the same n input variables with the property that the set of satisfying assignments for C' is a subset of those for C, and moreover, if C is satis able then C' has exactly one satisfying assignment. The Valiant-Vazirani procedure is randomized, and it produces a uniquely satisfiable circuit C' with probability > \Omega(1/n). Is it possible to have an efficient deterministic witness-isolating procedure? Or, at least, is it possible to improve the success probability of a randomized procedure to >\Omega(1)?We argue that the answer is likely `No'. More precisely, we prove that there exists a non-uniform randomized polynomial-time witness-isolating procedure with success probability bigger than 2/3 if and only if NP\subset P/poly. Thus, an improved witness-isolating procedure would imply the collapse of the polynomial-time hierarchy. We establish similar results for other variants of witness isolation.
Finally, we consider a black-box setting of witness isolation (generalizing the setting of the Valiant-Vazirani Isolation Lemma), and give the upper bound O(1/n) on the success probability for a natural class of randomized witness-isolating procedures.
Author(s): Yuichi Yoshida (Kyoto University and Preferred Infrastructure, Inc.)
Abstract: Let H be an undirected graph. In the List H-Homomorphism Problem, given an undirected graph G with a list constraint L(v) \subseteq V(H) for each variable v \in V(G), the objective is to find a list H-homomorphism f:V(G) \to V(H), that is, f(v) \in L(v) for every v \in V(G) and (f(u),f(v)) \in E(H) whenever (u,v) \in E(G). We consider testing list H-homomorphism: given a map f:V(G) \to V(H) as an oracle access, the objective is to decide with high probability whether f is a list H-homomorphism or far from any list H-homomorphisms. The efficiency of an algorithm is measured by the number of accesses to f. In this paper, we classify graphs H with respect to the query complexity for testing list H-homomorphisms, and we show that the following trichotomy holds: (i) List H-homomorphisms are testable with a constant number of queries if and only if H is a reflexive complete graph or an irreflexive complete bipartite graph. (ii) List H-homomorphisms are testable with a sublinear number of queries if and only if H is a bi-arc graph. (iii) Testing list H-homomorphisms requires a linear number of queries if H is not a bi-arc graph.
Author(s): Sangxia Huang (KTH Royal Institute of Technology), Pinyan Lu (Microsoft Research Asia)
Abstract: Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as #CSP and Graph Homomorphism. An effective dichotomy for such frameworks can settle simultaneously the complexity of all combinatorial problems expressible in that framework. Both #CSP and Graph Homomorphism can be viewed as sub-families of Holant with the additional assumption that the equality constraints are always available. Other sub-families of Holant such as Holant^* and Holant^c problems, in which we assume some specific sets of constraints to be freely available, were also studied. The Holant framework becomes more expressive and contains more interesting tractable cases with less or no freely available constraint functions, while, on the other hand, it also becomes more challenging to obtain a complete characterization of its time complexity. Recently, complexity dichotomy for a variety of sub-families of Holant such as #CSP, Graph Homomorphism, Holant^* and Holant^c were proved. The dichotomy for the general Holant framework, which is the most desirable, still remains open. In this paper, we prove a dichotomy for the general Holant framework where all the constraints are real symmetric functions. This setting already captures most of the interesting combinatorial problems defined by local constraints, such as (perfect) matching, independent set, vertex cover and so on. This is the first time a dichotomy is obtained for general Holant Problems without any auxiliary functions.One benefit of working with Holant framework is some powerful new reduction techniques such as Holographic reduction. Along the proof of our dichotomy, we introduce a new reduction technique, namely realizing a constraint function by approximating it. This new technique is employed in our proof in a situation where it seems that all previous reduction techniques fail, thus this new idea of reduction might also be of independent interest. Besides proving dichotomy and developing new technique, we also obtained some interesting by-products. We prove a dichotomy for #CSP restricting to instances where each variable appears a multiple of d times for any d. We also prove that counting the number of Eulerian-Orientations on 2k-regular graphs is #P-hard for any k>= 2.
Author(s): Or Meir (Stanford University)
Abstract: The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the discovery of the theorem, there has been a considerable work on improving the theorem in terms of the length of the proofs, culminating in the construction of PCPs of quasi-linear length, by Ben-Sasson and Sudan (SICOMP 38(2)) and Dinur (J. ACM 54(3)).One common theme in the aforementioned PCP constructions is that they all rely heavily on sophisticated algebraic machinery. The aforementioned work of Dinur (J. ACM 54(3)) suggested an alternative approach for constructing PCPs, which gives a simpler and arguably more intuitive proof of the PCP theorem using combinatorial techniques. However, this combinatorial construction only yields PCPs of polynomial length, and is therefore inferior to the algebraic constructions in this respect. This gives rise to the natural question of whether the proof length of the algebraic constructions can be matched using the combinatorial approach.
In this work, we provide a combinatorial construction of PCPs of length n*log(n)^O(loglog(n)) , coming very close to the state of the art algebraic constructions, whose proof length is n*polylog(n). To this end, we develop a few generic PCP techniques which may be interesting in their own right.
It should be mentioned that our construction does use low degree polynomials at one point. However, our use of polynomials is confined to the construction of error correcting codes with a certain simple multiplication property, and it is conceivable that such codes can be constructed without the use of polynomials.
Author(s): Chi-Jen Lu (Academia Sinica)
Abstract: We consider the problem of constructing hitting set generators for sparse multivariate polynomials over any finite fields. Hitting set generators, just as pseudorandom generators, play a fundamental role in the study of derandomization. Pseudorandom generators with a logarithmic seed length are only known for polynomials of constant degrees. On the other hand, hitting set generators with a logarithmic seed length are known for polynomials of larger degrees, but only over fields which are much larger than the degrees. Our main result is the construction of a hitting set generator with a seed length of $O(\log s)$, which works for $s$-term polynomials of any degrees over any finite fields of constant size. This gives the first optimal hitting set generator which allows the fields to be smaller than the degrees of polynomials. For larger fields, of non-constant size, we provide another hitting set generator with a seed length of $O(\log (sd))$, which works for $s$-term polynomials of any degree $d$, as long as $d$ is slightly smaller than the field size.
Author(s): Ran Raz (Weizmann Institute), Ricky Rosen (Princeton University)
Abstract: The parallel repetition theorem states that for any Two Prover Game with value at most 1- epsilon (for epsilon<1/2), the value of the game repeated n times in parallel is at most (1-epsilon^3)^(Omega(n/s)), where s is the length of the answers of the two provers [Raz STOC '95, Holenstein STOC '07]. For Projection Games, the bound on the value of the game repeated n times in parallel was improved to (1-epsilon^2)^(Omega(n)) [Rao STOC '08] and this bound was shown to be tight [Raz FOCS '08].In this paper we study the case where the underlying distribution, according to which the questions for the two provers are generated, is uniform over the edges of a (bipartite) expander graph.
We show that if lambda is the (normalized) spectral gap of the underlying graph, the value of the repeated game is at most (1-epsilon^2)^(Omega(c(lambda) n/ s)), where c(lambda) = poly(lambda); and if in addition the game is a projection game, we obtain a bound of (1-epsilon)^(Omega( c(lambda) n)), where c(lambda) = poly(lambda), that is, a strong parallel repetition theorem (when lambda is constant).
This gives a strong parallel repetition theorem for a large class of two prover games.
Author(s): Elena Grigorescu and Chris Peikert (Georgia Institute of Technology)
Abstract: The question of *list decoding* error-correcting codes over finite fields (under the Hamming metric) has been widely studied in recent years. Motivated by the similar discrete structure of linear codes and *point lattices* in R^N, and their many shared applications across complexity theory, cryptography, and coding theory, we initiate the study of list decoding for lattices. Namely: for a lattice L in R^N, given a target vector r in R^N and a distance parameter d, output the set of all lattice points w in L that are within distance d of r.In this work we focus on combinatorial and algorithmic questions related to list decoding for the well-studied family of *Barnes-Wall* lattices. Our main contributions are twofold:
1. We give tight (up to polynomials) combinatorial bounds on the worst-case list size, showing it to be polynomial in the lattice dimension for any error radius bounded away from the lattice's minimum distance (in the Euclidean norm).
2. Building on the *unique* decoding algorithm of Micciancio and Nicolosi (ISIT '08), we give a list-decoding algorithm that runs in time polynomial in the lattice dimension and worst-case list size, for any error radius. Moreover, our algorithm is highly parallelizable, and with sufficiently many processors can run in parallel time only *poly-logarithmic* in the lattice dimension.
In particular, our results imply a polynomial-time list-decoding algorithm for any error radius bounded away from the minimum distance, thus beating a typical barrier for error correcting codes posed by the Johnson radius.
Author(s): Markus Bläser (Saarland University), Bekhan Chokaev (Moscow State University)
Abstract: We prove that an associative algebra A has minimal rank if and only if the Alder-Strassen bound is also tight for the multiplicative complexity of A, that is, the multiplicative complexity of A is 2 dim A - t_A, where t_A denotes the number of maximal twosided ideals of A. This generalizes a result by E. Feig who proved this for division algebras. Furthermore, we show that if A is local or superbasic, then every optimal quadratic computation for A is almost bilinear.
Author(s): Gus Gutoski (University of Waterloo), Xiaodi Wu (University of Michigan)
Abstract: This paper presents an efficient parallel algorithm for a new class of min-max problems based on the matrix multiplicative weights update method. Our algorithm can be used to find near-optimal strategies for competitive two-player classical or quantum games in which a referee exchanges any number of messages with one player followed by any number of additional messages with the other. This algorithm considerably extends the class of games which admit parallel solutions, demonstrating for the first time the existence of a parallel algorithm for a game in which one player reacts adaptively to the other. As a consequence, we prove that several competing-provers complexity classes collapse to PSPACE such as QRG(2), SQG and two new classes called DIP and DQIP. A special case of our result is a parallel approximation scheme for a new class of semidefinite programs whose feasible region consists of n-tuples of semidefinite matrices that satisfy a "transcript-like" consistency condition. Applied to this special case, our algorithm yields a direct polynomial-space simulation of multi-message quantum interactive proofs resulting in a first-principles proof of QIP=PSPACE.
Author(s): Troy Lee (Centre for Quantum Technologies), Jérémie Roland (Université Libre de Bruxelles)
Abstract: We show that quantum query complexity satisfies a strong direct product theorem. This means that computing k copies of a function with less than k times the quantum queries needed to compute one copy of the function implies that the overall success probability will be exponentially small in k. For a boolean function f we also show an XOR lemma---computing the parity of k copies of f with less than k times the queries needed for one copy implies that the advantage over random guessing will be exponentially small. We do this by showing that the multiplicative adversary method, which inherently satisfies a strong direct product theorem, is always at least as large as the additive adversary method, which is known to characterize quantum query complexity.
Author(s): André Chailloux (UC Berkeley, California), Or Sattath (Hebrew University of Jerusalem)
Abstract: We study variants of the canonical Local-Hamiltonian problem where, in addition, the witness is promised to be separable. We define two variants of the Local-Hamiltonian problem. The input for the Separable-Local-Hamiltonian problem is the same as the Local-Hamiltonian problem, i.e. a local Hamiltonian and two energies a and b, but the question is somewhat different: the answer is YES if there is a separable quantum state with energy at most a, and the answer is NO if all separable quantum states have energy at least b. The Separable-Sparse-Hamiltonian problem is defined similarly, but the Hamiltonian is not necessarily local, but rather sparse. We show that the Separable-Sparse-Hamiltonian problem is QMA(2)-Complete, while Separable-Local-Hamiltonian is in QMA. This should be compared to the Local-Hamiltonian problem, and the Sparse-Hamiltonian problem which are both QMA-Complete. To the best of our knowledge, Separable-SPARSE-Hamiltonian is the first non-trivial problem shown to be QMA(2)-Complete.
Author(s): Gil Cohen and Ran Raz (Weizmann Institute), Gil Segev (MSR Silicon Valley)
Abstract: Motivated by the classical problem of privacy amplification, Dodis and Wichs [STOC09] introduced the notion of a non-malleable extractor, significantly strengthening the notion of a strong extractor.A non-malleable extractor is a function $\nmExt : \{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m$ that takes two inputs: a weak source $W$ and a uniform (independent) seed $S$, and outputs a string $\nmExt(W,S)$ that is nearly uniform given $S$ as well as $\nmExt(W, S')$ for any seed $S' \neq S$ that is determined as an arbitrary function of $S$.
The first explicit construction of a non-malleable extractor was recently provided by Dodis, Li, Wooley and Zuckerman [FOCS11]. Their extractor works for any weak source with min-entropy rate $1/2 + \delta$, where $\delta > 0$ is an arbitrary constant, and outputs up to a linear number of bits, but suffers from two drawbacks. First, the length of its seed is linear in the length of the weak source (which leads to privacy amplification protocols with high communication complexity). Second, the construction is conditional: when outputting more than a logarithmic number of bits (as required for privacy amplification protocols) its efficiency relies on a longstanding conjecture on the distribution of prime numbers.
In this paper we present an unconditional construction of a non-malleable extractor with short seeds. For any integers $n$ and $d$ such that $2.01 \cdot \log{n} \le d \le n$, we present an explicit construction of a non-malleable extractor $\nmExt \colon \{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m$, with $m=\Omega(d)$, and error exponentially small in $m$. The extractor works for any weak source with min-entropy rate $1/2 + \delta$, where $\delta > 0$ is an arbitrary constant.
Moreover, our extractor in fact satisfies an even more general notion of non-malleability: its output $\nmExt(W,S)$ is nearly uniform given the seed $S$ as well as the values $\nmExt(W, S_1), \ldots, \nmExt(W, S_t)$ for several seeds $S_1, \ldots, S_t$ that may be determined as an arbitrary function of $S$, as long as $S \notin \{S_1, \ldots, S_t\}$.
By instantiating the framework of Dodis and Wichs with our non-malleable extractor, we obtain the first 2-round privacy amplification protocol for min-entropy rate $1/2 + \delta$ with asymptotically optimal entropy loss and poly-logarithmic communication complexity. This improves the previously known 2-round privacy amplification protocols: the protocol of Dodis and Wichs whose entropy loss is not asymptotically optimal, and the protocol of Dodis, Li, Wooley and Zuckerman whose communication complexity is linear.
Author(s): Noga Alon (Tel Aviv University), Amir Shpilka (Technion), Christopher Umans (Caltech)
Abstract: We present several variants of the sunflower conjecture of Erdos and Rado [ER60] and discuss the relations among them.We then show that two of these conjectures (if true) imply negative answers to questions of Coppersmith and Winograd [CW90] and Cohn et al [CKSU05] regarding possible approaches for obtaining fast matrix multiplication algorithms. Specifically, we show that the Erdos-Rado sunflower conjecture (if true) implies a negative answer to the "no three disjoint equivoluminous subsets'" question of Coppersmith and Winograd [CW90]; we also formulate a "multicolored'" sunflower conjecture in Z_3^n and show that (if true) it implies a negative answer to the "strong USP'" conjecture of [CKSU05] (although it does not seem to impact a second conjecture in [CKSU05] or the viability of the general group-theoretic approach). A surprising consequence of our results is that the Coppersmith-Winograd conjecture actually implies the Cohn et al. conjecture.
The multicolored sunflower conjecture in Z_3^n is a strengthening of the well-known (ordinary) sunflower conjecture in Z_3^n, and we show via our connection that a construction from [CKSU05] yields a lower bound of (2.51...)^n on the size of the largest {\em multicolored} 3-sunflower-free set, which beats the current best known lower bound of (2.21...)^n [Edel04] on the size of the largest 3-sunflower-free set in Z_3^n.
Author(s): Amnon Ta-Shma (Tel-Aviv University), Christopher Umans (Caltech)
Abstract: We give a new construction of condensers based on Parvaresh-Vardy codes [PV05]. Our condensers have entropy rate (1 - \alpha) for subconstant \alpha (in contrast to [GUV09] which required constant \alpha) and suffer only sublinear entropy loss.Known extractors can be applied to the output to extract all but a subconstant fraction of the minentropy. The resulting (k, \eps) extractor E:{0,1}^n x {0,1}^d -> {0,1}^m has output length m = (1 - \alpha)k with \alpha = 1/polylog(n), and seed length d = O(log n), when \eps> 1/2^{log^\beta n} for any constant \beta< 1. Thus we achieve the same "world-record" extractor parameters as [DKSS09], with a more direct construction.
Author(s): Baris Aydinlioglu (University of Wisconsin-Madison), Dieter van Melkebeek (University of Wisconsin-Madison)
Abstract: Hardness against nondeterministic circuits is known to suffice for derandomizing Arthur-Merlin games. We show a result in the other direction -- that hardness against nondeterministic circuits is *necessary* for derandomizing Arthur-Merlin games. In fact, we obtain an equivalence for a mild notion of derandomization: Arthur-Merlin games can be simulated in Sigma2-SUBEXP (the subexponential version of Sigma2-P) with linear advice on infinitely many input lengths if and only if Sigma2-E (the linear-exponential version of Sigma2-P) requires nondeterministic circuits of superpolynomial size on infinitely many input lengths.Our equivalence result represents a full analogue of a similar result by Impagliazzo et al. in the deterministic setting: randomized polynomial-time decision procedures can be simulated in NSUBEXP (the subexponential version of NP) with linear advice on infinitely many input lengths if and only if NE (the linear-exponential version of NP) requires deterministic circuits of superpolynomial size on infinitely many input lengths.
A key ingredient in our proofs is improved Karp-Lipton style collapse results for nondeterministic circuits. The following are two instantiations that may be of independent interest: Assuming that Arthur-Merlin games can be derandomized in Sigma2-P, we show that (i) if coNP is contained in NP/poly then PH collapses to P^{Sigma2-P}, and (ii) if PSPACE is contained in NP/poly then PSPACE collapses to Sigma2-P.
Author(s): Samuel R. Buss (University of California, San Diego), Ryan Williams (Stanford University)