| 1. |
- 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”.
|
|
| 2. |
- 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.
|
|
| 3. |
- 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.
|
|
| 4. |
- 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.
|
|
| 5. |
- 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.
|
|
| 6. |
- 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.
|
|
| 7. |
- 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.
|
|
| 8. |
- 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.
|
|
| 9. |
|
|
| 10. |
- 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.
|
|
