Change search
Link to record
Permanent link

Direct link
BETA
Publications (10 of 58) Show all publications
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 < 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.

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
Barak, B., Gopalan, P., Håstad, J., Meka, R., Raghavendra, P. & Steurer, D. (2015). Making the long code shorter. Paper presented at 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012; New Brunswick, NJ; 20 October 2012 through 23 October 2012. SIAM journal on computing (Print), 44(5), 1287-1324
Open this publication in new window or tab >>Making the long code shorter
Show others...
2015 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 44, no 5, p. 1287-1324Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Society for Industrial and Applied Mathematics, 2015
Keywords
Cayley graphs, Expanders, Hardness of approximation, Locally testable codes, Codes (symbols), Eigenvalues and eigenfunctions, Hardness, Semi-definite programming, Sherali-adams hierarchies, Small-set expansions, Unique games conjecture, Graph theory
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:kth:diva-181506 (URN)10.1137/130929394 (DOI)000364454500006 ()2-s2.0-84945903744 (Scopus ID)
Conference
53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012; New Brunswick, NJ; 20 October 2012 through 23 October 2012
Note

QC 20160203

Available from: 2016-02-03 Created: 2016-02-02 Last updated: 2017-11-30Bibliographically approved
Austrin, P., Håstad, J. & Guruswami, V. (2014). (2 + epsilon)-Sat Is NP-hard. In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS: . Paper presented at 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014, 18 October 2014 through 21 October 2014 (pp. 1-10).
Open this publication in new window or tab >>(2 + epsilon)-Sat Is NP-hard
2014 (English)In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2014, p. 1-10Conference paper, Published paper (Refereed)
Abstract [en]

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.

Series
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, ISSN 0272-5428 ; 6978984
Keywords
complexity dichotomy, Constraint satisfaction, discrepancy, polymorphisms, probabilistically checkable proofs, promise problems
National Category
Computer Sciences
Identifiers
urn:nbn:se:kth:diva-167553 (URN)10.1109/FOCS.2014.9 (DOI)000366324300001 ()2-s2.0-84919962415 (Scopus ID)9781479965175 (ISBN)
Conference
55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014, 18 October 2014 through 21 October 2014
Note

QC 20150608

Available from: 2015-06-08 Created: 2015-05-22 Last updated: 2018-01-11Bibliographically approved
Blais, E., Håstad, J., Servedio, R. A. & Tan, L.-Y. (2014). On DNF Approximators for Monotone Boolean Functions. In: Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. Paper presented at 41st International Colloquium on Automata, Languages and Programming, July 08-11, 2014, Copenhagen, Denmark (pp. 235-246). Springer Berlin/Heidelberg, 8572
Open this publication in new window or tab >>On DNF Approximators for Monotone Boolean Functions
2014 (English)In: Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, Springer Berlin/Heidelberg, 2014, Vol. 8572, p. 235-246Conference paper, Published paper (Refereed)
Abstract [en]

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

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2014
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 8572
Keywords
Boolean functions, Approximators, Classical theorems, Disjunctive normal form, Exact computations, Monotone Boolean functions, Monotone functions, Non-trivial, Upper Bound
National Category
Computer and Information Sciences
Identifiers
urn:nbn:se:kth:diva-166367 (URN)10.1007/978-3-662-43948-7_20 (DOI)000352643300022 ()2-s2.0-84904165616 (Scopus ID)978-3-662-43948-7 (ISBN)
Conference
41st International Colloquium on Automata, Languages and Programming, July 08-11, 2014, Copenhagen, Denmark
Note

QC 20150507

Available from: 2015-05-07 Created: 2015-05-07 Last updated: 2018-01-11Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0002-5379-345X

Search in DiVA

Show all publications