Recently, Ajtai discovered a fascinating connection
between the worst-case complexity and the average-case
complexity of some well-known lattice problems.
Later, Ajtai and Dwork proposed a cryptosystem inspired
by Ajtai's work, provably secure if a particular lattice
problem is difficult. We show that there is a converse
to the ...
more >>>
We give a method for approximating any n-dimensional
lattice with a lattice \Lambda whose factor group
\mathbb{Z}^n / \Lambda has n-1 cycles of equal length
with arbitrary precision. We also show that a direct
consequence of this is that the Shortest Vector Problem and the Closest
Vector Problem cannot ...
more >>>
We show that the Closest Vector
Problem with Preprocessing over infty Norm
is NP-hard to approximate to within a factor of (\log n)^{1/2-\epsilon}. The result is the same as Regev and Rosen' result, but our proof methods are different from theirs. Their
reductions are based on norm embeddings. However, ...
more >>>
We prove that for an arbitrarily small constant \eps>0, assuming NP\not \subseteqDTIME(2^{{\log^{O(1/\epsilon)} n}}), the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than 2^{\log ^{1-\epsilon}n}. This improves upon the previous hardness factor of (\log n)^\delta for some $\delta ... more >>>
Quantum computers are expected to revolutionize our ability to process information. The advancement from classical to quantum computing is a product of our advancement from classical to quantum physics -- the more our understanding of the universe grows, so does our ability to use it for computation. A natural question ... more >>>