Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Miklos Ajtai:

TR13-083 | 7th June 2013
Miklos Ajtai

Lower Bounds for RAMs and Quantifier Elimination

For each natural number $d$ we consider a finite structure ${\bf M}_{d}$ whose universe is the set of all $0,1$-sequence of length $n=2^{d}$, each representing a natural number in the set $\lbrace 0,1,...,2^{n}-1\rbrace$ in binary form. The operations included in the structure are the four constants $0,1,2^{n}-1,n$, multiplication and addition ... more >>>

TR11-102 | 31st July 2011
Miklos Ajtai

Determinism Versus Nondeterminism with Arithmetic Tests and Computation

Revisions: 1

For each natural number $d$ we consider a finite structure $M_{d}$ whose
universe is the set of all $0,1$-sequence of length $n=2^{d}$, each
representing a natural number in the set $\lbrace 0,1,...,2^{n}-1\rbrace
$ in binary form.
The operations included in the structure are the
constants $0,1,2^{n}-1,n$, multiplication and addition ... more >>>

TR11-082 | 20th May 2011
Miklos Ajtai

Secure Computation with Information Leaking to an Adversary

Assume that Alice is running a program $P$ on a RAM, and an adversary
Bob would like to get some information about the input or output of the
program. At each time, during the execution of $P$, Bob is able to see
the addresses of the memory cells involved in ... more >>>

TR10-028 | 4th March 2010
Miklos Ajtai

Oblivious RAMs without Cryptographic Assumptions

Revisions: 1

Abstract. We show that oblivious on-line simulation with only
polylogarithmic increase in the time and space requirements is possible
on a probabilistic (coin flipping) RAM without using any cryptographic
assumptions. The simulation will fail with a negligible probability.
If $n$ memory locations are used, then the probability of failure is ... 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 >>>

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

TR99-026 | 7th July 1999
Miklos Ajtai

A Non-linear Time Lower Bound for Boolean Branching Programs

We prove that for all positive integer $k$ and for all
sufficiently small $\epsilon >0$ if $n$ is sufficiently large
then there is no Boolean (or $2$-way) branching program of size
less than $2^{\epsilon n}$ which for all inputs
$X\subseteq \lbrace 0,1,...,n-1\rbrace $ computes in time $kn$
the parity of ... more >>>

TR98-077 | 19th December 1998
Miklos Ajtai

Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions

Revisions: 1

Our computational model is a random access machine with $n$
read only input registers each containing $ c \log n$ bits of
information and a read and write memory. We measure the time by the
number of accesses to the input registers. We show that for all $k$
there is ... more >>>

TR97-047 | 20th October 1997
Miklos Ajtai

The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions.

Revisions: 1

We show that the shortest vector problem in lattices
with L_2 norm is NP-hard for randomized reductions. Moreover we
also show that there is a positive absolute constant c, so that to
find a vector which is longer than the shortest non-zero vector by no
more than a factor of ... more >>>

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

TR96-007 | 29th January 1996
Miklos Ajtai

Generating Hard Instances of Lattice Problems

Comments: 1

We give a random class of n dimensional lattices so that, if
there is a probabilistic polynomial time algorithm which finds a short
vector in a random lattice with a probability of at least 1/2
then there is also a probabilistic polynomial time algorithm which
solves the following three ... more >>>

TR94-015 | 12th December 1994
Miklos Ajtai

Symmetric Systems of Linear Equations modulo $p$

Suppose that $p$ is a prime number $A$ is a finite set
with $n$ elements
and for each sequence $a=<a_{1},...,a_{k}>$ of length $k$ from the
elements of
$A$, $x_{a}$ is a variable. (We may think that $k$ and $p$ are fixed an
$n$ is sufficiently large.) We will ... more >>>

TR94-014 | 12th December 1994
Miklos Ajtai

The Independence of the modulo p Counting Principles

The modulo $p$ counting principle is a first-order axiom
schema saying that it is possible to count modulo $p$ the number of
elements of the first-order definable subsets of the universe (and of
the finite Cartesian products of the universe with itself) in a
consistent way. It trivially holds on ... more >>>

ISSN 1433-8092 | Imprint