Miklos Ajtai

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

Miklos Ajtai

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

Miklos Ajtai

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