kth.sePublications

Please wait ... |

Link to record
http://kth.diva-portal.org/smash/person.jsf?pid=authority-person:31572 $(function(){PrimeFaces.cw("InputTextarea","widget_formSmash_upper_j_idt142_recordDirectLink",{id:"formSmash:upper:j_idt142:recordDirectLink",widgetVar:"widget_formSmash_upper_j_idt142_recordDirectLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt142_j_idt144",{id:"formSmash:upper:j_idt142:j_idt144",widgetVar:"widget_formSmash_upper_j_idt142_j_idt144",target:"formSmash:upper:j_idt142:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Permanent link

Direct link

Håstad, Johanorcid.org/0000-0002-5379-345X

Open this publication in new window or tab >>On small-depth Frege proofs for PHP### Håstad, Johan

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_some",{id:"formSmash:j_idt204:0:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_otherAuthors",{id:"formSmash:j_idt204:0:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_otherAuthors",multiple:true}); 2023 (English)In: Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023, Institute of Electrical and Electronics Engineers (IEEE) , 2023, p. 37-49Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Institute of Electrical and Electronics Engineers (IEEE), 2023
##### Keywords

complexity of proof procedures
##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:kth:diva-342646 (URN)10.1109/FOCS57990.2023.00010 (DOI)001137125900004 ()2-s2.0-85182392917 (Scopus ID)
##### Conference

64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, United States of America, Nov 6 2023 - Nov 9 2023
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_j_idt379",{id:"formSmash:j_idt204:0:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_j_idt385",{id:"formSmash:j_idt204:0:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_0_j_idt208_j_idt391",{id:"formSmash:j_idt204:0:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_0_j_idt208_j_idt391",multiple:true});
#####

##### Note

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).

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.

QC 20240130

Available from: 2024-01-25 Created: 2024-01-25 Last updated: 2024-07-01Bibliographically approvedOpen this publication in new window or tab >>On bounded depth proofs for Tseitin formulas on the grid; revisited### Risse, Kilian

### Håstad, Johan

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_some",{id:"formSmash:j_idt204:1:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_otherAuthors",{id:"formSmash:j_idt204:1:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_otherAuthors",multiple:true}); 2022 (English)In: 2022 IEEE 63RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), Institute of Electrical and Electronics Engineers (IEEE) , 2022, p. 1138-1149Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Institute of Electrical and Electronics Engineers (IEEE), 2022
##### Series

Annual IEEE Symposium on Foundations of Computer Science, ISSN 0272-5428
##### Keywords

proof complexity, bounded depth Frege
##### National Category

Discrete Mathematics
##### Identifiers

urn:nbn:se:kth:diva-319642 (URN)10.1109/FOCS54457.2022.00110 (DOI)000909382900104 ()2-s2.0-85146343295 (Scopus ID)
##### Conference

2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 31 October - 3 November 2022, Denver, CO, USA
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_j_idt379",{id:"formSmash:j_idt204:1:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_j_idt385",{id:"formSmash:j_idt204:1:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_1_j_idt208_j_idt391",{id:"formSmash:j_idt204:1:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_1_j_idt208_j_idt391",multiple:true});
#####

##### Note

KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).

We study Frege proofs using depth-d Boolean formulas for the Tseitin contradiction on n x n grids. We prove that if each line in the proof is of size M then the number of lines is exponential in n/(logM)(O(d)). This strengthens a recent result of Pitassi et al. [12]. The key technical step is a multi-switching lemma extending the switching lemma of Hastad [8] for a space of restrictions related to the Tseitin contradiction. The strengthened lemma also allows us to improve the lower bound for standard proof size of bounded depth Frege refutations from exponential in (Omega) over tilde (n(1/59d)) to exponential in (Omega) over tilde (n(1/(2d-1))).

Part of proceedings: ISBN 978-166545519-0

QC 20221011

Available from: 2022-10-04 Created: 2022-10-04 Last updated: 2023-02-28Bibliographically approvedOpen this publication in new window or tab >>Explicit two-deletion codes with redundancy matching the existential bound### Guruswami, V.

### Håstad, Johan

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_some",{id:"formSmash:j_idt204:2:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_otherAuthors",{id:"formSmash:j_idt204:2:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_otherAuthors",multiple:true}); 2021 (English)In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery , 2021, p. 21-32Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Association for Computing Machinery, 2021
##### Keywords

Algorithms, Code-words, Explicit constructions, Lower order terms, Binary codes
##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:kth:diva-309247 (URN)2-s2.0-85105290496 (Scopus ID)
##### Conference

32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, 10 January 2021 through 13 January 2021, Alexandria, Virginia, US, Virtual.
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_j_idt379",{id:"formSmash:j_idt204:2:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_j_idt385",{id:"formSmash:j_idt204:2:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_2_j_idt208_j_idt391",{id:"formSmash:j_idt204:2:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_2_j_idt208_j_idt391",multiple:true});
#####

##### Note

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).

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.

QC 20220228

Part of proceedings ISBN: 978-1-61197-646-5

Available from: 2022-02-28 Created: 2022-02-28 Last updated: 2022-06-25Bibliographically approvedOpen this publication in new window or tab >>Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound### Guruswami, Venkatesan

### Håstad, Johan

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_some",{id:"formSmash:j_idt204:3:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_otherAuthors",{id:"formSmash:j_idt204:3:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_otherAuthors",multiple:true}); 2021 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 67, no 10, p. 6384-6394Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Institute of Electrical and Electronics Engineers (IEEE), 2021
##### Keywords

Deletion codes, list decoding, explicit constructions
##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:kth:diva-303041 (URN)10.1109/TIT.2021.3069446 (DOI)000696077200012 ()2-s2.0-85103795877 (Scopus ID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_j_idt379",{id:"formSmash:j_idt204:3:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_j_idt385",{id:"formSmash:j_idt204:3:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_3_j_idt208_j_idt391",{id:"formSmash:j_idt204:3:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_3_j_idt208_j_idt391",multiple:true});
#####

##### Note

Carnegie Mellon Univ, Dept Comp Sci, Pittsburgh, PA 15213 USA..

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).

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.

QC 20211014

Available from: 2021-10-14 Created: 2021-10-14 Last updated: 2022-06-25Bibliographically approvedOpen this publication in new window or tab >>On Small-depth Frege Proofs for Tseitin for Grids### Håstad, Johan

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_some",{id:"formSmash:j_idt204:4:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_otherAuthors",{id:"formSmash:j_idt204:4:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_otherAuthors",multiple:true}); 2021 (English)In: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 68, no 1, article id 1Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Association for Computing Machinery (ACM), 2021
##### Keywords

Small-depth formulas, Frege proofs, switching lemma
##### National Category

Computer and Information Sciences
##### Identifiers

urn:nbn:se:kth:diva-292296 (URN)10.1145/3425606 (DOI)000621424400001 ()
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_j_idt379",{id:"formSmash:j_idt204:4:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_j_idt385",{id:"formSmash:j_idt204:4:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_4_j_idt208_j_idt391",{id:"formSmash:j_idt204:4:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_4_j_idt208_j_idt391",multiple:true});
#####

##### Note

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).

We prove that a small-depth Frege refutation of the Tseitin contradiction on the grid requires subexponential size. We conclude that polynomial size Frege refutations of the Tseitin contradiction must use formulas of almost logarithmic depth.

QC 20210406

Available from: 2021-04-06 Created: 2021-04-06 Last updated: 2022-06-25Bibliographically approvedOpen this publication in new window or tab >>Optimal inapproximability with universal factor graphs### Austrin, Per

### Brown-Cohen, Jonah

### Håstad, Johan

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_some",{id:"formSmash:j_idt204:5:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_otherAuthors",{id:"formSmash:j_idt204:5:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_otherAuthors",multiple:true}); 2021 (English)In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery , 2021, p. 434-453Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Association for Computing Machinery, 2021
##### Keywords

Optimization, Bipartite graphs, Factor graphs, Long codes, Optimal inapproximability, Technical tools, Constraint satisfaction problems
##### National Category

Computer Sciences
##### Identifiers

urn:nbn:se:kth:diva-309245 (URN)2-s2.0-85105336082 (Scopus ID)
##### Conference

32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, 10 January 2021 through 13 January 2021, Alexandria, Virtual
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_j_idt379",{id:"formSmash:j_idt204:5:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_j_idt385",{id:"formSmash:j_idt204:5:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_5_j_idt208_j_idt391",{id:"formSmash:j_idt204:5:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_5_j_idt208_j_idt391",multiple:true});
#####

##### Note

KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.

KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).

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”.

QC 20220225

Part of proceedings ISBN: 9781611976465

Available from: 2022-02-25 Created: 2022-02-25 Last updated: 2022-06-25Bibliographically approvedOpen this publication in new window or tab >>d-Galvin families### Håstad, Johan

### Lagarde, Guillaume

### Swernofsky, Joseph

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_some",{id:"formSmash:j_idt204:6:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_otherAuthors",{id:"formSmash:j_idt204:6:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_otherAuthors",multiple:true}); 2020 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 27, no 1, article id P1.36Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

ELECTRONIC JOURNAL OF COMBINATORICS, 2020
##### National Category

Mathematics
##### Identifiers

urn:nbn:se:kth:diva-269463 (URN)10.37236/8432 (DOI)000513911100005 ()2-s2.0-85079448290 (Scopus ID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_j_idt379",{id:"formSmash:j_idt204:6:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_j_idt385",{id:"formSmash:j_idt204:6:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_6_j_idt208_j_idt391",{id:"formSmash:j_idt204:6:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_6_j_idt208_j_idt391",multiple:true});
#####

##### Note

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).

