Making the Long Code Shorter

DOI10.1137/130929394zbMath1330.68089OpenAlexW4233411607WikidataQ56958711 ScholiaQ56958711MaRDI QIDQ3449561

Prasad Raghavendra, Raghu Meka, David Steurer, Boaz Barak, Parikshit Gopalan, Johan T. Håstad

Publication date: 4 November 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/760b59f98afe5518aebb64407b5e5462a55bccc6

zbMATH Keywords

Cayley graphsexpandershardness of approximationlocally testable codes

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Other types of codes (94B60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Approximation Limits of Linear Programs (Beyond Hierarchies), PCPs via the low-degree long code and hardness for constrained hypergraph coloring, Pseudorandom sets in Grassmann graph have near-perfect expansion, Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes, Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors, Unnamed Item, Unnamed Item, A Characterization of hard-to-cover CSPs, High order random walks: beyond spectral gap, Unnamed Item, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Spectral algorithms for unique games
• Noise stability of functions with low influences: invariance and optimality
• Convex Relaxations and Integrality Gaps
• Pseudorandom Generators for Polynomial Threshold Functions
• Near-optimal algorithms for unique games
• Subexponential Algorithms for Unique Games and Related Problems
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Testing Reed–Muller Codes
• On the power of unique 2-prover 1-round games
• Approximating unique games
• Optimal Testing of Reed-Muller Codes
• SDP Integrality Gaps with Local ell_1-Embeddability
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• Bounded Independence Fools Halfspaces
• Hypercontractivity, sum-of-squares proofs, and their applications
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Rounding Semidefinite Programming Hierarchies via Global Correlation