Lattice problems in NP∧coNP

被引:24
作者
Aharonov, D [1 ]
Regev, O [1 ]
机构
[1] Hebrew Univ Jerusalem, Sch Comp Sci & Engn, Jerusalem, Israel
来源
45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2004年
关键词
D O I
10.1109/FOCS.2004.35
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We show that the problems of approximating the shortest and closest vector in a lattice to within a factor of rootn lie in NP intersect coNP. The result (almost) subsumes the three mutually-incomparable previous results regarding these lattice problems: Banaszczyk [7], Goldreich and Goldwasser [13], and Aharonov and Regev [2]. Our technique is based on a simple fact regarding succinct approximation of functions using their Fourier transform over the lattice. This technique might be useful elsewhere - we demonstrate this by giving a simple and efficient algorithm for one other lattice problem (CVPP) improving on a previous result Of Regev [25]. An interesting fact is that our result emerged from a "dequantization" of our previous quantum result in [2]. This route to proving purely classical results might be beneficial elsewhere.
引用
收藏
页码:362 / 371
页数:10
相关论文
共 29 条
  • [1] AARONSON S, 2004, P 36 ANN ACM S THEOR, P465
  • [2] A lattice problem in quantum NP
    Aharonov, D
    Regev, O
    [J]. 44TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2003, : 210 - 219
  • [3] Ajtai M., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P99, DOI 10.1145/237814.237838
  • [4] Ajtai M., 1998, STOC, P10
  • [5] Ajtai M., 1997, PROC 29 S THEORY COM, P284, DOI DOI 10.1145/258533.258604
  • [6] NEW BOUNDS IN SOME TRANSFERENCE THEOREMS IN THE GEOMETRY OF NUMBERS
    BANASZCZYK, W
    [J]. MATHEMATISCHE ANNALEN, 1993, 296 (04) : 625 - 635
  • [7] BOAS PV, 1981, 8104 U AMST DEP MATH
  • [8] A note on the non-NP-hardness of approximate lattice problems under general Cook reductions
    Cai, JY
    Nerurkar, A
    [J]. INFORMATION PROCESSING LETTERS, 2000, 76 (1-2) : 61 - 66
  • [9] Approximating CVP to within almost-polynomial factors is NP-hard
    Dinur, I
    Kindler, G
    Raz, R
    Safra, S
    [J]. COMBINATORICA, 2003, 23 (02) : 205 - 243
  • [10] The inapproximability of lattice and coding problems with preprocessing
    Feige, U
    Micciancio, D
    [J]. 17TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2002, : 44 - 52