scientific article; zbMATH DE number 7650076

DOI10.4230/LIPICS.APPROX-RANDOM.2019.9MaRDI QIDQ5875460zbMATH OpenFDO

Authors Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.9

zbMATH Keywords

3LINcompositionlow soundness errorPCPprobabilistically checkable proofs

Mathematics Subject Classification ID

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

Recommendations

• On the hardness of approximating label-cover
• On the hardness of approximating balanced homogenous 3-Lin
• Improved Approximation Algorithms for Label Cover Problems
• Improved approximation algorithms for label cover problems
• New NP-hardness results for 3-coloring and 2-to-1 label cover
• Improved worst-case complexity for the MIN 3-SET COVERING problem
• Linear kernelizations for restricted 3-Hitting Set problems
• A New Point of NP-Hardness for 2-to-1 Label Cover
• Hardness results for structured linear systems
• New upper bounds on the linear complexity

Cites work

• A Parallel Repetition Theorem
• A sample of samplers: a computational perspective on sampling
• Analytical approach to parallel repetition
• Composition of low-error 2-query PCPs using decodable PCPs
• scientific article; zbMATH DE number 6474898 (Why is no real title available?)
• Inapproximability Results for Computational Problems on Lattices
• Linear Equations Modulo 2 and the L₁ Diameter of Convex Bodies
• On the advantage over a random assignment
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Some optimal inapproximability results
• Two-query PCP with subconstant error

This page was built for publication:

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