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