Venkatesan Guruswami

We define number-theoretic error-correcting codes based on algebraic

number fields, thereby providing a generalization of Chinese Remainder

Codes akin to the generalization of Reed-Solomon codes to

Algebraic-geometric codes. Our construction is very similar to

(and in fact less general than) the one given by (Lenstra 1986), but

the ...
more >>>

Chris Peikert, Alon Rosen

We demonstrate an \emph{average-case} problem which is as hard as

finding $\gamma(n)$-approximate shortest vectors in certain

$n$-dimensional lattices in the \emph{worst case}, where $\gamma(n)

= O(\sqrt{\log n})$. The previously best known factor for any class

of lattices was $\gamma(n) = \tilde{O}(n)$.

To obtain our ... more >>>