Change search
Link to record
Permanent link

Direct link
BETA
Publications (10 of 62) Show all publications
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)000513911100005 ()2-s2.0-85079448290 (Scopus ID)
Note

QC 20200310

Available from: 2020-03-10 Created: 2020-03-10 Last updated: 2020-03-10Bibliographically 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: 2019-12-19Bibliographically 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: 2019-09-18Bibliographically approved
Bukh, B., Guruswami, V. & Håstad, J. (2017). An Improved Bound on the Fraction of Correctable Deletions. Paper presented at ACM-SIAM Symposium on Discrete Algorithms, JAN 10-12, 2016, Arlington, VA. IEEE Transactions on Information Theory, 63(1), 93-103
Open this publication in new window or tab >>An Improved Bound on the Fraction of Correctable Deletions
2017 (English)In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 63, no 1, p. 93-103Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
IEEE, 2017
Keywords
Error-correction, deletion codes, combinatorics, concatenated coding
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:kth:diva-201242 (URN)10.1109/TIT.2016.2621044 (DOI)000391740000007 ()2-s2.0-85008473100 (Scopus ID)
Conference
ACM-SIAM Symposium on Discrete Algorithms, JAN 10-12, 2016, Arlington, VA
Note

QC 20170216

Available from: 2017-02-16 Created: 2017-02-16 Last updated: 2018-01-13Bibliographically approved
Håstad, J. (2017). On small-depth Frege proofs for Tseitin for grids. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS): . Paper presented at 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), OCT 15-17, 2017, Berkeley, CA (pp. 97-108). IEEE
Open this publication in new window or tab >>On small-depth Frege proofs for Tseitin for grids
2017 (English)In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, p. 97-108Conference paper, Published paper (Refereed)
Abstract [en]

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

Place, publisher, year, edition, pages
IEEE, 2017
Series
Annual IEEE Symposium on Foundations of Computer Science, ISSN 0272-5428
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:kth:diva-220658 (URN)10.1109/FOCS.2017.18 (DOI)000417425300009 ()2-s2.0-85041093986 (Scopus ID)978-1-5386-3464-6 (ISBN)
Conference
58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), OCT 15-17, 2017, Berkeley, CA
Note

QC 20180109

Available from: 2018-01-09 Created: 2018-01-09 Last updated: 2018-02-06Bibliographically approved
Håstad, J. & Manokaran, R. (2017). On the Hardness of Approximating Balanced Homogeneous 3-Lin. Theory of Computing, 13, Article ID UNSP 10.
Open this publication in new window or tab >>On the Hardness of Approximating Balanced Homogeneous 3-Lin
2017 (English)In: Theory of Computing, ISSN 1557-2862, E-ISSN 1557-2862, Vol. 13, article id UNSP 10Article in journal (Refereed) Published
Abstract [en]

We consider systems of homogeneous linear equations modulo 2 with three variables in each equation and study balanced assignments as solutions to such equations. We prove that it is hard to distinguish systems where there is a balanced assignment that satisfies a fraction 1-epsilon of the equations from systems where the best balanced assignment satisfies a fraction 1/2 + epsilon of the equations assuming that NP is not contained in quasipolynomial time. This improves on a similar result by Holmerin and Khot who relied on the assumption that NP is not contained in subexponential time. The key for the improvement is to replace long codes used by Holmerin and Khot by the low-degree long code.

Place, publisher, year, edition, pages
UNIV CHICAGO, DEPT COMPUTER SCIENCE, 2017
Keywords
hardness of approximation, inapproximability, probabilistically checkable proofs, constraint satisfaction problems, bisection, approximation resistance
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:kth:diva-230863 (URN)10.4086/toc.2017.v013a010 (DOI)000433613200001 ()2-s2.0-85044777803 (Scopus ID)
Note

QC 20180618

