A well-characterized approximation problem
From MaRDI portal
Publication:688442
DOI10.1016/0020-0190(93)90076-LzbMATH Open0782.68057OpenAlexW2117913620WikidataQ56959141 ScholiaQ56959141MaRDI QIDQ688442FDOQ688442
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
Recommendations
Cites Work
- Title not available (Why is that?)
- Simple Constructions of Almost k-wise Independent Random Variables
- Title not available (Why is that?)
- On the hardness of approximating minimization problems
- Efficient probabilistically checkable proofs and applications to approximations
- The complexity of approximating a nonlinear program
- Title not available (Why is that?)
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
- Nonlinear Algebra and Optimization on Rings are “Hard”
- Satisfying degree-\(d\) equations over \(\mathrm{GF}[2]^{n}\)
- 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
- Title not available (Why is that?)
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)
