Concepedia

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

Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk

Journal of Computer and System Sciences · 1997 · 343 citations · 25 references

DOI

Concepts

References

25

Factoring polynomials with rational coefficients

A. K. Lenstra, H. W. Lenstra, László Lovász · Mathematische Annalen · 1982 · 4K citations · Full text

, , +4

Approximation Algorithms for NP-Hard Problems

Dorit S. Hochba · ACM SIGACT News · 1997 · 3.1K citations · Full text

, , +13

Optimization, approximation, and complexity classes

Christos H. Papadimitriou, Mihalis Yannakakis · Journal of Computer and System Sciences · 1991 · 1.7K citations

, , +12

On the inherent intractability of certain coding problems (Corresp.)

Elwyn R. Berlekamp, Robert J. McEliece, H. van Tilborg · IEEE Transactions on Information Theory · 1978 · 1.5K citations · Full text

, , +13

On Lovász’ lattice reduction and the nearest lattice point problem

László Babai · COMBINATORICA · 1986 · 930 citations

, , +10