BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Two sets A,B⊆{0,1}n form a Uniquely Decodable Code Pair (UDCP) if every pair a∈A, b∈B yields a distinct sum a+b, where the addition is over Zn. We show that every UDCP A,B, with ∣A∣=2(1−ε)n and ∣B∣=2βn, satisfies β≤0.4228+ε. For sufficiently small ε, this bound significantly improves previous bounds by Urbanke and Li~[Information Theory Workshop '98] and Ordentlich and Shayevitz~[2014, arXiv:1412.8415], which upper bound β by 0.4921 and 0.4798, respectively, as ε approaches 0.
The Subset Sum problem asks whether a given set of n positive integers contains a subset of elements that sum up to a given target t. It is an outstanding open question whether the O∗(2n/2)-time algorithm for Subset Sum by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", O∗(2(0.5−δ)n)-time algorithm, with some constant δ>0. Continuing an earlier work [STACS 2015], we study Subset Sum parameterized by the maximum bin size β, defined as the largest number of subsets of the n input integers that yield the same sum. For every ε>0 we give a truly faster algorithm for instances with β≤2(0.5−ε)n, as well as instances with β≥20.661n. Consequently, we also obtain a characterization in terms of the popular density parameter n/log2t: if all instances of density at least 1.003 admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from novel combinations of earlier algorithms for Subset Sum and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory.
A constraint satisfaction problem (CSP) is said to be \emph{approximation resistant} if it is hard to approximate better than the trivial algorithm which picks a uniformly random assignment. Assuming the Unique Games Conjecture, we give a characterization of approximation resistance for k-partite CSPs defined by an even predicate.
We show improved NP-hardness of approximating Ordering Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove inapproximability of 14/15+ε and 1/2+ε. An OCSP is said to be approximation resistant if it is hard to approximate better than taking a uniformly random ordering. We prove that the Maximum Non-Betweenness Problem is approximation resistant and that there are width-m approximation-resistant OCSPs accepting only a fraction 1/(m/2)! of assignments. These results provide the first examples of approximation-resistant OCSPs subject only to P = \NP.
We study the class of languages, denoted by $\MIP[k, 1-ε, s]$, which have k-prover games where each prover just sends a \emph{single} bit, with completeness 1−ε and soundness error s. For the case that k=1 (i.e., for the case of interactive proofs), Goldreich, Vadhan and Wigderson ({\em Computational Complexity'02}) demonstrate that $\SZK$ exactly characterizes languages having 1-bit proof systems with"non-trivial" soundness (i.e., 1/2<s≤1−2ε). We demonstrate that for the case that k≥2, 1-bit k-prover games exhibit a significantly richer structure: + (Folklore) When s≤2k1−ε, $\MIP[k, 1-ε, s] = \BPP$; + When 2k1+ε≤s<2k2−ε, $\MIP[k, 1-ε, s] = \SZK$; + When s≥2k2+ε, $\AM \subseteq \MIP[k, 1-ε, s]$; + For s≤0.62k/2k and sufficiently large k, $\MIP[k, 1-ε, s] \subseteq \EXP$; + For s≥2k/2k, $\MIP[k, 1, 1-ε, s] = \NEXP$. As such, 1-bit k-prover games yield a natural "quantitative" approach to relating complexity classes such as $\BPP$,$\SZK$,$\AM$, $\EXP$, and $\NEXP$. We leave open the question of whether a more fine-grained hierarchy (between $\AM$ and $\NEXP$) can be established for the case when s≥2k2+ε.
The technique of Schroeppel and Shamir (SICOMP, 1981) has long been the most efficient way to trade space against time for the SUBSET SUM problem. In the random-instance setting, however, improved tradeoffs exist. In particular, the recently discovered dissection method of Dinur et al. (CRYPTO 2012) yields a significantly improved space--time tradeoff curve for instances with strong randomness properties. Our main result is that these strong randomness assumptions can be removed, obtaining the same space--time tradeoffs in the worst case. We also show that for small space usage the dissection algorithm can be almost fully parallelized. Our strategy for dealing with arbitrary instances is to instead inject the randomness into the dissection process itself by working over a carefully selected but random composite modulus, and to introduce explicit space--time controls into the algorithm by means of a "bailout mechanism".
We show that given a satisfiable instance of the 2-to-1 Label Cover problem, it is NP-hard to find a $(23/24 + \eps)$-satisfying assignment.
Recently Raghavendra and Tan (SODA 2012) gave a 0.85-approximation algorithm for the Max Bisection problem. We improve their algorithm to a 0.8776-approximation. As Max Bisection is hard to approximate within αGW+ε≈0.8786 under the Unique Games Conjecture (UGC), our algorithm is nearly optimal. We conjecture that Max Bisection is approximable within αGW−ε, i.e., the bisection constraint (essentially) does not make Max Cut harder. We also obtain an optimal algorithm (assuming the UGC) for the analogous variant of Max 2-Sat. Our approximation ratio for this problem exactly matches the optimal approximation ratio for Max 2-Sat, i.e., αLLZ+ε≈0.9401, showing that the bisection constraint does not make Max 2-Sat harder. This improves on a 0.93-approximation for this problem due to Raghavendra and Tan.
We show that given a 3-colorable graph, it is NP-hard to find a 3-coloring with $(16/17 + \eps)$ of the edges bichromatic. In a related result, we show that given a satisfiable instance of the 2-to-1 Label Cover problem, it is NP-hard to find a $(23/24 + \eps)$-satisfying assignment.
Motivated by the pervasiveness of strong inapproximability results for Max-CSPs, we introduce a relaxed notion of an approximate solution of a Max-CSP. In this relaxed version, loosely speaking, the algorithm is allowed to replace the constraints of an instance by some other (possibly real-valued) constraints, and then only needs to satisfy as many of the new constraints as possible. To be more precise, we introduce the following notion of a predicate P being \emph{useful} for a (real-valued) objective Q: given an almost satisfiable Max-P instance, there is an algorithm that beats a random assignment on the corresponding Max-Q instance applied to the same sets of literals. The standard notion of a nontrivial approximation algorithm for a Max-CSP with predicate P is exactly the same as saying that P is useful for P itself. We say that P is useless if it is not useful for any Q. This turns out to be equivalent to the following pseudo-randomness property: given an almost satisfiable instance of Max-P it is hard to find an assignment such that the induced distribution on k-bit strings defined by the instance is not essentially uniform. Under the Unique Games Conjecture, we give a complete and simple characterization of useful Max-CSPs defined by a predicate: such a Max-CSP is useless if and only if there is a pairwise independent distribution supported on the satisfying assignments of the predicate. It is natural to also consider the case when no negations are allowed in the CSP instance, and we derive a similar complete characterization (under the UGC) there as well. Finally, we also include some results and examples shedding additional light on the approximability of certain Max-CSPs.
In recent work of Hazan and Krauthgamer (SICOMP 2011), it was shown that finding an $\eps$-approximate Nash equilibrium with near-optimal value in a two-player game is as hard as finding a hidden clique of size O(logn) in the random graph G(n,1/2). This raises the question of whether a similar intractability holds for approximate Nash equilibrium without such constraints. We give evidence that the constraint of near-optimal value makes the problem distinctly harder: a simple algorithm finds an optimal 1/2-approximate equilibrium, while finding strictly better than 1/2-approximate equilibria is as hard as the Hidden Clique problem. This is in contrast to the unconstrained problem where more sophisticated algorithms, achieving better approximations, are known. Unlike general Nash equilibrium, which is in PPAD, optimal (maximum value) Nash equilibrium is NP-hard. We proceed to show that optimal Nash equilibrium is just one of several known NP-hard problems related to Nash equilibrium, all of which have approximate variants which are as hard as finding a planted clique. In particular, we show this for approximate variants of the following problems: finding a Nash equilibrium with value greater than η (for any η>0, even when the best Nash equilibrium has value 1−η), finding a second Nash equilibrium, and finding a Nash equilibrium with small support. Finally, we consider the complexity of approximate pure Bayes Nash equilibria in two-player games. Here we show that for general Bayesian games the problem is NP-hard. For the special case where the distribution over types is uniform, we give a quasi-polynomial time algorithm matched by a hardness result based on the Hidden Clique problem.
We study the approximability of a number of graph problems: treewidth and pathwidth of graphs, one-shot black (and black-white) pebbling costs of directed acyclic graphs, and a variety of different graph layout problems such as minimum cut linear arrangement and interval graph completion. We show that, assuming the recently introduced Small Set Expansion Conjecture, all of these problems are hard to approximate within any constant factor.
We present a simple deterministic gap-preserving reduction from SAT to the Minimum Distance of Code Problem over $\F_2$. We also show how to extend the reduction to work over any finite field. Previously a randomized reduction was known due to Dumer, Micciancio, and Sudan, which was recently derandomized by Cheng and Wan. These reductions rely on highly non-trivial coding theoretic constructions whereas our reduction is elementary. As an additional feature, our reduction gives a constant factor hardness even for asymptotically good codes, i.e., having constant rate and relative distance. Previously it was not known how to achieve deterministic reductions for such codes.
We show that it is Unique Games-hard to approximate the maximum of a submodular function to within a factor 0.695, and that it is Unique Games-hard to approximate the maximum of a symmetric submodular function to within a factor 0.739. These results slightly improve previous results by Feige, Mirrokni and Vondrák (FOCS 2007) who showed that these problems are NP-hard to approximate to within 3/4+ε≈0.750 and 5/6+ε≈0.833, respectively.
We study correlation bounds under pairwise independent distributions for functions with no large Fourier coefficients. Functions in which all Fourier coefficients are bounded by δ are called δ-{\em uniform}. The search for such bounds is motivated by their potential applicability to hardness of approximation, derandomization, and additive combinatorics. In our main result we show that $\E[f_1(X_1^1,...,X_1^n) ... f_k(X_k^1,...,X_k^n)]$ is close to 0 under the following assumptions: 1. The vectors {(X1j,...,Xkj):1≤j≤n} are i.i.d, and for each j the vector (X1j,...,Xkj) has a pairwise independent distribution. 2. The functions fi are uniform. 3. The functions fi are of low degree. We compare our result with recent results by the second author for low influence functions and to recent results in additive combinatorics using the Gowers norm. Our proofs extend some techniques from the theory of hypercontractivity to a multilinear setup.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.