Determinism versus nondeterminism for linear time RAMs with memory restrictions
- Miklós Ajtai
- 2002
- Journal of Computer and System Sciences
Publications
46 results for Miklós Ajtai
Sampling short lattice vectors and the closest lattice vector problem
- Miklós Ajtai
- Ravi Kumar
- et al.
- 2002
- CCC 2002
Approximate counting of inversions in a data stream
- Miklós Ajtai
- T.S. Jayram
- et al.
- 2002
- STOC 2002
The invasiveness of off-line memory checking
- Miklós Ajtai
- 2002
- STOC 2002
Compactly encoding unstructured inputs with differential compression
- Miklos Ajtai
- Randal Burns
- et al.
- 2002
- Journal of the ACM
A sieve algorithm for the shortest lattice vector problem
- Miklos Ajtai
- R. Kumar
- et al.
- 2001
- STOC 2001
Closure of monadic NP
- Miklos Ajtai
- Ronald Fagin
- et al.
- 2000
- Journal of Computer and System Sciences
Improved algorithms and analysis for secretary problems and generalizations
- Miklos Ajtai
- Nimrod Megiddo
- et al.
- 2000
- SIAM Journal on Discrete Mathematics
Non-linear time lower bound for Boolean branching programs
- Miklos Ajtai
- 1999
- FOCS 1999
Determinism versus non-determinism for linear time RAMs
- Miklos Ajtai
- 1999
- STOC 1999