Miklos Ajtai, Cynthia Dwork

We present a probabilistic public key cryptosystem which is

secure unless the following worst-case lattice problem can be solved in

polynomial time:

"Find the shortest nonzero vector in an n dimensional lattice

L where the shortest vector v is unique in the sense that any other

vector whose ...
more >>>

Daniele Micciancio

We show that computing the approximate length of the shortest vector

in a lattice within a factor c is NP-hard for randomized reductions

for any constant c<sqrt(2). We also give a deterministic reduction

based on a number theoretic conjecture.

Irit Dinur, Guy Kindler, Shmuel Safra

This paper shows finding the closest vector in a lattice

to be NP-hard to approximate to within any factor up to

$2^{(\log{n})^{1-\epsilon}}$ where

$\epsilon = (\log\log{n})^{-\alpha}$

and $\alpha$ is any positive constant $<{1\over 2}$.

Daniele Micciancio, Bogdan Warinschi

Computing the Hermite Normal Form

of an $n\times n$ matrix using the best current algorithms typically

requires $O(n^3\log M)$ space, where $M$ is a bound on the length of

the columns of the input matrix.

Although polynomial in the input size (which ...
more >>>

Miklos Ajtai

A measure $\mu_{n}$ on $n$-dimensional lattices with

determinant $1$ was introduced about fifty years ago to prove the

existence of lattices which contain points from certain sets. $\mu_{n}$

is the unique probability measure on lattices with determinant $1$ which

is invariant under linear transformations with determinant $1$, where a

more >>>

Miklos Ajtai, Cynthia Dwork

We describe a public-key cryptosystem with worst-case/average case

equivalence. The cryptosystem has an amortized plaintext to

ciphertext expansion of $O(n)$, relies on the hardness of the

$\tilde O(n^2)$-unique shortest vector problem for lattices, and

requires a public key of size at most $O(n^4)$ bits. The new

cryptosystem generalizes a conceptually ...
more >>>

Shachar Lovett, Sankeerth Rao Karingula, Alex Vardy

A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been introduced by Kuperberg, Lovett, and Peled (STOC 2012). Using this technique, it can be shown that under certain conditions, a randomly chosen structure has the required properties of a $t-(n,k,?)$ combinatorial design with tiny, yet ... more >>>

tatsuie tsukiji

This paper aims to derandomize the following problems in the smoothed analysis of Spielman and Teng. Learn Disjunctive Normal Form (DNF), invert Fourier Transforms (FT), and verify small circuits' unsatisfiability. Learning algorithms must predict a future observation from the only $m$ i.i.d. samples of a fixed but unknown joint-distribution $P(G(x),y)$ ... more >>>