kth.sePublications
Change search
Link to record
Permanent link

Direct link
Publications (10 of 74) Show all publications
Håstad, J. (2023). On small-depth Frege proofs for PHP. In: Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023: . Paper presented at 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, United States of America, Nov 6 2023 - Nov 9 2023 (pp. 37-49). Institute of Electrical and Electronics Engineers (IEEE)
Open this publication in new window or tab >>On small-depth Frege proofs for PHP
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]

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.

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
Note

QC 20240130

Available from: 2024-01-25 Created: 2024-01-25 Last updated: 2024-07-01Bibliographically approved
Risse, K. & Håstad, J. (2022). On bounded depth proofs for Tseitin formulas on the grid; revisited. In: 2022 IEEE 63RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS): . Paper presented at 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 31 October - 3 November 2022, Denver, CO, USA (pp. 1138-1149). Institute of Electrical and Electronics Engineers (IEEE)
Open this publication in new window or tab >>On bounded depth proofs for Tseitin formulas on the grid; revisited
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]

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

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
Note

Part of proceedings: ISBN 978-166545519-0

QC 20221011

Available from: 2022-10-04 Created: 2022-10-04 Last updated: 2023-02-28Bibliographically approved
Guruswami, V. & Håstad, J. (2021). Explicit two-deletion codes with redundancy matching the existential bound. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms: . Paper presented at 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, 10 January 2021 through 13 January 2021, Alexandria, Virginia, US, Virtual. (pp. 21-32). Association for Computing Machinery
Open this publication in new window or tab >>Explicit two-deletion codes with redundancy matching the existential bound
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]

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.

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

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 approved
Guruswami, V. & Håstad, J. (2021). Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound. IEEE Transactions on Information Theory, 67(10), 6384-6394
Open this publication in new window or tab >>Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound
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]

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.

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)
Note

QC 20211014

Available from: 2021-10-14 Created: 2021-10-14 Last updated: 2022-06-25Bibliographically approved
Håstad, J. (2021). On Small-depth Frege Proofs for Tseitin for Grids. Journal of the ACM, 68(1), Article ID 1.
Open this publication in new window or tab >>On Small-depth Frege Proofs for Tseitin for Grids
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]

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.

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 ()
Note

QC 20210406

Available from: 2021-04-06 Created: 2021-04-06 Last updated: 2022-06-25Bibliographically approved
Austrin, P., Brown-Cohen, J. & Håstad, J. (2021). Optimal inapproximability with universal factor graphs. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms: . Paper presented at 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, 10 January 2021 through 13 January 2021, Alexandria, Virtual (pp. 434-453). Association for Computing Machinery
Open this publication in new window or tab >>Optimal inapproximability with universal factor graphs
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]

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

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
Note

QC 20220225

Part of proceedings ISBN: 9781611976465

Available from: 2022-02-25 Created: 2022-02-25 Last updated: 2022-06-25Bibliographically approved
Håstad, J., Lagarde, G. & Swernofsky, J. (2020). d-Galvin families. The Electronic Journal of Combinatorics, 27(1), Article ID P1.36.
Open this publication in new window or tab >>d-Galvin families
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]

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.

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)
Note

QC 20200310

Available from: 2020-03-10 Created: 2020-03-10 Last updated: 2024-03-15Bibliographically approved
Boppana, R., Håstad, J., Lee, C. H. & Viola, E. (2019). Bounded Independence versus Symmetric Tests. ACM Transactions on Computation Theory, 11(4), Article ID 21.
Open this publication in new window or tab >>Bounded Independence versus Symmetric Tests
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]

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.

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)
Note

QC 20191219

Available from: 2019-12-19 Created: 2019-12-19 Last updated: 2022-06-26Bibliographically approved
Håstad, J. (2018). Knuth Prize Lecture: On the difficulty of approximating boolean max-CSPs. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS): . Paper presented at 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, 7 October 2018 through 9 October 2018. IEEE Computer Society, Article ID 8555141.
Open this publication in new window or tab >>Knuth Prize Lecture: On the difficulty of approximating boolean max-CSPs
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
Note

QC 20190123

Available from: 2019-01-23 Created: 2019-01-23 Last updated: 2022-06-26Bibliographically approved
Austrin, P., Guruswami, V. & Håstad, J. (2017). (2 + ϵ)-SAT is NP-hard. SIAM journal on computing (Print), 46(5), 1554-1573
Open this publication in new window or tab >>(2 + ϵ)-SAT is NP-hard
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]

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.

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)
Note

QC 20171116

Available from: 2017-11-16 Created: 2017-11-16 Last updated: 2024-03-15Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-5379-345X

Search in DiVA

Show all publications