DocumentCode
3330758
Title
An improved worst-case to average-case connection for lattice problems
Author
Cai, Jin-Yi ; Nerurkar, Ajay P.
Author_Institution
Dept. of Comput. Sci., State Univ. of New York, Buffalo, NY, USA
fYear
1997
fDate
20-22 Oct 1997
Firstpage
468
Lastpage
477
Abstract
We improve a connection of the worst-case complexity and the average-case complexity of some well-known lattice problems. This fascinating connection was first discovered by Ajtai (1995). We improve the exponent of this connection from 8 to 3.5+ε
Keywords
computational complexity; group theory; average-case complexity; discrete additive subgroup; lattice problems; worst-case complexity; Bridges; Computer science; Cryptographic protocols; Cryptography; Gaussian processes; Geometry; Lattices; Microwave integrated circuits; Polynomials; Security;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on
Conference_Location
Miami Beach, FL
ISSN
0272-5428
Print_ISBN
0-8186-8197-7
Type
conf
DOI
10.1109/SFCS.1997.646135
Filename
646135
Link To Document