Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Making the long code shorter
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
Show others and affiliations
2015 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 44, no 5, 1287-1324 p.Article in journal (Refereed) Published
Resource type
Text
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. Vol. 44, no 5, 1287-1324 p.
Keyword [en]
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: urn:nbn:se:kth:diva-181506DOI: 10.1137/130929394ISI: 000364454500006Scopus ID: 2-s2.0-84945903744OAI: oai:DiVA.org:kth-181506DiVA: diva2:900131
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: 2016-02-03Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Theoretical Computer Science, TCS
In the same journal
SIAM journal on computing (Print)
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 104 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf