Making the Long Code Shorter

DOI10.1137/130929394MaRDI QIDQ3449561zbMATH OpenOpenAlexWikidataFDO

Authors Boaz Barak, Parikshit Gopalan, Raghu Meka, Prasad Raghavendra, David Steurer, Johan Hastad

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Other types of codes (94B60)

Recommendations

• Shortening of codes
• General code shortening construction
• Shortened Regenerating Codes
• Reducing coding redundancy in LZW
• Simple, Effective Code-Size Reduction for Functional Programs
• Coding and Code Compression
• Coding Ockham's Razor
• Code optimization in FORM
• Compiler Construction

Cites work

• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Approximating unique games
• Bounded Independence Fools Halfspaces
• Convex relaxations and integrality gaps
• scientific article; zbMATH DE number 5485570 (Why is no real title available?)
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• Hypercontractivity, sum-of-squares proofs, and their applications
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• Near-optimal algorithms for unique games
• Noise stability of functions with low influences: invariance and optimality
• On the power of unique 2-prover 1-round games
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Optimal testing of Reed-Muller codes
• Rounding Semidefinite Programming Hierarchies via Global Correlation
• SDP Integrality Gaps with Local ell₁-Embeddability
• Spectral algorithms for unique games
• Subexponential algorithms for unique games and related problems
• Testing Reed–Muller Codes
• The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number

Cited in

(16)

• High order random walks: beyond spectral gap
• Derandomized graph product results using the low degree long code
• Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Boolean function analysis on high-dimensional expanders
• High order random walks: beyond spectral gap
• Small-set expansion in shortcode graph and the 2-to-2 conjecture
• Candidate hard unique game
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
• A characterization of hard-to-cover CSPs
• Pseudorandom sets in Grassmann graph have near-perfect expansion
• Boolean function analysis on high-dimensional expanders
• Small-set expansion in the Johnson graph
• Improved optimal testing results from global hypercontractivity
• Complexity measures on the symmetric group and beyond (extended abstract)
• PCPs via the low-degree long code and hardness for constrained hypergraph coloring

This page was built for publication: Making the Long Code Shorter

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449561)