Univ Bordeaux, LaBRI, Bordeaux, France..

KTH, School of Electrical Engineering and Computer Science (EECS).

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.

QC 20200310

Available from: 2020-03-10 Created: 2020-03-10 Last updated: 2024-03-15Bibliographically approvedOpen this publication in new window or tab >>Bounded Independence versus Symmetric Tests### Boppana, Ravi

### Håstad, Johan

### Lee, Chin Ho

### Viola, Emanuele

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_some",{id:"formSmash:j_idt204:7:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_otherAuthors",{id:"formSmash:j_idt204:7:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_otherAuthors",multiple:true}); 2019 (English)In: ACM Transactions on Computation Theory, ISSN 1942-3454, E-ISSN 1942-3462, Vol. 11, no 4, article id 21Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

ASSOC COMPUTING MACHINERY, 2019
##### Keywords

Pseudorandomness, bounded independence, thresholds, modulus, symmetric functions
##### National Category

Computational Mathematics
##### Identifiers

urn:nbn:se:kth:diva-265221 (URN)10.1145/3337783 (DOI)000496750000003 ()2-s2.0-85075582195 (Scopus ID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_j_idt379",{id:"formSmash:j_idt204:7:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_j_idt385",{id:"formSmash:j_idt204:7:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_7_j_idt208_j_idt391",{id:"formSmash:j_idt204:7:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_7_j_idt208_j_idt391",multiple:true});
#####

##### Note

MIT, Dept Math, Cambridge, MA 02142 USA..

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).

Northeastern Univ, Khoury Coll Comp Sci, 440 Huntington Ave,202 West Village H, Boston, MA 02115 USA..

Northeastern Univ, Khoury Coll Comp Sci, 440 Huntington Ave,202 West Village H, Boston, MA 02115 USA..

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.

QC 20191219

Available from: 2019-12-19 Created: 2019-12-19 Last updated: 2022-06-26Bibliographically approvedOpen this publication in new window or tab >>Knuth Prize Lecture: On the difficulty of approximating boolean max-CSPs### Håstad, Johan

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_some",{id:"formSmash:j_idt204:8:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_otherAuthors",{id:"formSmash:j_idt204:8:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_otherAuthors",multiple:true}); 2018 (English)In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2018, article id 8555141Conference paper, Published paper (Refereed)
##### Place, publisher, year, edition, pages

IEEE Computer Society, 2018
##### Series

Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, ISSN 0272-5428
##### Keywords

Approximation algorithms, Approximation hardness, Approximation resistance, Constraint satisfaction problems
##### National Category

Mathematics
##### Identifiers

urn:nbn:se:kth:diva-241526 (URN)10.1109/FOCS.2018.00063 (DOI)000455014500054 ()2-s2.0-85059818202 (Scopus ID)9781538642306 (ISBN)
##### Conference

59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, 7 October 2018 through 9 October 2018
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_j_idt379",{id:"formSmash:j_idt204:8:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_j_idt385",{id:"formSmash:j_idt204:8:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_8_j_idt208_j_idt391",{id:"formSmash:j_idt204:8:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_8_j_idt208_j_idt391",multiple:true});
#####

##### Note

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).

QC 20190123

Available from: 2019-01-23 Created: 2019-01-23 Last updated: 2022-06-26Bibliographically approvedOpen this publication in new window or tab >>(2 + ϵ)-SAT is NP-hard### Austrin, Per

### Guruswami, V.

### Håstad, Johan

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_some",{id:"formSmash:j_idt204:9:j_idt208:some",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_otherAuthors",{id:"formSmash:j_idt204:9:j_idt208:otherAuthors",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_otherAuthors",multiple:true}); 2017 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 46, no 5, p. 1554-1573Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Society for Industrial and Applied Mathematics Publications, 2017
##### Keywords

Complexity dichotomy, Constraint satisfaction, Discrepancy, Hypergraph coloring, Polymorphisms, Probabilistically checkable proofs
##### National Category

Computer and Information Sciences
##### Identifiers

urn:nbn:se:kth:diva-217605 (URN)10.1137/15M1006507 (DOI)000416763900003 ()2-s2.0-85032973667 (Scopus ID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_j_idt379",{id:"formSmash:j_idt204:9:j_idt208:j_idt379",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_j_idt379",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_j_idt385",{id:"formSmash:j_idt204:9:j_idt208:j_idt385",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_j_idt385",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt204_9_j_idt208_j_idt391",{id:"formSmash:j_idt204:9:j_idt208:j_idt391",widgetVar:"widget_formSmash_j_idt204_9_j_idt208_j_idt391",multiple:true});
#####

##### Note

KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.

KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.

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.

QC 20171116

Available from: 2017-11-16 Created: 2017-11-16 Last updated: 2024-03-15Bibliographically approved