2 Search Results for "H�stad, Johan"

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.24
Bounded Independence vs. Moduli

Authors: Ravi Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
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 S_m := {x in {0,1}^n: sum_i x_i equiv 0 mod m}, where m is any integer. We show that Omega(n/m^2 log m) <= 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 S_m. For any fixed odd m there is k \ge (1 - Omega(1))n such that any k-wise uniform distribution lands in S_m with probability exponentially close to |S_m|/2^n; and this result is false for any even m.
Cite as

Ravi Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola. Bounded Independence vs. Moduli. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 24:1-24:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{boppana_et_al:LIPIcs.APPROX-RANDOM.2016.24,
  author =	{Boppana, Ravi and H\r{a}stad, Johan and Lee, Chin Ho and Viola, Emanuele},
  title =	{{Bounded Independence vs. Moduli}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{24:1--24:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.24},
  URN =		{urn:nbn:de:0030-drops-66475},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.24},
  annote =	{Keywords: Bounded independence, Modulus}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.341
Improved NP-Inapproximability for 2-Variable Linear Equations

Authors: Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O’Donnell, and John Wright

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
An instance of the 2-Lin(2) problem is a system of equations of the form "x_i + x_j = b (mod 2)". Given such a system in which it's possible to satisfy all but an epsilon fraction of the equations, we show it is NP-hard to satisfy all but a C*epsilon fraction of the equations, for any C < 11/8 = 1.375 (and any 0 < epsilon <= 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.
Cite as

Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O’Donnell, and John Wright. Improved NP-Inapproximability for 2-Variable Linear Equations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 341-360, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{hastad_et_al:LIPIcs.APPROX-RANDOM.2015.341,
  author =	{H\r{a}stad, Johan and Huang, Sangxia and Manokaran, Rajsekar and O’Donnell, Ryan and Wright, John},
  title =	{{Improved NP-Inapproximability for 2-Variable Linear Equations}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{341--360},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.341},
  URN =		{urn:nbn:de:0030-drops-53112},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.341},
  annote =	{Keywords: approximability, unique games, linear equation, gadget, linear programming}
}
  • Refine by Author
  • 2 Håstad, Johan
  • 1 Boppana, Ravi
  • 1 Huang, Sangxia
  • 1 Lee, Chin Ho
  • 1 Manokaran, Rajsekar
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Bounded independence
  • 1 Modulus
  • 1 approximability
  • 1 gadget
  • 1 linear equation
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2015
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact