We establish deterministic hardness of approximation results for the Shortest Vector Problem in ℓp norm (SVPp) and for Unique-SVP (uSVPp) for all p > 2. Previously, no deterministic hardness results were known, except for ℓ∞.

We give alternate proofs for three related results in analysis of Boolean functions, namely the KKL Theorem, Friedgut’s Junta Theorem, and Talagrand’s strengthening of the KKL Theorem. We follow a new approach: looking at the first Fourier level of the function after a suitable random restriction and applying the Log-Sobolev inequality appropriately. In particular, we avoid using the hypercontractive inequality that is common to the original proofs. Our proofs might serve as an alternate, uniform exposition to these theorems and the techniques might benefit further research.

We prove that pseudorandom sets in the Grassmann graph have near-perfect expansion. This completes the last missing piece of the proof of the 2-to-2-Games Conjecture (albeit with imperfect completeness). The Grassmann graph has induced subgraphs that are themselves isomorphic to Grassmann graphs of lower orders. A set of vertices is called pseudorandom if its density within all such subgraphs (of constant order) is at most slightly higher than its density in the entire graph. We prove that pseudorandom sets have almost no edges within them. Namely, their edge-expansion is very close to 1.

We present a polynomial time reduction from gap-3LIN to label cover with 2-to-1 constraints. In the “yes” case the fraction of satisfied constraints is at least 1 −ε, and in the “no” case we show that this fraction is at most ε, assuming a certain (new) combinatorial hypothesis on the Grassmann graph. In other words, we describe a combinatorial hypothesis that implies the 2-to-1 conjecture with imperfect completeness. The companion submitted paper [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] makes some progress towards proving this hypothesis.

We show a directed and robust analogue of a boolean isoperimetric-type theorem of Talagrand [ Geom. Funct. Anal., 3 (1993), pp. 295--314]. As an application, we give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\varepsilon^2)$ nonadaptive queries to a function $f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function, and rejects a function that is $\varepsilon$-far from being monotone with constant probability.

We present a candidate reduction from the 3-Lin problem to the 2-to-2 Games problem and present a combinatorial hypothesis about Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in a certain non-standard sense. A reduction that is sound in this non-standard sense implies that it is NP-hard to distinguish whether an n-vertex graph has an independent set of size ( 1- 1/√2 ) n - o(n) or whether every independent set has size o(n), and consequently, that it is NP-hard to approximate the Vertex Cover problem within a factor √2-o(1).

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand [13]. As an application, we give a monotonicity testing algorithm that makes O̅(√n/ε2) non-adaptive queries to a function f : {0, 1}n→ {0, 1}, always accepts a monotone function and rejects a function that is ε-far from being monotone with constant probability.

We construct a PCP based on the hyper-graph linearity test with 3 free queries. It has near-perfect completeness and soundness strictly less than 1/8. Such a PCP was known before only assuming the Unique Games Conjecture, albeit with soundness arbitrarily close to 1/16. At a technical level, our main contribution is constructing a new outer PCP which is "robust" against bounded degree polynomials, and showing that it can be composed with the hyper-graph linearity test with 3 free queries. We believe this outer PCP may be useful in obtaining the optimal query vs. soundness tradeoff for PCPs.

We show that for any fixed prime q ≥ 5 and constant ζ >; 0, it is NP-hard to distinguish whether a two prover one round game with q6answers has value at least 1 - ζ or at most 4/q. The result is obtained by combining two techniques: (i) An Inner PCP based on the point versus subspace test for linear functions. The test is analyzed Fourier analytically, (ii) The Outer/Inner PCP composition that relies on a certain sub-code covering property for Hadamard codes. This is a new and essentially black-box method to translate a codeword test for Hadamard codes to a consistency test, leading to a full PCP construction. As an application, we show that unless NP has quasi-polynomial time deterministic algorithms, the Quadratic Programming Problem is inapproximable within factor (log n)1/6-o(1).

This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Consider the task of verifying a written proof for the membership of a given input in an NP language. In this paper, this is achieved by making a constant number of accesses to the proof, obtaining error probability that is exponentially small in the total number of bits that are read. We show that the number of bits that are read in each access to the proof can be made as high as log β n , for any constant β < 1, where n is the length of the proof. The BGLR conjecture asserts the same for any constant β, for β smaller or equal to 1. Our results are in fact stronger, implying that the Gap-Quadratic-Solvability problem with a constant number of variables in each equation is NP-hard. That is, given a system of n quadratic equations over a field $${\mathcal{F}}$$ of size up to $$2^{\log^\beta n}$$ , where each equation depends on a constant number of variables, it is NP-hard to distinguish between the case where there is a common solution to all of the equations and the case where any assignment satisfies at most a $${2 / |\mathcal{F}|}$$ fraction of them. At the same time, our proof presents a direct construction of a low-degree test whose error-probability is exponentially small in the number of bits accessed. Such a result was previously known only relying on recursive applications of the entire PCP theorem.

For every ∈ > 0, and integer q ≥ 3, we show that given an N-vertex graph that has an induced q-colorable subgraph of size (1 - ∈)N, it is NP-hard to find an independent set of size N/q2.

We study the inapproximability of Vertex Cover and Independent Set on degree d graphs. We prove that: (1) Vertex Cover is Unique Games-hard to approximate to within a factor 2 - (2 + od(1)) log log d/log d. This exactly matches the algorithmic result of Halperin up to the od(1) term. (2) Independent Set is Unique Games-hard to approximate to within a factor O(d/log2d). This improves the d/logO(1)(d)) Unique Games hardness result of Samorodnitsky and Trevisan. Additionally, our result does not rely on the construction of a query efficient PCP as in.

An errorless heuristic is an algorithm that on all inputs returns either the correct answer or the special symbol perp, which means "I don't know," A central question in average-case complexity is whether every distributional decision problem in N P has an errorless heuristic scheme: This is an algorithm that, for every delta > 0, runs in time polynomial in the instance size and | / delta and answers perp only on a delta fraction of instances. We study the question from the standpoint of hardness amplification and show that If every problem in (NP,U) has errorless heuristic circuits that output the correct answer on n-2/9+omicron(1)-fraction of inputs, then (NP,U) has non-uniform errorless heuristic schemes. If every problem in (NP,U) has randomized errorless heuristic algorithms that output the correct answer on (log n)-1/10+omicron(1)-fraction of inputs, then (NP.W) has randomized errorless heuristic schemes. In both cases, the low-end amplification is achieved by analyzing a new sensitivity property of monotone boolean Junctions in NP. In the non-uniform setting we use a " holographic Junction" introduced by Benjamini, Schramm, and Wilson (STOC 2005). For the uniform setting we introduce a new Junction that can be viewed as an efficient version of Talagrand's "random DNF".

In [S. Safra, Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, 1988, pp. 319–327] an exponential determinization procedure for Buchi automata was shown, yielding tight bounds for decision procedures of some logics (see [A. E. Emerson and C. Jutla, Proceedings of the 29th IEEE Symposium on Foundations of Computer Science, 1988, pp. 328–337; Safra (1988); S. Safra and M. Y. Vardi, Proceedings of the 21st ACM Symposium on Theory of Computing, 1989, pp. 127–137; and D. Kozen and J. Tiuryn, Logics of program, in Handbook of Theoretical Computer Science, Elsevier, Amsterdam, 1990, pp. 789–840]). In Safra and Vardi (1989) the complexity of determinization and complementation of ω‐automata was further investigated, leaving as an open question the complexity of the determinization of a single class of ω‐automata. For this class of ω‐automata with strong fairness as an acceptance condition (Streett automata), Safra and Vardi (1989) managed to show an exponential complementation procedure; however, the blow‐up of translating these automata—to any of the classes known to admit exponential determinization—is inherently exponential. This might suggest that the blow‐up of the determinization of Streett automata is inherently doubly exponential. This paper shows an exponential determinization construction for Streett automata. In fact, the complexity of our construction is roughly the same as the complexity achieved in Safra (1988) for Buchi automata. Moreover, a simple observation extends this upper bound to the complementation problem. Since any ω‐automaton that admits exponential determinization can be easily converted into a Streett automaton, we have obtained a single procedure that can be used for all of these conversions. Furthermore, this construction is optimal (up to a constant factor in the exponent) for all of these conversions. Our results imply that Streett automata (with strong fairness as an acceptance condition) can be used instead of Buchi automata (with the weaker acceptance condition) without any loss of efficiency.

This work addresses k-restriction problems , which unify combinatorial problems of the following type: The goal is to construct a short list of strings in Σ m that satisfies a given set of k -wise demands. For every k positions and every demand, there must be at least one string in the list that satisfies the demand at these positions. Problems of this form frequently arise in different fields in Computer Science.The standard approach for deterministically solving such problems is via almost k -wise independence or k -wise approximations for other distributions. We offer a generic algorithmic method that yields considerably smaller constructions. To this end, we generalize a previous work of Naor et al. [1995]. Among other results, we enhance the combinatorial objects in the heart of their method, called splitters, and construct multi-way splitters , using a new discrete version of the topological Necklace Splitting Theorem [Alon 1987].We utilize our methods to show improved constructions for group testing [Ngo and Du 2000] and generalized hashing [Alon et al. 2003], and an improved inapproximability result for SET-COVER under the assumption P ≠ NP .

This paper studies the computational complexity of the following type of quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find x /spl isin/ {-1, 1}/sup n/ that maximizes x/sup T/Mx. This problem recently attracted attention due to its application in various clustering settings, as well as an intriguing connection to the famous Grothendieck inequality. It is approximable to within a factor of O(log n), and known to be NP-hard to approximate within any factor better than 13/11 - /spl epsi/ for all /spl epsi/ > 0. We show that it is quasi-NP-hard to approximate to a factor better than O(log/sup /spl gamma// n)for some /spl gamma/ > 0. The integrality gap of the natural semidefinite relaxation for this problem is known as the Grothendieck constant of the complete graph, and known to be /spl Theta/(log n). The proof of this fact was nonconstructive, and did not yield an explicit problem instance where this integrality gap is achieved. Our techniques yield an explicit instance for which the integrality gap is /spl Omega/ (log n/log log n), essentially answering one of the open problems of Alon et al. [AMMN].

We introduce a unifying framework for proving that predicate P is hard-core for a one-way function f, and apply it to a broad family of functions and predicates, reproving old results in an entirely different way as well as showing new hard-core predicates for well known one-way function candidates. Our framework extends the list-coding method of Goldreich and Levin for showing hard-core predicates. Namely, a predicate will correspond to some error correcting code, predicting a predicate will correspond to access to a corrupted codeword, and the task of inverting one-way functions will correspond to the task of list decoding a corrupted codeword. A characteristic of the error correcting codes which emerge and are addressed by our framework is that codewords can be approximated by a small number of heavy coefficients in their Fourier representation. Moreover, as long as corrupted words are close enough to legal codewords, they will share a heavy Fourier coefficient. We list decodes, by devising a learning algorithm applied to corrupted codewords for learning heavy Fourier coefficients. For codes defined over {0, 1}/sup n/ domain, a learning algorithm by Kushilevitz and Mansour already exists. For codes defined over Z/sub N/, which are the codes which emerge for predicates based on number theoretic one-way functions such as the RSA and Exponentiation modulo primes, we develop a new learning algorithm. This latter algorithm may be of independent interest outside the realm of hard-core predicates.

We show that a Boolean function over n Boolean variables can be tested for the property of depending on only k of them, using a number of queries that depends only on k and the approximation parameter /spl epsi/. We present two tests, both non-adaptive, that require a number of queries that is polynomial k and linear in /spl epsi//sup -1/. The first test is stronger in that it has a 1-sided error, while the second test has a more compact analysis. We also present an adaptive version and a 2-sided error version of the first test, that have a somewhat better query complexity than the other algorithms. We then provide a lower bound of /spl Omega//spl tilde/(/spl radic/ k) on the number of queries required for the non-adaptive testing of the above property; a lower bound of /spl Omega/(log(k + 1)) for adaptive algorithms naturally follows from this. In providing this we also prove a result about random walks on the group Z/sub 2//sup q/ that may be interesting in its own right. We show that for some t(q) = O/spl tilde/(q/sup 2/), the distributions of the random walk at times t and t + 2 are close to each other, independently of the step distribution of the walk. We also discuss related questions. In particular, when given in advance a known k junta function h, we show how to test a function f for the property of being identical to h up to a permutation of the variables, in a number of queries that is polynomial in k and /spl epsi/.

We prove complexity, approximability, and inapproximability results for the problem of finding an exchange equilibrium in markets with indivisible (integer) goods, most notably a polynomial-time algorithm that approximates the market equilibrium arbitrarily closely when the number of goods is bounded and the utilities are linear. We also show a communication complexity lower bound, implying that the ideal informational economy of a market with unique individual optima is unattainable in general.

(MATH) We show that the Minimum Vertex Cover problem is NP-hard to approximate to within any factor smaller than $10\sqrt{5}-21 \approx 1.36067$, improving on the previously known hardness result for a $\frac{7}{6}$ factor.

Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. Previous research has focused on two approaches, one related to hashing and the other to pseudorandom generators. A third view, regarding extractors as good error correcting codes, was noticed before. Yet, researchers had failed to build extractors directly from a good code without using other tools from pseudorandomness. We succeed in constructing an extractor directly from a Reed-Muller code. To do this, we develop a novel proof technique. Furthermore, our construction is the first to achieve a degree close to linear. In contrast, the best previous constructions brought the log of the degree within a constant of optimal, which gives polynomial degree. This improvement is important for certain applications. For example, it follows that approximating the VC dimension to within a factor of N/sup 1-/spl delta// is AM-hard for any positive /spl delta/.

The current proof of the probabilistically checkable proofs (PCP) theorem (i.e., ${\cal NP}={\cal PCP}(\log,O(1))$) is very complicated. One source of difficulty is the technically involved analysis of low-degree tests. Here, we refer to the difficulty of obtaining strong results regarding low-degree tests; namely, results of the type obtained and used by Arora and Safra [J. ACM, 45 (1998), pp. 70--122] and Arora et al. [J. ACM, 45 (1998), pp. 501--555]. In this paper, we eliminate the need to obtain such strong results on low-degree tests when proving the PCP theorem. Although we do not remove the need for low-degree tests altogether, using our results it is now possible to prove the PCP theorem using a simpler analysis of low-degree tests (which yields weaker bounds). In other words, we replace the strong algebraic analysis of low-degree tests presented by Arora and Safra and Arora et al. by a combinatorial lemma (which does not refer to low-degree tests or polynomials).

This paper strengthens the law-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture.Namely, we prove that witnesses for membership in any NP language can be verified with a constant nunbcr of accesses, and with an error probability exponentially small in the number of bits accessed, where this number is as high as lagan, for any constant fl < 1. (The BGLR conjecture claims the same for any p 5 1).Our results are in fact stronger, implying the Gap-Quadratic-Solvability problem to be NP-hard even if the equations are restricted to having a constant number of variables.That is, given a system of quadratic-equations over a field 3 (of size up to ZLogD"), where each equation depends on a constant number of variables, it is NP-hard to decide between the case where there is a common solution for all of the equations, and the case where any assignment satisfies no more than a & fraction of them.At the same time, ow proof presents a direct eonstmction of a low-degree-test whose error-probability is expancntially small in the number of hits accessed.Such a result was previously known only relying on recursive applications of the entire PCP theorem.

This paper shows the closest vector in a lattice to be NP-hard to approximate to within any factor up to 2/sup (logn)1-4/ where /spl epsiv/=(loglogn)/sup -c/ for any constant c< 1/2.

We give a new characterization of NP: the class NP contains exactly those languages L for which membership proofs (a proof that an input x is in L ) can be verified probabilistically in polynomial time using logarithmic number of random bits and by reading sublogarithmic number of bits from the proof. We discuss implications of this characterization; specifically, we show that approximating Clique and Independent Set, even in a very weak sense, is NP-hard.

We introduce a new low-degree--test, one that uses the restriction of low-degree polynomials to planes (i.e., affine sub-spaces of dimension 2), rather than the restriction to lines (i.e., affine sub-spaces of dimension 1). We prove the new test to be of a very small errorprobability (in particular, much smaller than constant). The new test enables us to prove a low-error characterization of NP in terms of PCP. Specifically, our theorem states that, for any given ffl ? 0, membership in any NP language can be verified with O(1) accesses, each reading logarithmic number of bits, and such that the error-probability is 2 \\Gamma log 1\\Gammaffl n . Our results are in fact stronger, as stated below. One application of the new characterization of NP is that approximating SET-COVER to within a logarithmic factors is NP-hard. Previous analysis for low-degree-tests, as well as previous characterizations of NP in terms of PCP, have managed to achieve, with constant number of accesses, error...

In the automata-theoretic approach to verification, we translate specifications to automata. Complexity considerations motivate the distinction between different types of automata. Already in the 60's, it was known that deterministic Buchi word automata are less expressive than nondeterministic Buchi word automata. The proof is easy and can be stated in a few lines. In the late 60's, Rabin proved that Buchi tree automata are less expressive than Rabin tree automata. This proof is much harder. In this work we relate the expressiveness gap between deterministic and nondeterministic Buchi word automata and the expressiveness gap between Buchi and Rabin tree automata. We consider tree automata that recognize derived languages. For a word language L, the derived language of L, denoted L/spl Delta/, is the set of all trees all of whose paths are in L. Since often we want to specify that all the computations of the program satisfy some property, the interest in derived languages is clear. Our main result shows that L is recognizable by a nondeterministic Buchi word automaton but not by a deterministic Buchi word automaton iff L/spl Delta/ is recognizable by a Rabin tree automaton and not by a Buchi tree automaton. Our result provides a simple explanation to the expressiveness gap between Buchi and Rabin tree automata. Since the gap between deterministic and nondeterministic Buchi word automata is well understood, our result also provides a characterization of derived languages that can be recognized by Buchi tree automata. Finally, it also provides an exponential determinization of Buchi tree automata that recognize derived languages.

The contribution of this paper is two-fold. First, a connection is established between approximating the size of the largest clique in a graph and multi-prover interactive proofs. Second, an efficient multi-prover interactive proof for NP languages is constructed, where the verifier uses very few random bits and communication bits. Last, the connection between cliques and efficient multi-prover interaction proofs, is shown to yield hardness results on the complexity of approximating the size of the largest clique in a graph. Of independent interest is our proof of correctness for the multilinearity test of functions.

In this paper we consider two-party communication complexity, the "asymmetric case", when the input sizes of the two players differ significantly. Most of previous work on communication complexity only considers the total number of bits sent, but we study trade-offs between the number of bits the first player sends and the number of bits the second sends. These types of questions are closely related to the complexity of static data structure problems in the cell probe model. We derive two generally applicable methods of proving lower bounds and obtain several applications. These applications include new lower bounds for data structures in the cell probe model. Of particular interest is our "round elimination" lemma, which is interesting also for the usual symmetric communication case. This lemma generalizes and abstracts in a very clean form the "round reduction" techniques used in many previous lower bound proofs.

This paper introduces a framework for Planning while Learning where an agent is given a goal to achieve in anenvironment whose behavior is only partially known to the agent. We discuss the tractability of various plan-design processes. We show that for a large natural class of Planning while Learning systems, a plan can be presented and verified in a reasonable time. However, coming up algorithmically with a plan, even for simple classes of systems is apparently intractable. We emphasize the role of off-line plan-design processes, andshow that, in most natural cases, the verification (projection) part canbe carried out in an efficient algorithmic manner.

The authors give a new characterization of NP: the class NP contains exactly those languages L for which membership proofs (a proof that an input x is in L) can be verified probabilistically in polynomial time using logarithmic number of random bits and sub-logarithmic number of queries to the proof. This is a non-relativizing characterization of NP. They discuss implications of this characterization; specifically, they show that approximating clique (or independent set) is NP-hard.>

In [Saf88] an exponential determination procedure for Bu¨chi automata was shown, yielding tight bounds for decision procedures of some logics ([EJ88, Saf88, SV89, KT89]). In [SV89] the complexity of determinization and complementation of ω-automata was further investigated, leaving as an open question the complexity of the determinization of a single class of ω-automata. For this class of ω-automata with strong fairness as acceptance condition (Street automata), [SV89] managed to show an exponential complementation procedure, but showed that the blow-up of the translation of these automata to any of the classes known to admit exponential determinization is inherently exponential. This might suggest that the blow-up of the determinization of Street automata is inherently doubly exponential.

The computational complexity of approximating omega (G), the size of the largest clique in a graph G, within a given factor is considered. It is shown that if certain approximation procedures exist, then EXPTIME=NEXPTIME and NP=P.>

We study here the use of different representation for infinitary regular languages in extended temporal logic. We focus on three different kinds of acceptance conditions for finite automata on infinite words, due to Büchi, Streett, and Emerson and Lei (EL), and we study their computational properties. Our finding is that Büchi, Streett, and EL automata span a spectrum of succinctness. EL automata are exponentially more succinct than Büchi automata, and complementation of EL automata is doubly exponential. Streett automata are of intermediate complexity. While translating from Streett automata to Büchi automata involves an exponential blow-up, so does the translation from EL automata to Streett automata. Furthermore, even though Streett automata are exponentially more succinct than Büchi automata, complementation of Streett automata is only exponential. As a result, we show that the decision problem for ETLEL, where temporal connectives are represented by EL automata, is EXPSPACE-complete, and the decision problem for ETLS, where temporal connectives are represented by Streett automata, is PSPACE-complete.

Automata on infinite words were introduced by J.R. Buchi (1962) in order to give a decision procedure for S1S, the monadic second-order theory of one successor. D.E. Muller (1963) suggested deterministic omega -automata as a means of describing the behavior of nonstabilising circuits. R. McNaughton (1966) proved that classes of languages accepted by nondeterministic Buchi automata and by deterministic Muller automata are the same. His construction and its proof are quite complicated, and the blow-up of the construction is double exponential. The author presents a determinisation construction that is simpler and yields a single exponent upper bound for the general case. This construction is essentially optimal. It can also be used to obtain an improved complementation construction for Buchi automata that is also optimal. Both constructions can be used to improve the complexity of decision procedures that use automata-theoretic techniques.>