A 3-query PCP over integers

MaRDI QIDQ3549614zbMATH OpenFDO

Authors Prasad Raghavendra, Venkatesan Guruswami

Publication date 5 January 2009

zbMATH Keywords

equations over the integersequations over the realsfinite fieldhardnesslinear equationsoverdetermined system

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Symbolic computation and algebraic computation (68W30)

Recommendations

• Hardness of solving sparse overdetermined linear systems: a 3-query PCP over integers
• NP-hardness of approximately solving linear equations over reals
• More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
• STACS 2005
• Hardness of MAX-2Lin and MAX-3Lin over integers, reals, and large cyclic groups

Cited in

(4)

• Pricing on paths: a PTAS for the highway problem
• Hardness of solving sparse overdetermined linear systems: a 3-query PCP over integers
• Three‐query PCPs with perfect completeness over non‐Boolean domains
• Approximating maximum satisfiable subsystems of linear equations of bounded width

This page was built for publication: A 3-query PCP over integers

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