Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
- 1 January 2007
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 37 (1), 267-302
- https://doi.org/10.1137/s0097539705447360
Abstract
No abstract availableThis publication has 14 references indexed in Scilit:
- Hardness of approximating the shortest vector problem in latticesJournal of the ACM, 2005
- Lattice problems in NP ∩ coNPJournal of the ACM, 2005
- The complexity of the covering radius problemcomputational complexity, 2005
- A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factorDiscrete Applied Mathematics, 2003
- On the Limits of Nonapproximability of Lattice ProblemsJournal of Computer and System Sciences, 2000
- Approximating shortest lattice vectors is not harder than approximating closest lattice vectorsInformation Processing Letters, 1999
- New bounds in some transference theorems in the geometry of numbersMathematische Annalen, 1993
- On Lovász’ lattice reduction and the nearest lattice point problemCombinatorica, 1986
- Factoring polynomials with rational coefficientsMathematische Annalen, 1982
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963