PCPs via the low-degree long code and hardness for constrained hypergraph coloring
type: Item
instance of: scholarly article
title: PCPs via the low-degree long code and hardness for constrained hypergraph coloring
zbMATH Open document ID: 1330.68091
author: Irit Dinur
author: Venkatesan Guruswami
published in: Israel Journal of Mathematics
publication date: 2015-11-16T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 94B05
zbMATH DE Number: 6509379
MaRDI profile type: Publication
full work available at URL: s11856-015-1231-3
OpenAlex ID: W2256256972
cites work: Q3002852
cites work: Making the Long Code Shorter
cites work: Free Bits, PCPs, and Nonapproximability---Towards Tight Results
cites work: Corrigendum to: ``Efficient probabilistic checkable proofs and applications to approximation''
cites work: Optimal Testing of Reed-Muller Codes
cites work: The complexity of equality constraint languages
cites work: PCP characterizations of NP: toward a polynomially-small error-probability
cites work: Some optimal inapproximability results
cites work: The hardness of 3-uniform hypergraph coloring
cites work: Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes
cites work: Hardness of Approximate Hypergraph Coloring
cites work: On the NP-Hardness of Max-Not-2
cites work: A PRG for lipschitz functions of polynomials with applications to sparsest cut
cites work: Hardness results for approximate hypergraph coloring
cites work: Noise stability of functions with low influences: invariance and optimality
cites work: On the power of unique 2-prover 1-round games
cites work: Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
cites work: Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors
cites work: Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs
cites work: The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
DOI: 10.1007/S11856-015-1231-3
description: scientific article; zbMATH DE number 6509379