A well-characterized approximation problem

DOI10.1016/0020-0190(93)90076-LMaRDI QIDQ688442zbMATH OpenOpenAlexWikidataFDO

Authors Shmuel Safra, Johan Hastad, Steven J. Phillips

Publication date 13 March 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90076-l

zbMATH Keywords

approximation algorithmNP-hard

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Satisfying degree-\(d\) equations over \(\mathrm{GF}[2]^{n}\)
• The complexity of approximating a nonlinear program
• NP-hardness of approximately solving linear equations over reals
• On the hardness of approximating max-satisfy
• Satisfying degree-\(d\) equations over \(\mathrm{GF}[2]^n\)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256635 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• Efficient probabilistically checkable proofs and applications to approximations
• On the hardness of approximating minimization problems
• Simple Constructions of Almost k-wise Independent Random Variables
• The complexity of approximating a nonlinear program

Cited in

(11)

• Approximate solutions of polynomial equations.
• \(\mathrm{MOD}_p\)-tests, almost independence and small probability spaces (extended abstract)
• Phase transition of multivariate polynomial systems
• Polly cracker, revisited
• Satisfying degree-\(d\) equations over \(\mathrm{GF}[2]^{n}\)
• Nonlinear Algebra and Optimization on Rings are “Hard”
• Minimal achievable approximation ratio for MAX-MQ in finite fields
• Satisfying degree-\(d\) equations over \(\mathrm{GF}[2]^n\)
• PCP characterizations of NP: toward a polynomially-small error-probability
• The complexity and approximability of finding maximum feasible subsystems of linear relations
• scientific article; zbMATH DE number 4054234 (Why is no real title available?)

This page was built for publication: A well-characterized approximation problem

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