Making the long code shorter

↓ Direkt till sidans innehåll
↓ Direkt till sidans sekundära innehåll (sidomenyn)

Search: WFRF:(Gopalan D) > Making the long cod...

Details
MARC

Barak, B. (author)

Making the long code shorter

Article/chapterEnglish2015

Publisher, publication year, extent ...

Society for Industrial and Applied Mathematics,2015
printrdacarrier

Numbers

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

Supplementary language notes

Language:English
Summary in:English

Part of subdatabase

SwePubSwePub

Classification

Subject category:ref swepub-contenttype
Subject category:art swepub-publicationtype

Notes

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.

Subject headings and genre

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

Added entries (persons, corporate bodies, meetings, titles ...)

Gopalan, P. (author)
Håstad, JohanKTH,Teoretisk datalogi, TCS(Swepub:kth)u1demvyb (author)
Meka, R. (author)
Raghavendra, P. (author)
Steurer, D. (author)
KTHTeoretisk datalogi, TCS (creator_code:org_t)

Related titles

In:SIAM journal on computing (Print): Society for Industrial and Applied Mathematics44:5, s. 1287-13240097-53971095-7111

Internet link

Find in a library

SIAM journal on computing (Print) (Search for host publication in LIBRIS)

To the university's database

Find more in SwePub

By the author/editor: Barak, B.; Gopalan, P.; Håstad, Johan; Meka, R.; Raghavendra, P.; Steurer, D.

About the subject

NATURAL SCIENCES: NATURAL SCIENCES; and Mathematics; and Discrete Mathema ...

Articles in the publication: SIAM journal on ...

By the university: Royal Institute of Technology

Search outside SwePub

Extend your search to:: Google; 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.

LIBRIS.kb.se