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_idt122_recordDirectLink",{id:"formSmash:upper:j_idt122:recordDirectLink",widgetVar:"widget_formSmash_upper_j_idt122_recordDirectLink",autoResize:true});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt122_j_idt124",{id:"formSmash:upper:j_idt122:j_idt124",widgetVar:"widget_formSmash_upper_j_idt122_j_idt124",target:"formSmash:upper:j_idt122: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 >>d-Galvin families### Håstad, Johan

### Lagarde, Guillaume

### Swernofsky, Joseph

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_some",{id:"formSmash:j_idt184:0:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_otherAuthors",{id:"formSmash:j_idt184:0:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_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)000513911100005 ()2-s2.0-85079448290 (Scopus ID)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_j_idt359",{id:"formSmash:j_idt184:0:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_j_idt365",{id:"formSmash:j_idt184:0:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_0_j_idt188_j_idt371",{id:"formSmash:j_idt184:0:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_0_j_idt188_j_idt371",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: 2020-03-10Bibliographically 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_idt184_1_j_idt188_some",{id:"formSmash:j_idt184:1:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_otherAuthors",{id:"formSmash:j_idt184:1:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_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_idt184_1_j_idt188_j_idt359",{id:"formSmash:j_idt184:1:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_j_idt365",{id:"formSmash:j_idt184:1:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_1_j_idt188_j_idt371",{id:"formSmash:j_idt184:1:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_1_j_idt188_j_idt371",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: 2019-12-19Bibliographically 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_idt184_2_j_idt188_some",{id:"formSmash:j_idt184:2:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_otherAuthors",{id:"formSmash:j_idt184:2:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_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_idt184_2_j_idt188_j_idt359",{id:"formSmash:j_idt184:2:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_j_idt365",{id:"formSmash:j_idt184:2:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_2_j_idt188_j_idt371",{id:"formSmash:j_idt184:2:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_2_j_idt188_j_idt371",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: 2019-09-18Bibliographically approvedOpen this publication in new window or tab >>An Improved Bound on the Fraction of Correctable Deletions### Bukh, Boris

### Guruswami, Venkatesan

### Håstad, Johan

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_some",{id:"formSmash:j_idt184:3:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_otherAuthors",{id:"formSmash:j_idt184:3:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_otherAuthors",multiple:true}); 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]

##### 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
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_j_idt359",{id:"formSmash:j_idt184:3:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_j_idt365",{id:"formSmash:j_idt184:3:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_3_j_idt188_j_idt371",{id:"formSmash:j_idt184:3:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_3_j_idt188_j_idt371",multiple:true});
#####

##### Note

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

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.

QC 20170216

Available from: 2017-02-16 Created: 2017-02-16 Last updated: 2018-01-13Bibliographically 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_idt184_4_j_idt188_some",{id:"formSmash:j_idt184:4:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_otherAuthors",{id:"formSmash:j_idt184:4:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_otherAuthors",multiple:true}); 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]

##### 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
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_j_idt359",{id:"formSmash:j_idt184:4:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_j_idt365",{id:"formSmash:j_idt184:4:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_4_j_idt188_j_idt371",{id:"formSmash:j_idt184:4:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_4_j_idt188_j_idt371",multiple:true});
#####

##### Note

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

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.

QC 20180109

Available from: 2018-01-09 Created: 2018-01-09 Last updated: 2018-02-06Bibliographically approvedOpen this publication in new window or tab >>On the Hardness of Approximating Balanced Homogeneous 3-Lin### Håstad, Johan

### Manokaran, Rajsekar

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_some",{id:"formSmash:j_idt184:5:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_otherAuthors",{id:"formSmash:j_idt184:5:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_otherAuthors",multiple:true}); 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]

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_j_idt359",{id:"formSmash:j_idt184:5:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_j_idt365",{id:"formSmash:j_idt184:5:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_5_j_idt188_j_idt371",{id:"formSmash:j_idt184:5:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_5_j_idt188_j_idt371",multiple:true});
#####

##### Note

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

IIT Madras, Madras, Tamil Nadu, India.;Indian Inst Technol, Madras, Tamil Nadu, India..

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.

QC 20180618

Available from: 2018-06-18 Created: 2018-06-18 Last updated: 2018-06-18Bibliographically approvedOpen this publication in new window or tab >>SUPER-POLYLOGARITHMIC HYPERGRAPH COLORING HARDNESS VIA LOW-DEGREE LONG CODES### Guruswami, Venkatesan

### Harsha, Prahladh

### Håstad, Johan

### Srinivasan, Srikanth

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_some",{id:"formSmash:j_idt184:6:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_some",multiple:true}); ### Varma, Girish

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_otherAuthors",{id:"formSmash:j_idt184:6:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_otherAuthors",multiple:true}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt184_6_j_idt188_j_idt202",{id:"formSmash:j_idt184:6:j_idt188:j_idt202",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt202",onLabel:"Hide others...",offLabel:"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]

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_j_idt359",{id:"formSmash:j_idt184:6:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_j_idt365",{id:"formSmash:j_idt184:6:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_6_j_idt188_j_idt371",{id:"formSmash:j_idt184:6:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_6_j_idt188_j_idt371",multiple:true});
#####

##### Note

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

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.

QC 20170412

Available from: 2017-04-12 Created: 2017-04-12 Last updated: 2018-01-13Bibliographically approvedOpen this publication in new window or tab >>Bounded Independence vs. Moduli### Boppana, R.

### Håstad, Johan

### Lee, C. H.

### Viola, E.

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_some",{id:"formSmash:j_idt184:7:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_otherAuthors",{id:"formSmash:j_idt184:7:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_otherAuthors",multiple:true}); 2016 (English)In: Leibniz International Proceedings in Informatics, LIPIcs, Dagstuhl Publishing , 2016Conference paper, Published paper (Refereed)
##### Abstract [en]

##### 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
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_j_idt359",{id:"formSmash:j_idt184:7:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_j_idt365",{id:"formSmash:j_idt184:7:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_7_j_idt188_j_idt371",{id:"formSmash:j_idt184:7:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_7_j_idt188_j_idt371",multiple:true});
#####

##### Note

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

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.

QC 20170309

Available from: 2017-03-09 Created: 2017-03-09 Last updated: 2017-03-09Bibliographically approvedOpen this publication in new window or tab >>The Square Lattice Shuffle (vol 29, pg 466, 2006)### Håstad, Johan

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_some",{id:"formSmash:j_idt184:8:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_otherAuthors",{id:"formSmash:j_idt184:8:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_otherAuthors",multiple:true}); 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)
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_j_idt359",{id:"formSmash:j_idt184:8:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_j_idt365",{id:"formSmash:j_idt184:8:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_8_j_idt188_j_idt371",{id:"formSmash:j_idt184:8:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_8_j_idt188_j_idt371",multiple:true});
#####

##### Note

KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.

QC 20160207

Available from: 2016-02-07 Created: 2016-02-01 Last updated: 2018-01-10Bibliographically approvedOpen this publication in new window or tab >>Improved NP-inapproximability for 2-variable linear equations### Håstad, Johan

### Huang, Sangxia

### Manokaran, R.

### O’Donnell, R.

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_some",{id:"formSmash:j_idt184:9:j_idt188:some",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_some",multiple:true}); ### Wright, J.

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_otherAuthors",{id:"formSmash:j_idt184:9:j_idt188:otherAuthors",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_otherAuthors",multiple:true}); Show others...PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt184_9_j_idt188_j_idt202",{id:"formSmash:j_idt184:9:j_idt188:j_idt202",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_j_idt202",onLabel:"Hide others...",offLabel:"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]

##### 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
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_j_idt359",{id:"formSmash:j_idt184:9:j_idt188:j_idt359",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_j_idt359",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_j_idt365",{id:"formSmash:j_idt184:9:j_idt188:j_idt365",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_j_idt365",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt184_9_j_idt188_j_idt371",{id:"formSmash:j_idt184:9:j_idt188:j_idt371",widgetVar:"widget_formSmash_j_idt184_9_j_idt188_j_idt371",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.

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.

QC 20160517

Available from: 2016-05-17 Created: 2016-05-17 Last updated: 2016-05-17Bibliographically approved