Closure of monadic NP
- Miklos Ajtai
- Ronald Fagin
- et al.
- 1998
- STOC 1998
Publications
46 results for Miklós Ajtai
Shortest vector problem in L2 is NP-hard for randomized reductions
- Miklos Ajtai
- 1998
- STOC 1998
Fairness in Scheduling
- Miklos Ajtai
- James Aspnes
- et al.
- 1998
- Journal of Algorithms
Public-key cryptosystem with worst-case/average-case equivalence
- Miklos Ajtai
- Cynthia Dwork
- 1997
- STOC 1997
Generating hard instances of lattice problems
- Miklos Ajtai
- 1996
- STOC 1996
A deterministic poly(loglog n)-time n-processor algorithm for linear programming in fixed dimension
- Miklos Ajtai
- Nimrod Megiddo
- 1996
- SIAM Journal on Computing
Improved algorithms and analysis for secretary problems and generalizations
- Miklos Ajtai
- Nimrod Megiddo
- et al.
- 1995
- FOCS 1995
Fairness in scheduling
- Miklos Ajtai
- James Aspnes
- et al.
- 1995
- SODA 1995
Recursive construction for 3-regular expanders
- Miklos Ajtai
- 1994
- Combinatorica
The complexity of the Pigeonhole Principle
- Miklos Ajtai
- 1994
- Combinatorica