Revisiting alphabet reduction in Dinur’s PCP.

DOI10.4230/lipics.approx/random.2020.34OpenAlexW3081690414MaRDI QIDQ6062158

Jakub Opršal, Venkatesan Guruswami, Sai Sandeep

Publication date: 31 October 2023

Full work available at URL: http://dro.dur.ac.uk/31716/

zbMATH Keywords

PCP theoremCSPdiscrete Fourier analysislabel coverlong code

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Boolean functions whose Fourier transform is concentrated on the first two levels.
• Proof verification and the hardness of approximation problems
• On Dinur’s proof of the PCP theorem
• Probabilistic checking of proofs
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Algebraic approach to promise constraint satisfaction
• $(2+\varepsilon)$-Sat Is NP-hard
• Some optimal inapproximability results
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• The PCP theorem by gap amplification

This page was built for publication: Revisiting alphabet reduction in Dinur’s PCP.