Available from: 2018-06-18 Created: 2018-06-18 Last updated: 2018-06-18Bibliographically approved
Guruswami, V., Harsha, P., Håstad, J., Srinivasan, S. & Varma, G. (2017). SUPER-POLYLOGARITHMIC HYPERGRAPH COLORING HARDNESS VIA LOW-DEGREE LONG CODES. SIAM journal on computing (Print), 46(1), 132-159
Open this publication in new window or tab >>SUPER-POLYLOGARITHMIC HYPERGRAPH COLORING HARDNESS VIA LOW-DEGREE LONG CODES
Show others...
2017 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 46, no 1, p. 132-159Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
SIAM PUBLICATIONS, 2017
Keywords
hardness of approximation, hypergraph coloring, short code
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:kth:diva-205167 (URN)10.1137/140995520 (DOI)000396677400005 ()2-s2.0-85014495830 (Scopus ID)
Note

QC 20170412

Available from: 2017-04-12 Created: 2017-04-12 Last updated: 2018-01-13Bibliographically approved
Boppana, R., Håstad, J., Lee, C. H. & Viola, E. (2016). Bounded Independence vs. Moduli. In: Leibniz International Proceedings in Informatics, LIPIcs: . Paper presented at 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016, 7 September 2016 through 9 September 2016. Dagstuhl Publishing
Open this publication in new window or tab >>Bounded Independence vs. Moduli
2016 (English)In: Leibniz International Proceedings in Informatics, LIPIcs, Dagstuhl Publishing , 2016Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Dagstuhl Publishing, 2016
Keywords
Bounded independence, Modulus, Approximation algorithms, Combinatorial optimization, Optimization, Random processes, Uniform distribution, Probability distributions
National Category
Mathematics
Identifiers
urn:nbn:se:kth:diva-202890 (URN)10.4230/LIPIcs.APPROX-RANDOM.2016.24 (DOI)2-s2.0-84990829261 (Scopus ID)9783959770187 (ISBN)
Conference
19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016, 7 September 2016 through 9 September 2016
Note

QC 20170309

Available from: 2017-03-09 Created: 2017-03-09 Last updated: 2017-03-09Bibliographically approved
Håstad, J. (2016). The Square Lattice Shuffle (vol 29, pg 466, 2006). Random structures & algorithms (Print), 48(1), 213-213
Open this publication in new window or tab >>The Square Lattice Shuffle (vol 29, pg 466, 2006)
2016 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 48, no 1, p. 213-213Article in journal (Refereed) Published
Place, publisher, year, edition, pages
Wiley-Blackwell, 2016
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:kth:diva-181374 (URN)10.1002/rsa.20620 (DOI)000367622800010 ()2-s2.0-84947976572 (Scopus ID)
Note

QC 20160207

Available from: 2016-02-07 Created: 2016-02-01 Last updated: 2018-01-10Bibliographically approved
Håstad, J., Huang, S., Manokaran, R., O’Donnell, R. & Wright, J. (2015). Improved NP-inapproximability for 2-variable linear equations. In: Leibniz International Proceedings in Informatics, LIPIcs: . Paper presented at 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015; Princeton UniversityPrinceton; United States (pp. 341-360). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, 40
Open this publication in new window or tab >>Improved NP-inapproximability for 2-variable linear equations
Show others...
2015 (English)In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH , 2015, Vol. 40, p. 341-360Conference paper, Published paper (Refereed)
Abstract [en]

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 &lt; 11/8 = 1.375 (and any 0 &lt; ε ≤ 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.

Place, publisher, year, edition, pages
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, 2015
National Category
Mathematical Analysis
Identifiers
urn:nbn:se:kth:diva-187142 (URN)10.4230/LIPIcs.APPROX-RANDOM.2015.341 (DOI)2-s2.0-84958547344 (Scopus ID)
Conference
18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015; Princeton UniversityPrinceton; United States
Note

QC 20160517

Available from: 2016-05-17 Created: 2016-05-17 Last updated: 2016-05-17Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-5379-345X

Search in DiVA

Show all publications