Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR99-006 | 10th March 1999 00:00

Some Recent Progress on the Complexity of Lattice Problems

RSS-Feed




TR99-006
Authors: Jin-Yi Cai
Publication: 11th March 1999 09:25
Downloads: 1970
Keywords: 


Abstract:

We survey some recent developments in the study of
the complexity of lattice problems. After a discussion of some
problems on lattices which can be algorithmically solved
efficiently, our main focus is the recent progress on complexity
results of intractability. We will discuss Ajtai's worst-case/
average-case connections, NP-hardness and non-NP-hardness,
transference theorems between primal and dual lattices, and the
Ajtai-Dwork cryptosystem.

(This is a survey article appearing in the Conference on
Computational Complexity at FCRC, May 1999.)



ISSN 1433-8092 | Imprint