onr:"swepub:oai:DiVA.org:kth-181506"
Sökning: onr:"swepub:oai:DiVA.org:kth-181506" > Making the long cod...
- 1 av 1
- Föregående post
- Nästa post
- Till träfflistan
- Barak, B. (författare)
Making the long code shorter
- Artikel/kapitelEngelska2015
Förlag, utgivningsår, omfång ...
- Society for Industrial and Applied Mathematics,2015
- printrdacarrier
Nummerbeteckningar
- LIBRIS-ID:oai:DiVA.org:kth-181506
- https://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-181506URI
- https://doi.org/10.1137/130929394DOI
Kompletterande språkuppgifter
- Språk:engelska
- Sammanfattning på:engelska
Ingår i deldatabas
- SwePubSwePub
Klassifikation
Anmärkningar
- QC 20160203
- 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.
Ämnesord och genrebeteckningar
- NATURVETENSKAP Matematik Diskret matematik hsv//swe
- NATURAL SCIENCES Mathematics Discrete Mathematics hsv//eng
- 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
Biuppslag (personer, institutioner, konferenser, titlar ...)
- Gopalan, P. (författare)
- Håstad, JohanKTH,Teoretisk datalogi, TCS(Swepub:kth)u1demvyb (författare)
- Meka, R. (författare)
- Raghavendra, P. (författare)
- Steurer, D. (författare)
- KTHTeoretisk datalogi, TCS (creator_code:org_t)
Sammanhörande titlar
- Ingår i:SIAM journal on computing (Print): Society for Industrial and Applied Mathematics44:5, s. 1287-13240097-53971095-7111
Internetlänk
Hitta via bibliotek
- SIAM journal on computing (Print) (Sök värdpublikationen i LIBRIS)
Till lärosätets databas
- 1 av 1
- Föregående post
- Nästa post
- Till träfflistan
Hitta mer i SwePub
- Av författaren/redakt...
- Barak, B.
- Gopalan, P.
- Håstad, Johan
- Meka, R.
- Raghavendra, P.
- Steurer, D.
- Om ämnet
-
- NATURVETENSKAP
- NATURVETENSKAP
- och Matematik
- och Diskret matemati ...
- Artiklar i publikationen
- SIAM journal on ...
- Av lärosätet
- Kungliga Tekniska Högskolan
Sök utanför SwePub
- Sök vidare i:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - Nationella bibliotekssystem
- LIBRIS.kb.se
