| 1. |
- Håstad, Johan, et al.
(författare)
-
A smaller sleeping bag for a baby snake
- 2001
-
Ingår i: Discrete & Computational Geometry. - : Springer Science and Business Media LLC. - 0179-5376 .- 1432-0444. ; 26:1, s. 173-181
-
Tidskriftsartikel (refereegranskat)abstract
- By a sleeping bag for a baby snake in d dimensions we mean a subset of Rd which can cover, by rotation and translation, every curve of unit length. We construct sleeping bags which are smaller than any previously known in dimensions 3 and higher. In particular, we construct a three-dimensional sleeping bag of volume approximately 0.075803. For large d we construct d-dimensional sleeping bags with volume less than (cvlog d)d/d3d/2 for some constant c. To obtain the last result, we show that every curve of unit length in Rd lies between two parallel hyperplanes at distance at most C1d-3/2vlog d, for some constant c1.
|
|
| 2. |
- Andersson, Arne, et al.
(författare)
-
Tight bounds for searching a sorted array of strings
- 2000
-
Ingår i: SIAM journal on computing (Print). - 0097-5397 .- 1095-7111. ; 30:5, s. 1552-1578
-
Tidskriftsartikel (refereegranskat)abstract
- Given a k-character query string and an array of n strings arranged in lexicographical order, computing the rank of the query string among the n strings or deciding whether it occurs in the array requires the inspection [GRAPHICS] characters in the worst case.
|
|
| 3. |
- Andersson, G., et al.
(författare)
-
A new way of using semidefinite programming with applications to linear equations mod p
- 2001
-
Ingår i: Journal of Algorithms. - : Elsevier BV. - 0196-6774 .- 1090-2678. ; 39:2, s. 162-204
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce a new method of constructing approximation algorithms for combinatorial optimization problems using semidefinite programming. It consists of expressing each combinatorial object in the original problem as a constellation of vectors in the semidefinite program. When we apply this technique to systems of linear equations mod p with at most two variables in each equation, we can show that the problem is approximable within (1 - kappa (p))p, where kappa (p)> 0 for all p. Using standard techniques we also show that it is NP-hard to approximate the problem within a constant ratio, independent of p.
|
|
| 4. |
- Aumann, Y., et al.
(författare)
-
Linear-consistency testing
- 2001
-
Ingår i: Journal of computer and system sciences (Print). - : Elsevier BV. - 0022-0000 .- 1090-2724. ; 62:4, s. 589-607
-
Tidskriftsartikel (refereegranskat)abstract
- We extend the notion of linearity testing to the task of checking linear consistency of multiple functions. Informally, functions are linear if their graphs form straight lines on the plane. Two such functions are consistent if the lines have the same slope. We propose a variant of a test of M. Blum et al. (J. Comput. System Sci. 47 (1993), 549-595) to check the linear consistency of three functions f(1). f(2). f(3) mapping a finite Abelian group G to an Abelian group H: Pick x, y is an element of G uniformly and independently at random and check if f(1)(x) + f(2)(y) = f(3)(x + y). We analyze this test for two cases: (1) G and H are arbitrary Abelian groups and (2) G = F-2(n) and H = F-2. Questions bearing close relationship to linear-consistency testing seem to hav e been implicitly considered in recent work on the construction of PCPs and in particular in the work of J. Hastad [9] (in Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing. El Paso. Texas, 4-6 May 1997, pp. 1-10). It is abstracted explicitly for the first time here. As an application of our results we give yet another new and tight characterization of NP. namely For All epsilon > 0, NP = MIP1-epsilon 1/2 [O(log n), 3, 1]. That is, every language in NP has 3-prover 1-round proof systems in which the verifier tosses O(log n) coins and asks each of the three provers one question each. The provers respond with one bit each such that the verifier accepts instance of the language with probability 1 - epsilon and rejects noninstances with probability at least;. Such a result is of some interest in the study of probabilistically checkable proofs.
|
|
| 5. |
- Austrin, Per, et al.
(författare)
-
(2 + epsilon)-Sat Is NP-hard
- 2014
-
Ingår i: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. - 9781479965175 ; , s. 1-10
-
Konferensbidrag (refereegranskat)abstract
- We prove the following hardness result for anatural promise variant of the classical CNF-satisfiabilityproblem: Given a CNF-formula where each clause has widthw and the guarantee that there exists an assignment satisfyingat least g = [w/2]-1 literals in each clause, it is NP-hard tofind a satisfying assignment to the formula (that sets at leastone literal to true in each clause). On the other hand, when g = [w/2], it is easy to find a satisfying assignment via simplegeneralizations of the algorithms for 2-SAT. Viewing 2-SAT σ P as easiness of SAT when 1-in-2 literals are true in every clause, and NP-hardness of 3-SAT as intractability of SAT when 1-in-3 literals are true, our resultshows, for any fixed ε > 0, the hardness of finding a satisfyingassignment to instances of '(2 + ε)-SAT' where the density ofsatisfied literals in each clause is promised to exceed 1/(2+ε). We also strengthen the results to prove that given a (2k + 1)-uniform hypergraph that can be 2-colored such that each edgehas perfect balance (at most k + 1 vertices of either color), itis NP-hard to find a 2-coloring that avoids a monochromaticedge. In other words, a set system with discrepancy 1 is hard todistinguish from a set system with worst possible discrepancy.
|
|
| 6. |
- Austrin, Per, et al.
(författare)
-
(2 + ϵ)-SAT is NP-hard
- 2017
-
Ingår i: SIAM journal on computing (Print). - : Society for Industrial and Applied Mathematics Publications. - 0097-5397 .- 1095-7111. ; 46:5, s. 1554-1573
-
Tidskriftsartikel (refereegranskat)abstract
- We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width w and the guarantee that there exists an assignment satisfying at least g = [w/2]-1 literals in each clause, it is NP-hard to find a satisfying assignment to the formula (that sets at least one literal to true in each clause). On the other hand, when g = [w/2], it is easy to find a satisfying assignment via simple generalizations of the algorithms for 2-Sat. Viewing 2-Sat 2 P as tractability of Sat when 1 in 2 literals are true in every clause, and NP-hardness of 3-Sat as intractability of Sat when 1 in 3 literals are true, our result shows, for any fixed ϵ > 0, the difficulty of finding a satisfying assignment to instances of "(2 + ϵ)-Sat" where the density of satisfied literals in each clause is guaranteed to exceed 1/2+ϵ. We also strengthen the results to prove that, given a (2k +1)-uniform hypergraph that can be 2-colored such that each edge has perfect balance (at most k +1 vertices of either color), it is NP-hard to find a 2-coloring that avoids a monochromatic edge. In other words, a set system with discrepancy 1 is hard to distinguish from a set system with worst possible discrepancy. Finally, we prove a general result showing the intractability of promise constraint satisfaction problems based on the paucity of certain "weak polymorphisms." The core of the above hardness results is the claim that the only weak polymorphisms in these particular cases are juntas depending on few variables.
|
|
| 7. |
- Austrin, Per, 1981-
(författare)
-
Conditional Inapproximability and Limited Independence
- 2008
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Understanding the theoretical limitations of efficient computation is one of the most fundamental open problems of modern mathematics. This thesis studies the approximability of intractable optimization problems. In particular, we study so-called Max CSP problems. These are problems in which we are given a set of constraints, each constraint acting on some k variables, and are asked to find an assignment to the variables satisfyingas many of the constraints as possible. A predicate P : [q]ᵏ → {0, 1} is said to be approximation resistant if it is intractable to approximate the corresponding CSP problem to within a factor which is better than what is expected from a completely random assignment to the variables. We prove that if the Unique Games Conjecture is true, then a sufficient condition for a predicate P :[q]ᵏ → {0, 1} to be approximation resistant is that there exists a pairwise independent distribution over [q]ᵏ which is supported on the set of satisfying assignments Pˉ¹(1) of P. We also study predicates P : {0, 1}² → {0, 1} on two boolean variables. The corresponding CSP problems include fundamental computational problems such as Max Cut and Max 2-Sat. For any P, we give an algorithm and a Unique Games-based hardness result. Under a certain geometric conjecture, the ratios of these two results are shown to match exactly. In addition, this result explains why additional constraints beyond the standard “triangle inequalities” do not appear to help when solving these problems. Furthermore,we are able to use the generic hardness result to obtain improved hardness for the special cases of Max 2-Sat and Max 2-And. For Max 2-Sat, we obtain a hardness of αLLZ + ε ≈ 0.94016, where αLLZ is the approximation ratio of the algorithm due to Lewin, Livnat and Zwick. For Max 2-And, we obtain a hardness of 0.87435. For both of these problems, our results surprisingly demonstrate that the special case of balanced instances (instances where every variable occurs positively and negatively equally often) is not the hardest. Furthermore, the result for Max 2-And also shows that Max Cut is not the hardest 2-CSP. Motivated by the result for k-CSP problems, and their fundamental importance in computer science in general, we then study t-wise independent distributions with random support. We prove that, with high probability, poly(q) ・ n² random points in [q]ⁿ can support a pairwise independent distribution. Then, again with high probability, we show that (poly(q) ・n)ᵗ log(nᵗ) random points in [q]ⁿ can support a t-wise independent distribution. For constant t and q, we show that Ω(nᵗ) random points are necessary in order to be able to support a t-wise independent balanced distribution with non-negligible probability. Also, we show that every subset of [q]ⁿ with size at least qⁿ(1−poly(q)ˉᵗ) can support a t-wise independent distribution. Finally, we prove a certain noise correlation bound for low-degree functions with small Fourier coefficients. This type of result is generally useful in hardness of approximation, derandomization, and additive combinatorics.
|
|
| 8. |
- Austrin, Per, et al.
(författare)
-
On the power of many one-bit provers
- 2013
-
Ingår i: ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science. - New York : Association for Computing Machinery (ACM). - 9781450318594 ; , s. 215-220
-
Konferensbidrag (refereegranskat)abstract
- We study the class of languages, denoted by MIP[k, 1-∈, s], which have k-prover games where each prover just sends a 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 (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 ≤ 1/2 k - ∈, MIP[k, 1-∈, s] = BPP; • When 1/2k + ∈ ≤ s < 2/2k -∈, MIP[k, 1-∈, s] = SZK; • When s ≥ 2/2k + ∈, AM ⊆ MIP[k, 1-∈, s]; • For s ≤ 0.62 k/2k and sufficiently large k, MIP[k, 1-∈, s] ⊆ 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 ≥ 2/2k + ∈.
|
|
| 9. |
- Austrin, Per, et al.
(författare)
-
On the Usefulness of Predicates
- 2012
-
Ingår i: ACM Transactions on Computation Theory. - : Association for Computing Machinery (ACM). - 1942-3454 .- 1942-3462. ; 5:1
-
Tidskriftsartikel (refereegranskat)abstract
- Motivated by the pervasiveness of strong inapproximability results forMax-CSPs, we introduce a relaxed notion of an approximate solution of aMax-CSP. In this relaxed version, loosely speaking, the algorithm is allowed toreplace the constraints of an instance by some other (possibly real-valued)constraints, and then only needs to satisfy as many of the new constraints aspossible.To be more precise, we introduce the following notion of a predicate $P$being \emph{useful} for a (real-valued) objective $Q$: given an almostsatisfiable Max-$P$ instance, there is an algorithm that beats a randomassignment on the corresponding Max-$Q$ instance applied to the same sets ofliterals. The standard notion of a nontrivial approximation algorithm for aMax-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 tobe equivalent to the following pseudo-randomness property: given an almostsatisfiable instance of Max-$P$ it is hard to find an assignment such that theinduced distribution on $k$-bit strings defined by the instance is notessentially uniform.Under the Unique Games Conjecture, we give a complete and simplecharacterization of useful Max-CSPs defined by a predicate: such a Max-CSP isuseless if and only if there is a pairwise independent distribution supportedon the satisfying assignments of the predicate. It is natural to also considerthe case when no negations are allowed in the CSP instance, and we derive asimilar complete characterization (under the UGC) there as well.Finally, we also include some results and examples shedding additional lighton the approximability of certain Max-CSPs.
|
|
| 10. |
- Austrin, P., et al.
(författare)
-
On the usefulness of predicates
- 2012
-
Ingår i: 2012 IEEE 27th Annual Conference On Computational Complexity (CCC). - : IEEE. - 9780769547084 ; , s. 53-63
-
Konferensbidrag (refereegranskat)abstract
- Motivated by the pervasiveness of strong in approximability 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. Under the Unique Games Conjecture, we can give a complete and simple characterization of useless Max-CSPs defined by a predicate: such a Max-CSP is useless if and only if there is a pair wise 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.
|
|
| 11. |
- Austrin, Per, 1981-, et al.
(författare)
-
Optimal inapproximability with universal factor graphs
- 2021
-
Ingår i: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. - Philadelphia, PA : Association for Computing Machinery. ; , s. 434-453
-
Konferensbidrag (refereegranskat)abstract
- The 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 remain 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: 1. Optimal inapproximability for Max-3-Lin and Max-3-Sat (Håstad, J. ACM 2001). 2. Approximation resistance for predicates supporting pairwise independent subgroups (Chan, J. ACM 2016). 3. Hardness of the “(2 + ε)-Sat” problem and other Promise CSPs (Austrin et al., SIAM J. Comput. 2017). The main technical tool used to establish these results is a new way of folding the long code which we call “functional folding”.
|
|
| 12. |
- Austrin, Per, et al.
(författare)
-
Randomly Supported Independence and Resistance
- 2009
-
Ingår i: STOC'09. - NEW YORK : ASSOC COMPUTING MACHINERY. - 9781605586137 ; , s. 483-492
-
Konferensbidrag (refereegranskat)abstract
- We prove that for any positive integer k, there is a constant C-k such that a randomly selected set of c(k)n(k) log n Boolean vectors with high probability supports a balanced k-wise independent distribution. In the case of k <= 2 a more elaborate argument, gives the strong-er bound ckn(k). Using a recent, result. by Austrin and Mossel this shows that a predicate on t, bits. Chosen at, random among predicates accepting c(2)t(2) input, vectors, is, assuming the Unique Games Conjecture, likely to be approximation resistant. These result's are close to tight,: we show that there are other constants, c(k)(1), such that a randomly selected set of points is unlikely to support a balanced k-wise. independent distribution and for some c > 0, a random predicate accepting ct(2)/log t input, vectors is is non-trivially approximable with high probability. In a different application of the result of Austrin and Mossel we prove that, again assuming the Unique Games Conjecture, any predicate on t bits accepting at least (32/33) - 2(t) inputs is approximation resistant. The results extend front the Boolean domain to larger finite domains.
|
|
| 13. |
- Austrin, Per, et al.
(författare)
-
Randomly supported independence and resistance
- 2011
-
Ingår i: SIAM journal on computing (Print). - : Society for Industrial & Applied Mathematics (SIAM). - 0097-5397 .- 1095-7111. ; 40:1, s. 1-27
-
Tidskriftsartikel (refereegranskat)abstract
- We prove that for any positive integers q and k there is a constant c(q,k) such that a uniformly random set of c(q,k)n(k) log n vectors in [q](n) with high probability supports a balanced k-wise independent distribution. In the case of k <= 2 a more elaborate argument gives the stronger bound, c(q,k)n(k). Using a recent result by Austrin and Mossel, this shows that a predicate on t bits, chosen at random among predicates accepting c(q,2)t(2) input vectors, is, assuming the unique games conjecture, likely to be approximation resistant. These results are close to tight: we show that there are other constants, c'(q,k), such that a randomly selected set of cardinality c'(q,k)n(k) points is unlikely to support a balanced k-wise independent distribution and, for some c > 0, a random predicate accepting ct(2)/logt input vectors is nontrivially approximable with high probability. In a different application of the result of Austrin and Mossel we prove that, again assuming the unique games conjecture, any predicate on t Boolean inputs accepting at least (32/33).2(t) inputs is approximation resistant. The results extend from balanced distributions to arbitrary product distributions.
|
|
| 14. |
- Barak, B., et al.
(författare)
-
Making the long code shorter
- 2015
-
Ingår i: SIAM journal on computing (Print). - : Society for Industrial and Applied Mathematics. - 0097-5397 .- 1095-7111. ; 44:5, s. 1287-1324
-
Tidskriftsartikel (refereegranskat)abstract
- The long code is a central tool in hardness of approximation especially in questions related to the Unique Games Conjecture. We construct a new code that is exponentially more efficient but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results including the following: (1) For any ε > 0, we show the existence of an n-vertex graph G where every set of o(n) vertices has expansion 1-ε but G's adjacency matrix has more than exp(logδ n) eigenvalues larger than 1 - ε, where δ depends only on ε. This answers an open question of Arora, Barak, and Steurer [Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 563-572] who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. (2) A gadget that reduces Unique Games instances with linear constraints modulo K into instances with alphabet k with a blowup of kpolylog(K) , improving over the previously known gadget with blowup of kω(K). (3) An n-variable integrality gap for Unique Games that survives exp(poly(log log n)) rounds of the semidefinite programming version of the Sherali-Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and Small-Set Expansion in certain related Cayley graphs and use this connection to derandomize the noise graph on the Boolean hypercube.
|
|
| 15. |
- Barak, Boaz, et al.
(författare)
-
Making the Long Code Shorter
- 2012
-
Ingår i: Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on. - : IEEE Computer Society. ; , s. 370-379
-
Konferensbidrag (refereegranskat)abstract
- The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. We construct a new code that is exponentially more efficient, but can still be used in many of these applications. Using the new code we obtain exponential improvements over several known results, including the following: 1) For any ε > 0, we show the existence of an n vertex graph G where every set of o(n) vertices has expansion 1-ε, but G's adjacency matrix has more than exp(logδ n) eigenvalues larger than 1 - ε, where δ depends only on ε. This answers an open question of Arora, Barak and Steurer (FOCS 2010) who asked whether one can improve over the noise graph on the Boolean hypercube that has poly(log n) such eigenvalues. 2) A gadget that reduces unique games instances with linear constraints modulo K into instances with alphabet k with a blowup of Kpolylog(K), improving over the previously known gadget with blowup of 2Ω(K). 3) An n variable integrality gap for Unique Games that survives exp(poly(log log n)) rounds of the SDP + Sherali Adams hierarchy, improving on the previously known bound of poly(log log n). We show a connection between the local testability of linear codes and small set expansion in certain related Cayley graphs, and use this connection to derandomize the noise graph on the Boolean hypercube.
|
|
| 16. |
- Blais, Eric, et al.
(författare)
-
On DNF Approximators for Monotone Boolean Functions
- 2014
-
Ingår i: Automata, Languages, and Programming. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783662439487 ; , s. 235-246
-
Konferensbidrag (refereegranskat)abstract
- We study the complexity of approximating monotone Boolean functions with disjunctive normal form (DNF) formulas, exploring two main directions. First, we construct DNF approximators for arbitrary monotone functions achieving one-sided error: we show that every monotone f can be e-approximated by a DNF g of size 2(n-Omega)(root n) satisfying g(x) <= f(x) for all x is an element of{0, 1}(n). This is the first non-trivial universal upper bound even for DNF approximators incurring two-sided error. Next, we study the power of negations in DNF approximators for monotone functions. We exhibit monotone functions for which non-monotone DNFs perform better than monotone ones, giving separations with respect to both DNF size and width. Our results, when taken together with a classical theorem of Quine [1], highlight an interesting contrast between approximation and exact computation in the DNF complexity of monotone functions, and they add to a line of work on the surprising role of negations in monotone complexity [2,3,4].
|
|
| 17. |
- Boppana, Ravi, et al.
(författare)
-
Bounded Independence versus Symmetric Tests
- 2019
-
Ingår i: ACM Transactions on Computation Theory. - : ASSOC COMPUTING MACHINERY. - 1942-3454 .- 1942-3462. ; 11:4
-
Tidskriftsartikel (refereegranskat)abstract
- For a test T subset of {0, 1}(n), define k* (T) to be the maximum k such that there exists a k-wise uniform distribution over {0, 1}(n) whose support is a subset of T. For H-t = {x is an element of {0,1}(n) : vertical bar Sigma(i) x(i) - n/2 vertical bar <= t}, we prove k* (H-t) = Theta(t(2)/n + 1). For S-m,S-c = {x is an element of 1)(n) : Sigma(i )x(i) = c (mod m)}, we prove that k* (S-m,S-c) = Theta(n/m(2)). For some k = O(n/ m) we also show that any k-wise uniform distribution puts probability mass at most 1 /m + 1/100 over S-m,S-c. Finally, for any fixed odd m we show that there is an integer k = (1 - Omega(1))n such that any k-wise uniform distribution lands in T with probability exponentially close to vertical bar S-m,S-c vertical bar/2(n); and this result is false for any even m.
|
|
| 18. |
- Boppana, R., et al.
(författare)
-
Bounded Independence vs. Moduli
- 2016
-
Ingår i: Leibniz International Proceedings in Informatics, LIPIcs. - : Dagstuhl Publishing. - 9783959770187
-
Konferensbidrag (refereegranskat)abstract
- Let k = k(n) be the largest integer such that there exists a k-wise uniform distribution over {0, 1}n that is supported on the set Sm := {x 2 {0, 1}n : Σi xi ≡ 0 mod m}, where m is any integer. We show that Ω(n/m2 logm) ≤ k ≤ 2n/m + 2. For k = O(n/m) we also show that any k-wise uniform distribution puts probability mass at most 1/m + 1/100 over Sm. For any fixed odd m there is k ≥ (1-Ω(1))n such that any k-wise uniform distribution lands in Sm with probability exponentially close to |Sm|/2n; and this result is false for any even m.
|
|
| 19. |
- Bukh, Boris, et al.
(författare)
-
An Improved Bound on the Fraction of Correctable Deletions
- 2017
-
Ingår i: IEEE Transactions on Information Theory. - : IEEE. - 0018-9448 .- 1557-9654. ; 63:1, s. 93-103
-
Tidskriftsartikel (refereegranskat)abstract
- We consider codes over fixed alphabets against worst case symbol deletions. For any fixed k >= 2, we construct a family of codes over alphabet of size k with positive rate, which allow efficient recovery from a worst case deletion fraction approaching 1 - (2/(k + root k)). In particular, for binary codes, we are able to recover a fraction of deletions approaching 1/(root 2+1) = root 2-1 approximate to 0.414. Previously, even non-constructively, the largest deletion fraction known to be correctable with positive rate was 1 - Theta (1/root k), and around 0.17 for the binary case. Our result pins down the largest fraction of correctable deletions for k-ary codes as 1 - Theta (1/k), since 1 - 1/k is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between (root 2 - 1) and 1/2 for the limit of worst case deletions correctable by binary codes remains a tantalizing open question.
|
|
| 20. |
- Cheraghchi, M., et al.
(författare)
-
Approximating Linear Threshold Predicates
- 2010
-
Ingår i: Lecture Notes in Computer Science. 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010, Barcelona, 1-3 September 2010. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783642153686 ; 6302, s. 110-123
-
Konferensbidrag (refereegranskat)abstract
- We study constraint satisfaction problems on the domain {-1,1}, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form sgn(w1 x1+⋯+wn x n ) for some positive integer weights w 1, ..., w n . Despite their simplicity, current techniques fall short of providing a classification of these predicates in terms of approximability. In fact, it is not easy to guess whether there exists a homogeneous linear threshold predicate that is approximation resistant or not. The focus of this paper is to identify and study the approximation curve of a class of threshold predicates that allow for non-trivial approximation. Arguably the simplest such predicate is the majority predicate sgn(x 1+⋯+xn ), for which we obtain an almost complete understanding of the asymptotic approximation curve, assuming the Unique Games Conjecture. Our techniques extend to a more general class of "majority-like" predicates and we obtain parallel results for them. In order to classify these predicates, we introduce the notion of Chow-robustness that might be of independent interest.
|
|
| 21. |
- Cheraghchi, M., et al.
(författare)
-
Approximating linear threshold predicates
- 2012
-
Ingår i: ACM Transactions on Computation Theory. - : Association for Computing Machinery (ACM). - 1942-3454 .- 1942-3462. ; 4:1
-
Tidskriftsartikel (refereegranskat)abstract
- We study constraint satisfaction problems on the domain {-1, 1}, where the given constraints are homogeneous linear threshold predicates, that is, predicates of the form sgn(w 1 x 1 + · · · + w n x n ) for some positive integer weights w 1 , . . . , w n . Despite their simplicity, current techniques fall short of providing a classification of these predicates in terms of approximability. In fact, it is not easy to guess whether there exists a homogeneous linear threshold predicate that is approximation resistant or not. The focus of this article is to identify and study the approximation curve of a class of threshold predicates that allow for nontrivial approximation. Arguably the simplest such predicate is the majority predicate sgn(x 1 + · · · + x n ), for which we obtain an almost complete understanding of the asymptotic approximation curve, assuming the Unique Games Conjecture. Our techniques extend to a more general class of "majority-like" predicates and we obtain parallel results for them. In order to classify these predicates, we introduce the notion of Chow-robustness that might be of independent interest.
|
|
| 22. |
- Dodis, Y., et al.
(författare)
-
Randomness extraction and key derivation using the CBC, Cascade and HMAC Modes
- 2004
-
Ingår i: ADVANCES IN CRYPTOLOGY - CRYPTO 2004, PROCEEDINGS. - Berlin, Heidelberg : Springer Berlin Heidelberg. ; , s. 494-510
-
Konferensbidrag (refereegranskat)abstract
- We study the suitability of common pseudorandomness modes associated with cryptographic hash functions and block ciphers (CBC-MAC, Cascade and HMAC) for the task of "randomness extraction", namely, the derivation of keying material from semi-secret and/or semi-random sources. Important applications for such extractors include the derivation of strong cryptographic keys from non-uniform sources of randomness (for example, to extract a seed for a pseudorandom generator from a weak source of physical or digital noise), and the derivation of pseudorandom keys from a Diffie-Hellman value. Extractors are closely related in their applications to pseudorandom functions and thus it is attractive to (re)use the common pseudorandom modes as randomness extractors. Yet, the crucial difference between pseudorandom generation and randomness extraction is that the former uses random secret keys while the latter uses random but known keys. We show that under a variety of assumptions on the underlying primitives (block ciphers and compression functions), ranging from ideal randomness assumptions to realistic universal-hashing properties, these modes induce good extractors. Hence, these schemes represent a more practical alternative to combinatorial extractors (that are seldom used in practice), and a better-analyzed alternative to the common practice of using SHA-1 or MD5 (as a single un-keyed function) for randomness extraction. In particular, our results serve to validate the method of key extraction and key derivation from Diffie-Hellman values used in the IKE (IPsec's Key Exchange) protocol.
|
|
| 23. |
- Dor, D., et al.
(författare)
-
On lower bounds for selecting the median
- 2001
-
Ingår i: SIAM Journal on Discrete Mathematics. - 0895-4801 .- 1095-7146. ; 14:3, s. 299-311
-
Tidskriftsartikel (refereegranskat)abstract
- We present a reformulation of the 2n + o(n) lower bound of Bent and John [Proceedings of the 17th Annual A CM Symposium on Theory of Computing, 1985, pp. 213-216] for the number of comparisons needed for selecting the median of n elements. Our reformulation uses a weight function. Apart from giving a more intuitive proof for the lower bound, the new formulation opens up possibilities for improving it. We use the new formulation to show that any pair-forming median finding algorithm, i.e., a median finding algorithm that starts by comparing [n/2] disjoint pairs of elements must perform, in the worst case, at least 2.01n + o(n) comparisons. This provides strong evidence that selecting the median requires at least cn + o(n) comparisons for some c > 2.
|
|
| 24. |
- Ekerå, Martin, et al.
(författare)
-
Quantum algorithms for computing short discrete logarithms and factoring RSA integers
- 2017
-
Ingår i: 8th International Workshop on Post-Quantum Cryptography, PQCrypto 2017. - Cham : Springer. - 9783319598789 ; , s. 347-363
-
Konferensbidrag (refereegranskat)abstract
- We generalize the quantum algorithm for computing short discrete logarithms previously introduced by Ekerå [2] so as to allow for various tradeoffs between the number of times that the algorithm need be executed on the one hand, and the complexity of the algorithm and the requirements it imposes on the quantum computer on the other hand. Furthermore, we describe applications of algorithms for computing short discrete logarithms. In particular, we show how other important problems such as those of factoring RSA integers and of finding the order of groups under side information may be recast as short discrete logarithm problems. This gives rise to an algorithm for factoring RSA integers that is less complex than Shor’s general factoring algorithm in the sense that it imposes smaller requirements on the quantum computer. In both our algorithm and Shor’s algorithm, the main hurdle is to compute a modular exponentiation in superposition. When factoring an n bit integer, the exponent is of length 2n bits in Shor’s algorithm, compared to slightly more than n/2 bits in our algorithm.
|
|
| 25. |
- Guruswami, Venkatesan, et al.
(författare)
-
BEATING THE RANDOM ORDERING IS HARD : EVERY ORDERING CSP IS APPROXIMATION RESISTANT
- 2011
-
Ingår i: SIAM journal on computing (Print). - : Society for Industrial & Applied Mathematics (SIAM). - 0097-5397 .- 1095-7111. ; 40:3, s. 878-914
-
Tidskriftsartikel (refereegranskat)abstract
- We prove that, assuming the Unique Games conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSPs) where each constraint has constant arity is approximation resistant. In other words, we show that if. is the expected fraction of constraints satisfied by a random ordering, then obtaining rho' approximation for any rho' > rho is UG-hard. For the simplest OCSP, the MAXIMUM ACYCLIC SUBGRAPH (MAS) problem, this implies that obtaining a.-approximation for any constant rho > 1/2 is UG-hard. Specifically, for every constant epsilon > 0 the following holds: given a directed graph G that has an acyclic subgraph consisting of a fraction (1-epsilon) of its edges, it is UG-hard to find one with more than (1/2 + epsilon) of its edges. Note that it is trivial to find an acyclic subgraph with 1/2 the edges by taking either the forward or backward edges in an arbitrary ordering of the vertices of G. The MAS problem has been well studied, and beating the random ordering for MAS has been a basic open problem. An OCSP of arity k is specified by a subset Pi subset of S-k of permutations on {1, 2, ... ,k}. An instance of such an OCSP is a set V and a collection of constraints, each of which is an ordered k-tuple of V. The objective is to find a global linear ordering of V while maximizing the number of constraints ordered as in.. A random ordering of V is expected to satisfy rho = vertical bar Pi vertical bar/k! fraction. We show that, for any fixed k, it is hard to obtain rho'-approximation for Pi-OCSP for any rho' > rho. The result is in fact stronger: we show that for every Lambda subset of Pi subset of S-k, and an arbitrarily small epsilon, it is hard to distinguish instances where a (1 - epsilon) fractionof the constraints can be ordered according to. from instances where at most a (rho + epsilon) fraction can be ordered as in Pi. A special case of our result is that the BETWEENNESS problem is hard to approximate beyond a factor 1/3. The results naturally generalize to OCSPs which assign a payoff to the different permutations. Finally, our results imply (unconditionally) that a simple semidefinite relaxation for MAS does not suffice to obtain a better approximation.
|
|
| 26. |
- Guruswami, V., et al.
(författare)
-
Combinatorial bounds for list decoding
- 2002
-
Ingår i: IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9448 .- 1557-9654. ; 48:5, s. 1021-1034
-
Tidskriftsartikel (refereegranskat)abstract
- Informally, an error-correcting code has nice list-decodability properties if every Hamming ball of large radius has a small number of codewords in it. Here, we report linear codes with nontrivial list-decodability: i.e., codes of large rate that are nicely list-decodable, and codes of large distance that are not nicely list-decodable. Specifically, on the positive side, we show that there exist codes of rate R and block length n that have at most c codewords in every Hamming ball of radius H-1 (1-R-1/c) (.) n. This answers the main open question from the work of Elias. This result also has consequences for the construction of concatenated codes of good rate that are list decodable from a large fraction of errors, improving previous results of Guruswami and Sudan in this vein. Specifically, for every epsilon > 0, we present a polynomial time constructible asymptotically good family of binary codes of rate Omega(epsilon(4)) that can be list-decoded in polynomial time from up to a fraction (1/2 - epsilon) of errors, using lists of size O(epsilon(-2)). On the negative side, we show that for every delta and c, there exists tau < delta, c(1) > 0, and an infinite family of linear codes {C-i}(i) such that if n(i) denotes the block length of C-i, then C-i has minimum distance at least delta (.) n(i) and contains more than c(1) (.) n(i)(c) codewords in some Hamming ball of radius tau (.) n(i). While this result is still far from known bounds on the list-decodability of linear codes, it is the first to bound the radius for list-decodability by a polynomial-sized list away from the minimum distance of the code.
|
|
| 27. |
- Guruswami, Venkatesan, et al.
(författare)
-
Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound
- 2021
-
Ingår i: IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9448 .- 1557-9654. ; 67:10, s. 6384-6394
-
Tidskriftsartikel (refereegranskat)abstract
- We give an explicit construction of length-n binary codes capable of correcting the deletion of two bits that have size 2(n)/n(4+o(1)). This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size Omega(2(n)/n(4)). Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size Omega(2(n)/n(3+o(1))) that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear.
|
|
| 28. |
- Guruswami, V., et al.
(författare)
-
Explicit two-deletion codes with redundancy matching the existential bound
- 2021
-
Ingår i: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. - : Association for Computing Machinery. ; , s. 21-32
-
Konferensbidrag (refereegranskat)abstract
- We give an explicit construction of length-n binary codes capable of correcting the deletion of two bits that have size 2n/n4+o(1). This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size Ω(2n/n4). Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size Ω(2n/n3+o(1)) that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear.
|
|
| 29. |
- Guruswami, V., et al.
(författare)
-
Hardness of approximate hypergraph coloring
- 2002
-
Ingår i: SIAM journal on computing (Print). - 0097-5397 .- 1095-7111. ; 31:6, s. 1663-1686
-
Tidskriftsartikel (refereegranskat)abstract
- We introduce the notion of covering complexity of a veri er for probabilistically checkable proofs (PCPs). Such a veri er is given an input, a claimed theorem, and an oracle, representing a purported proof of the theorem. The veri er is also given a random string and decides whether to accept the proof or not, based on the given random string. We de ne the covering complexity of such a veri er, on a given input, to be the minimum number of proofs needed to satisfy the veri er on every random string; i.e., on every random string, at least one of the given proofs must be accepted by the veri er. The covering complexity of PCP verifiers offers a promising route to getting stronger inapproximability results for some minimization problems and, in particular, (hyper) graph coloring problems. We present a PCP veri er for NP statements that queries only four bits and yet has a covering complexity of one for true statements and a superconstant covering complexity for statements not in the language. Moreover, the acceptance predicate of this veri er is a simple not-all-equal check on the four bits it reads. This enables us to prove that, for any constant c, it is NP-hard to color a 2-colorable 4-uniform hypergraph using just c colors and also yields a superconstant inapproximability result under a stronger hardness assumption.
|
|
| 30. |
- Guruswami, V., et al.
(författare)
-
On the list-decodability of random linear codes
- 2010
-
Ingår i: Proceedings of the Annual ACM Symposium on Theory of Computing. - New York, NY, USA : ACM. - 9781605588179 ; , s. 409-416
-
Konferensbidrag (refereegranskat)abstract
- We show that the list-decodability of random linear codes is as good as that of general random codes. Specifically, for every fixed finite field double-struck Fq, p ∈ (0,1-1/q) and ε > 0, we prove that with high probability a random linear code C in double-struck F qn of rate (1-H-q(p)-ε) can be list decoded from a fraction p of errors with lists of size at most O(1/ε). This also answers a basic open question concerning the existence of highly list-decodable linear codes, showing that a list-size of O(1/ε) suffices to have rate within ε of the "list decoding capacity" 1-Hq(p). The best previously known list-size bound was qO(1/ε) (except in the q=2 case where a list-size bound of O(1/ε) was known). The main technical ingredient in our proof is a strong upper bound on the probability that ℓ random vectors chosen from a Hamming ball centered at the origin have too many (more than Θ(ℓ)) vectors from their linear span also belong to the ball.
|
|
| 31. |
- Guruswami, Venkatesan, et al.
(författare)
-
On the List-Decodability of Random Linear Codes
- 2011
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448 .- 1557-9654. ; 57:2, s. 718-725
-
Tidskriftsartikel (refereegranskat)abstract
- The list-decodability of random linear codes is shown to be as good as that of general random codes. Specifically, for every fixed finite field, Gamma(q), p is an element of (0, 1 - 1/q) and epsilon > 0, it is proved that with high probability a random linear code C in F-q(n) of rate (1 - H-q(p) - epsilon) can be list decoded from a fraction p of errors with lists of size at most O(1/epsilon). This also answers a basic open question concerning the existence of highly list-decodable linear codes, showing that a list-size of O(1/epsilon) suffices to have rate within epsilon of the information-theoretically optimal rate of 1 - H-q(p). The best previously known list-size bound was q(O(1/epsilon)) (except in the q = 2 case where a list-size bound of O(1/epsilon) was known). The main technical ingredient in the proof is a strong upper bound on the probability that l random vectors chosen from a Hamming ball centered at the origin have too many (more than Omega(l)) vectors from their linear span also belong to the ball.
|
|
| 32. |
- Guruswami, Venkatesan, et al.
(författare)
-
SUPER-POLYLOGARITHMIC HYPERGRAPH COLORING HARDNESS VIA LOW-DEGREE LONG CODES
- 2017
-
Ingår i: SIAM journal on computing (Print). - : SIAM PUBLICATIONS. - 0097-5397 .- 1095-7111. ; 46:1, s. 132-159
-
Tidskriftsartikel (refereegranskat)abstract
- We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka the "short code" of Barak et al. [SIAM J. Comput., 44 (2015), pp. 1287-1324]) and the techniques proposed by Dinur and Guruswami [Israel J. Math., 209 (2015), pp. 611-649] to incorporate this code for inapproximability results. In particular, we prove quasi NP-hardness of the following problems on n-vertex hypergraphs: coloring a 2-colorable 8-uniform hypergraph with 2(2 Omega(root loglg n)) colors; coloring a 4-colorable 4-uniform hypergraph with 2(2 Omega(root loglg n)) colors; and coloring a 3-colorable 3-uniform hypergraph with (log n)(Omega(1/log log log n)) colors. For the first two cases, the hardness results obtained are superpolynomial in what was previously known, and in the last case it is an exponential improvement. In fact, prior to this result, (log n)(O(1))Colors was the strongest quantitative bound on the number of colors ruled out by inapproximability results for O(1) -colorable hypergraphs, and (log log n)(O(1)) for O(1) -colorable, 3-uniform hypergraphs.
|
|
| 33. |
- Guruswami, V., et al.
(författare)
-
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
- 2014
-
Ingår i: Proceedings of the Annual ACM Symposium on Theory of Computing. - New York, NY, USA : ACM. - 9781450327107 ; , s. 614-623
-
Konferensbidrag (refereegranskat)abstract
- We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the"short code" of Barak et. al. [FOCS 2012]) and the techniques pro-posed by Dinur and Guruswami [FOCS 2013] to incorporatethis code for inapproximability results. In particular, we prove quasi-NP-hardness of the following problems on n-vertex hypergraphs: • Coloring a 2-colorable 8-uniform hypergraph with 2 2Ω(√log log n) colors. • Coloring a 4-colorable 4-uniform hypergraph with 22Ω(√ log log n) colors. • Coloring a 3-colorable 3-uniform hypergraph with (log n) Ω(1√ log log log n) colors. In each of these cases, the hardness results obtained are (at least) superpolynomially stronger (if not exponentially stronger as in the third case) than what was previously known for the respective cases. In fact, prior to this result, (log n)O(1) colors was the strongest quantitative bound on the number of colors ruled out by inapproximability results for O(1)-colorable hypergraphs. The fundamental bottleneck in obtaining coloring in approximability results using the low-degree long code was a ultipartite structural restriction in the PCP construction of Dinur-Guruswami. We are able to get around this restriction by simulating the multipartite structure implicitly by querying just one partition (albeit requiring 8 queries), which yields our result for 2-colorable 8-uniform hypergraphs. The result for 4-colorable 4-uniform hypergraphs is obtained via a "query doubling" method exploiting additional properties of the 8-query test. For 3-colorable 3-uniform hyper-graphs, we exploit the ternary domain to design a test with an additive (as opposed to multiplicative) noise function, and analyze its efficacy in killing high weight Fourier coefficients via the pseudorandom properties of an associated quadratic form. The latter step involves extending the key algebraic ingredient of Dinur-Guruswami concerning testing binary Reed-Muller codes to the ternary alphabet.
|
|
| 34. |
- Hast, Gustav, 1975-
(författare)
-
Beating a Random Assignment : Approximating Constraint Satisfaction Problems
- 2005
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- An instance of a Boolean constraint satisfaction problem, CSP, consists of a set of constraints acting over a set of Boolean variables. The objective is to find an assignment to the variables that satisfies all the constraints. In the maximization version, Max CSP, each constraint has a weight and the objective is to find an assignment such that the weight of satisfied constraints is maximized. By specifying which types of constraints that are allowed we create subproblems to Max CSP. For example, an instance of Max kCSP only contains constraints that act over at most k different variables. Another problem is Max CSP(P), where P is a predicate, i.e., a Boolean function. In such an instance P is used to determine if a constraint is satisfied or not. Both Max kCSP and Max CSP(P) are NP-hard to solve optimally for k ≥ 2 and predicates P that depend on at least two input values. Therefore, we consider efficient approximation algorithms for these two problems. A trivial algorithm is to assign all variables a random value. Somewhat surprisingly, Håstad showed that using this random assignment approach is essentially optimal for approximating Max CSP(P), for some predicates P. We call such predicates approximation resistant. Goemans and Williamson introduced an approximation method that relaxes problems into semidefinite programs. Using this method they show that for predicates P of arity two, it is possible to outperform a random assignment in approximating Max CSP(P). By extending this technique Zwick characterized all predicates of arity three as either approximation resistant or not. In this thesis we consider predicates of arity larger than three. We extend the work of Håstad and the work of Samorodnitsky and Trevisan in order to show predicates to be approximation resistant. We also use semidefinite relaxation algorithms in order to show that predicates are not approximation resistant. In particular we show that predicates with few non-accepting inputs are approximation resistant and that predicates with few accepting inputs are not approximation resistant. We study predicates of arity four more closely and characterize 354 out of 400 predicate types. Max kCSP is 2-k-approximated by a random assignment and previously no algorithms were known to outperform such an algorithm with more than a small constant factor. In this thesis a probabilistic Ω (2k+log k-log log k)-approximation for Max kCSP is presented.
|
|
| 35. |
- Huang, Sangxia, 1988-
(författare)
-
Hardness of Constraint Satisfaction and Hypergraph Coloring : Constructions of Probabilistically Checkable Proofs with Perfect Completeness
- 2015
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- A Probabilistically Checkable Proof (PCP) of a mathematical statement is a proof written in a special manner that allows for efficient probabilistic verification. The celebrated PCP Theorem states that for every family of statements in NP, there is a probabilistic verification procedure that checks the validity of a PCP proof by reading only 3 bits from it. This landmark theorem, and the works leading up to it, laid the foundation for many subsequent works in computational complexity theory, the most prominent among them being the study of inapproximability of combinatorial optimization problems.This thesis focuses on a broad class of combinatorial optimization problems called Constraint Satisfaction Problems (CSPs). In an instance of a CSP problem of arity k, we are given a set of variables taking values from some finite domain, and a set of constraints each involving a subset of at most k variables. The goal is to find an assignment that simultaneously satisfies as many constraints as possible. An alternative formulation of the goal that is commonly used is Gap-CSP, where the goal is to decide whether a CSP instance is satisfiable or far from satisfiable, where the exact meaning of being far from satisfiable varies depending on the problems.We first study Boolean CSPs, where the domain of the variables is {0,1}. The main question we study is the hardness of distinguishing satisfiable Boolean CSP instances from those for which no assignment satisfies more than some epsilon fraction of the constraints. Intuitively, as the arity increases, the CSP gets more complex and thus the hardness parameter epsilon should decrease. We show that for Boolean CSPs of arity k, it is NP-hard to distinguish satisfiable instances from those that are at most 2^{~O(k^{1/3})}/2^k-satisfiable.We also study coloring of graphs and hypergraphs. Given a graph or a hypergraph, a coloring is an assignment of colors to vertices, such that all edges or hyperedges are non-monochromatic. The gap problem is to distinguish instances that are colorable with a small number of colors, from those that require a large number of colors. For graphs, we prove that there exists a constant K_0>0, such that for any K >= K_0, it is NP-hard to distinguish K-colorable graphs from those that require 2^{Omega(K^{1/3})} colors. For hypergraphs, we prove that it is quasi-NP-hard to distinguish 2-colorable 8-uniform hypergraphs of size N from those that require 2^{(log N)^{1/4-o(1)}} colors.In terms of techniques, all these results are based on constructions of PCPs with perfect completeness, that is, PCPs where the probabilistic proof verification procedure always accepts a correct proof. Not only is this a very natural property for proofs, but it can also be an essential requirement in many applications. It has always been particularly challenging to construct PCPs with perfect completeness for NP statements due to limitations in techniques. Our improved hardness results build on and extend many of the current approaches. Our Boolean CSP result and GraphColoring result were proved by adapting the Direct Sum of PCPs idea by Siu On Chan to the perfect completeness setting. Our proof for hypergraph coloring hardness improves and simplifies the recent work by Khot and Saket, in which they proposed the notion of superposition complexity of CSPs.
|
|
| 36. |
- Håstad, Johan
(författare)
-
A slight sharpening of LMN
- 2001
-
Ingår i: Journal of computer and system sciences (Print). - : Elsevier BV. - 0022-0000 .- 1090-2724. ; 63:3, s. 498-508
-
Tidskriftsartikel (refereegranskat)abstract
- N. Linial et al. (1993. J. Assoc. Comput. Mach. 40, No. 3, 607-620) proved that a function computed by a small-depth circuit of limited size has most of its Fourier support on small sets. We improve their bounds. When the bottom fanin is bounded we use essentially their argument, but to reduce the general case to this case without a loss in the asymptotic bounds requires a new argument.
|
|
| 37. |
- Håstad, Johan, 1960-, et al.
(författare)
-
An average-case depth hierarchy theorem for boolean circuits
- 2017
-
Ingår i: Journal of the ACM. - : Association for Computing Machinery (ACM). - 0004-5411 .- 1557-735X. ; 64:5
-
Tidskriftsartikel (refereegranskat)abstract
- We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d ≥ 2, there is an explicit n-variable Boolean function f, computed by a linear-size depth-d formula, which is such that any depth-(d−1) circuit that agrees with f on (1/2 + on(1)) fraction of all inputs must have size exp(nΩ (1/d)). This answers an open question posed by Håstad in his Ph.D. thesis (Håstad 1986b).Our average-case depth hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, confirming a conjecture of Håstad (1986a), Cai (1986), and Babai (1987). We also use our result to show that there is no “approximate converse” to the results of Linial, Mansour, Nisan (Linial et al. 1993) and (Boppana 1997) on the total influence of bounded-depth circuits.A key ingredient in our proof is a notion of random projections which generalize random restrictions.
|
|
| 38. |
- Håstad, Johan
(författare)
-
An Average-case Depth Hierarchy Theorem for Higher Depths
- 2016
-
Ingår i: 2016 IEEE 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS). - : IEEE Computer Society. - 9781509039333 ; , s. 79-88
-
Konferensbidrag (refereegranskat)abstract
- We extend the recent hierarchy results of Ross-man, Servedio and Tan [1] to address circuits of almost logarithmic depth. Our proof uses the same basic approach as [1] but a number of small differences enables us to obtain a stronger result by a significantly shorter proof.
|
|
| 39. |
- Håstad, Johan, et al.
(författare)
-
An Efficient Parallel Repetition Theorem
- 2010
-
Ingår i: THEORY OF CRYPTOGRAPHY, PROCEEDINGS. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 9783642117985 ; , s. 1-18
-
Konferensbidrag (refereegranskat)abstract
- We present a general parallel-repetition theorem with an efficient reduction. As a corollary of this theorem we establish that parallel repetition reduces the soundness error at an exponential rate in any public-coin argument, and more generally, any argument where the verifier's messages, but not necessarily its decision to accept or reject, can be efficiently simulated with noticeable probability.
|
|
| 40. |
- Håstad, Johan
(författare)
-
Complexity theory, proofs and approximation
- 2005
-
Ingår i: European Congress of Mathematics. - Zuerich, Switzerland : European Mathematical Society Publishing House. - 3037190094 ; , s. 733-750
-
Konferensbidrag (refereegranskat)abstract
- We give a short introduction to some questions in complexity theory and proceed to describe some recent developments. In particular, we discuss probabilistically checkable proofs and their applications in establishing inapproximability results. In a traditional proof the proof-checker reads the entire proof and decides deterministically whether the proof is correct. In a probabilistically checkable proof the proof-checker randomly verifies only a very small portion of the proof but still cannot be fooled into accepting a false claim except with small probability.
|
|
| 41. |
- Håstad, Johan, 1960-, et al.
(författare)
-
d-Galvin families
- 2020
-
Ingår i: The Electronic Journal of Combinatorics. - : ELECTRONIC JOURNAL OF COMBINATORICS. - 1097-1440 .- 1077-8926. ; 27:1
-
Tidskriftsartikel (refereegranskat)abstract
- The Galvin problem asks for the minimum size of a family F subset of ([n]n/2) with the property that, for any set A of size n/2, there is a set S is an element of F which is balanced on A, meaning that vertical bar S boolean AND A vertical bar = vertical bar S boolean AND ( A) over bar vertical bar. We consider a generalization of this question that comes from a possible approach in complexity theory. In the generalization the required property is, for any A, to be able to find d sets from a family F subset of ([n]n/d) that form a partition of [n] and such that each part is balanced on A. We construct such families of size polynomial in the parameters n and d.
|
|
| 42. |
- Håstad, Johan
(författare)
-
Every 2-CSP Allows Nontrivial Approximation
- 2005
-
Ingår i: Proceedings of the 37th Annual ACM Symposium on Theory of Computing. - New York, NY, USA : ACM. - 1581139608 ; , s. 740-746
-
Konferensbidrag (refereegranskat)abstract
- We use semidefinite programming to prove that any constraint satisfaction problem in two variables over any domain allows an efficient approximation algorithm that does provably better than picking a random assignment. To be more precise assume that each variable can take values in [d] and that each constraint rejects t out of the d2 possible input pairs. Then, for some universal constant c, we can, in probabilistic polynomial time, find an assignment whose objective value is, on expectation, within a factor (1- t/d2(1- c/d2 log d)) of optimal.
|
|
| 43. |
- Håstad, Johan
(författare)
-
EVERY 2-CSP ALLOWS NONTRIVIAL APPROXIMATION
- 2008
-
Ingår i: Computational Complexity. - : Springer Science and Business Media LLC. - 1016-3328 .- 1420-8954. ; 17:4, s. 549-566
-
Tidskriftsartikel (refereegranskat)abstract
- We use semidefinite programming to prove that any constraint satisfaction problem in two variables over any domain allows an efficient approximation algorithm that does better than picking a random assignment. Specifically we consider the case when each variable can take values in [d] and that each constraint rejects t out of the d(2) possible input pairs. Then, for some universal constant c, we can, in probabilistic polynomial time, find an assignment whose objective value is, in expectation, within a factor 1 - t/d(2) + ct/d(4) log d of optimal, improving on the trivial bound of 1 - t/d(2).
|
|
| 44. |
- Håstad, Johan, et al.
(författare)
-
Fitting points on the real line and its application to RH mapping
- 2003
-
Ingår i: Journal of Algorithms. - : Elsevier BV. - 0196-6774 .- 1090-2678. ; 49:1, s. 42-62
-
Tidskriftsartikel (refereegranskat)abstract
- A natural problem is that of, given an n x n symmetric matrix D, finding an arrangement of n points on the real line such that the so obtained distances agree as well as possible with the by D specified distances. We refer to the variation in which the difference in distance is measured in maximum norm as the MATRIX-TO-LINE problem. The MATRIX-TO-LINE problem has previously been shown to be NP-complete [J.B. Saxe, 17th Allerton Conference in Communication, Control, and Computing, 1979, pp. 480-489]. We show that it can be approximated within 2, but unless P = NP not within 7/5 - delta for any delta > 0. We also show a tight lower bound under a stronger assumption. We show that the MATRIX-TO-LINE problem cannot be approximated within 2 - delta unless 3-colorable graphs can be colored with [4/delta] colors in polynomial time. Currently, the best polynomial time algorithm colors a 3-colorable graph with (O) over tilde (n(3/14)) colors [A. Blum, D. Karger, Inform. Process. Lett. 61 (1), (1997), 49-53]. We apply our MATRIX-TO-LINE algorithm to a problem in computational biology, namely, the Radiation Hybrid (RH) problem. That is, the algorithmic part of a physical mapping method called RH mapping. This gives us the first algorithm with a guaranteed convergence for the general RH problem.
|
|
| 45. |
- Håstad, Johan, et al.
(författare)
-
Improved NP-inapproximability for 2-variable linear equations
- 2015
-
Ingår i: Leibniz International Proceedings in Informatics, LIPIcs. - : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH. ; , s. 341-360
-
Konferensbidrag (refereegranskat)abstract
- An instance of the 2-Lin(2) problem is a system of equations of the form "xi + xj = b (mod 2)". Given such a system in which it’s possible to satisfy all but an C ε fraction of the equations, we show it is NP-hard to satisfy all but a Cε fraction of the equations, for any C < 11/8 = 1.375 (and any 0 < ε ≤ 1/8). The previous best result, standing for over 15 years, had 5/4 in place of 11/8. Our result provides the best known NP-hardness even for the Unique-Games problem, and it also holds for the special case of Max-Cut. The precise factor 11 8 is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2. Our proof is by a modified gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, any such reduction can never establish a hardness factor C greater than 2.54. Previously, no such limitation on gadget reductions was known.
|
|
| 46. |
- Håstad, Johan, 1960-, et al.
(författare)
-
Improved NP-Inapproximability for 2-Variable Linear Equations
- 2017
-
Ingår i: Theory of Computing. - : UNIV CHICAGO, DEPT COMPUTER SCIENCE. - 1557-2862. ; 13
-
Tidskriftsartikel (refereegranskat)abstract
- An instance of the 2-Lin(2) problem is a system of equations of the form "x(i)+x(j)= b (mod 2)." Given such a system in which it is possible to satisfy all but an epsilon fraction of the equations, we show it is NP-hard to satisfy all but a C epsilon fraction of equations, for any C < 11/8 - 1.375 (and any 0 < epsilon <= 1/8). The previous best result, standing for over 15 years, had 5/4 in place of 11/8. Our result provides the best known NP-hardness even for the Unique-Games problem, and it also holds for the special case of Max-Cut. The precise factor 11/8 is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2. Our proof is by a modified gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, any such reduction can never establish a hardness factor C greater than 2.54. Previously, no such limitations on gadget reductions was known.
|
|
| 47. |
|
|
| 48. |
- Håstad, Johan
(författare)
-
On bounded occurrence constraint satisfaction
- 2000
-
Ingår i: Information Processing Letters. - 0020-0190 .- 1872-6119. ; 74:02-jan, s. 1-6
-
Tidskriftsartikel (refereegranskat)abstract
- An approximation algorithm for a constraint satisfaction problem is said to be nontrivial if its performance ratio is strictly superior to the expected performance of the algorithm which simply chooses a random assignment. We prove that any constraint satisfaction problem where each variable appears a bounded number of times admits a nontrivial polynomial time approximation algorithm.
|
|
| 49. |
- Håstad, Johan
(författare)
-
On Nontrivial Approximation of CSPs
- 2007
-
Konferensbidrag (refereegranskat)abstract
- Constraint satisfaction problems, more simply called CSPs are central in computer science, the most famous probably being Satisfiability, SAT, the basic NP-complete problem. In this talk we survey some results about the optimization version of CSPs where we want to satisfy as many constraints as possible. One very simple approach to a CSP is to give random values to the variables. It turns out that for some CSPs, one example being Max-3Sat, unless P=NP, there is no polynomial time algorithm that can achieve a an approximation ratio that is superior to what is obtained by this trivial strategy. Some other CSPs, Max-Cut being a prime example, do allow very interesting non-trivial approximation algorithms which do give an approximation ratio that is substantially better than that obtained by a random assignment. These results hint at a general classification problem of determining which CSPs do admit a polynomial time approximation algorithm that beats the random assignment by a constant factor. Positive results giving such algorithms tend to be based on semi-definite programming while the PCP theorem is the central tool for proving negative result. We describe many of the known results in the area and also discuss some of the open problems.
|
|
| 50. |
- Håstad, Johan, 1960-
(författare)
-
On small-depth Frege proofs for PHP
- 2023
-
Ingår i: Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. - : Institute of Electrical and Electronics Engineers (IEEE). ; , s. 37-49
-
Konferensbidrag (refereegranskat)abstract
- We study Frege proofs for the one-to-one graph Pigeon Hole Principle defined on the n × n grid where n is odd. We are interested in the case where each formula in the proof is a depth d formula in the basis given by ∧, ∨, and ¬. We prove that in this situation the proof needs to be of size exponential in nΩ(1/d). If we restrict the size of each line in the proof to be of size M then the number of lines needed is exponential in n /(log M)O(d). The main technical component of the proofs is to design a new family of random restrictions and to prove the appropriate switching lemmas.
|
|
