More on average case vs approximation complexity
Top Cited Papers
- 3 February 2004
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
No abstract availableThis publication has 21 references indexed in Scilit:
- Spectral Methods for Matrix Rigidity with Applications to Size–Depth Trade-offs and Communication ComplexityJournal of Computer and System Sciences, 2001
- Some optimal inapproximability resultsJournal of the ACM, 2001
- On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processesDiscrete Applied Mathematics, 2001
- Improved lower bounds on the rigidity of Hadamard matricesMathematical Notes, 1998
- On the limits of non-approximability of lattice problemsPublished by Association for Computing Machinery (ACM) ,1998
- A remark on matrix rigidityInformation Processing Letters, 1997
- Natural ProofsJournal of Computer and System Sciences, 1997
- Small-Bias Probability Spaces: Efficient Constructions and ApplicationsSIAM Journal on Computing, 1993
- Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal latticeCombinatorica, 1990
- Dual vectors and lower bounds for the nearest lattice point problemCombinatorica, 1988