The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations

This publication has 23 references indexed in Scilit:

• The complexity and approximability of finding maximum feasible subsystems of linear relations
  Theoretical Computer Science, 1995
• Efficient probabilistic checkable proofs and applications to approximation
  Published by Association for Computing Machinery (ACM) ,1994
• Proof verification and hardness of approximation problems
  Published by Institute of Electrical and Electronics Engineers (IEEE) ,1992
• Probabilistic checking of proofs; a new characterization of NP
  Published by Institute of Electrical and Electronics Engineers (IEEE) ,1992
• Non-deterministic exponential time has two-prover interactive protocols
  computational complexity, 1991
• Checking computations in polylogarithmic time
  Published by Association for Computing Machinery (ACM) ,1991
• Designing programs that check their work
  Published by Association for Computing Machinery (ACM) ,1989
• Multi-prover interactive proofs: how to remove intractability
  Published by Association for Computing Machinery (ACM) ,1988
• On Lovász’ lattice reduction and the nearest lattice point problem
  Combinatorica, 1986
• On the inherent intractability of certain coding problems (Corresp.)
  IEEE Transactions on Information Theory, 1978