{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T07:49:05Z","timestamp":1761292145324,"version":"3.28.0"},"reference-count":34,"publisher":"IEEE Computer. Soc","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/sfcs.2003.1238203","type":"proceedings-article","created":{"date-parts":[[2004,3,1]],"date-time":"2004-03-01T21:26:50Z","timestamp":1078176410000},"page":"290-297","source":"Crossref","is-referenced-by-count":7,"title":["Hardness of approximating the shortest vector problem in high L\/sub p\/ norms"],"prefix":"10.1109","author":[{"given":"S.","family":"Khot","sequence":"first","affiliation":[]}],"member":"263","reference":[{"key":"19","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.415"},{"key":"17","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258536"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808749"},{"key":"33","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90064-8"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276704"},{"article-title":"Another NP-complete problem and the complexity of computing short vectors in a lattice","year":"1981","author":"van emde boas","key":"34"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892074"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743433"},{"article-title":"Disquisitiones arithmeticae","year":"1966","author":"gauss","key":"14"},{"key":"11","article-title":"An improved worst-case to average-case connection for lattice problems","author":"cai","year":"0","journal-title":"38th IEEE Symposium on Foundations of Computer Science 1997"},{"key":"12","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-46521-9_22","article-title":"Approximating SVPM? to within almost polynomial factors is NP-hard","volume":"1767","author":"dinur","year":"2000","journal-title":"Proc of the 4th Italian Conference on Algorithms and Complexity LNCS"},{"key":"21","doi-asserted-by":"publisher","DOI":"10.1007\/BF02128669"},{"key":"20","first-page":"40","article-title":"Complexity of SVP - a reader's digest","volume":"32","author":"kumar","year":"2001","journal-title":"Sigact News"},{"key":"22","doi-asserted-by":"publisher","DOI":"10.1145\/2455.2461"},{"key":"23","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90013-3"},{"key":"24","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457454"},{"key":"26","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"27","article-title":"The shortest vector problem is NP-hard to approximate to within some constant","author":"micciancio","year":"0","journal-title":"Proc of the 39th IEEE Symposium on Foundations of Computer Science 1998"},{"year":"1998","author":"micciancio","key":"28"},{"article-title":"Complexity of lattice problems, A cryptographic perspective","year":"2002","author":"micciancio","key":"29"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258604"},{"key":"2","first-page":"99","article-title":"Generating hard instances of lattice problems","author":"ajtai","year":"0","journal-title":"Proc of the 28th Annual ACM Symposium on the Theory of Computing 1996"},{"key":"10","first-page":"151","article-title":"Approximating the SVP to within a factor (1 + 1\/dim?) is NP-hard under randomized reductions","author":"cai","year":"0","journal-title":"Proc of the 13th Annual IEEE Conference on Computational Complexity 1998"},{"key":"1","first-page":"10","article-title":"The shortest vector problem in L2 is NP-hard for randomized reductions","author":"ajtai","year":"0","journal-title":"Proc of the 30th Annual ACM Symposium on the Theory of Computing 1998"},{"article-title":"Geometrie der zahlen","year":"1910","author":"minkowski","key":"30"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"32","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780603"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"31","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380857"},{"key":"9","article-title":"Applications of a new transference theorem to Ajtai's connection factor","author":"cai","year":"0","journal-title":"Proc of the 14th Annual IEEE Conference on Computational Complexity 1999"},{"key":"8","article-title":"Efficient probabilistically checkable poofs and applications to approximation","author":"bellare","year":"0","journal-title":"Proc of the 25th Annual ACM Symposium on Theory of Computing 1993"}],"event":{"name":"44th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2003","acronym":"SFCS-03","location":"Cambridge, MA, USA"},"container-title":["44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings."],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/8767\/27770\/01238203.pdf?arnumber=1238203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,16]],"date-time":"2017-06-16T00:05:25Z","timestamp":1497571525000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1238203\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":34,"URL":"https:\/\/doi.org\/10.1109\/sfcs.2003.1238203","relation":{},"subject":[]}}