Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with lattice:
TR96-065 | 13th December 1996
Miklos Ajtai, Cynthia Dwork

A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence

Revisions: 1 , Comments: 1

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 >>>

TR98-016 | 24th March 1998
Daniele Micciancio

The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant.

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.

more >>>

TR98-048 | 6th July 1998
Irit Dinur, Guy Kindler, Shmuel Safra

Approximating CVP to Within Almost Polynomial Factor is NP-Hard

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}$.

more >>>

TR00-074 | 12th July 2000
Daniele Micciancio, Bogdan Warinschi

A Linear Space Algorithm for Computing the Hermite Normal Form

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 >>>

TR02-061 | 14th November 2002
Miklos Ajtai

A conjectured 0-1 law about the polynomial time computable properties of random lattices, I.

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 >>>

TR07-097 | 8th October 2007
Miklos Ajtai, Cynthia Dwork

The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.

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 >>>

TR17-070 | 15th April 2017
Shachar Lovett, Sankeerth Rao Karingula, Alex Vardy

Probabilistic Existence of Large Sets of Designs

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 >>>

TR21-179 | 8th December 2021
tatsuie tsukiji

Smoothed Complexity of Learning Disjunctive Normal Forms, Inverting Fourier Transforms, and Verifying Small Circuits

Comments: 1

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 >>>

ISSN 1433-8092 | Imprint