| 2022 | PODS | The White-Box Adversarial Data Stream Model. | Mikls Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou |
| 2013 | STOC | Lower bounds for RAMs and quantifier elimination. | Mikls Ajtai |
| 2012 | STOC | Determinism versus nondeterminism with arithmetic tests and computation: extended abstract. | Mikls Ajtai |
| 2011 | STOC | Secure computation with information leaking to an adversary. | Mikls Ajtai |
| 2010 | STOC | Oblivious RAMs without cryptogrpahic assumptions. | Mikls Ajtai |
| 2009 | ICALP | Sorting and Selection with Imprecise Comparisons. | Mikls Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson |
| 2007 | TAMC | Generalizations of the Compactness Theorem and Gdel's Completeness Theorem for Nonstandard Finite Structures. | Mikls Ajtai |
| 2006 | LATIN | An Architecture for Provably Secure Computation. | Mikls Ajtai, Cynthia Dwork, Larry J. Stockmeyer |
| 2005 | STOC | Representing hard lattices with O(n log n) bits. | Mikls Ajtai |
| 2004 | STOC | A conjecture about polynomial time computable lattice-lattice functions. | Mikls Ajtai |
| 2003 | STOC | The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice. | Mikls Ajtai |
| 2002 | FOCS | Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties. | Mikls Ajtai |
| 2002 | STOC | The invasiveness of off-line memory checking. | Mikls Ajtai |
| 2002 | STOC | Approximate counting of inversions in a data stream. | Mikls Ajtai, T. S. Jayram, Ravi Kumar, D. Sivakumar |
| 2001 | STOC | A sieve algorithm for the shortest lattice vector problem. | Mikls Ajtai, Ravi Kumar, D. Sivakumar |
| 1999 | FOCS | A Non-linear Time Lower Bound for Boolean Branching Programs. | Mikls Ajtai |
| 1999 | ICALP | Generating Hard Instances of the Short Basis Problem. | Mikls Ajtai |
| 1999 | STOC | Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract). | Mikls Ajtai |
| 1998 | STOC | The Shortest Vector Problem in | Mikls Ajtai |
| 1998 | STOC | The Closure of Monadic NP (Extended Abstract). | Mikls Ajtai, Ronald Fagin, Larry J. Stockmeyer |
| 1997 | STOC | A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. | Mikls Ajtai, Cynthia Dwork |
| 1996 | STOC | Generating Hard Instances of Lattice Problems (Extended Abstract). | Mikls Ajtai |
| 1995 | FOCS | Improved Algorithms and Analysis for Secretary Problems and Generalizations. | Mikls Ajtai, Nimrod Megiddo, Orli Waarts |
| 1995 | SODA | Fairness in Scheduling. | Mikls Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts |
| 1994 | FOCS | A Theory of Competitive Analysis for Distributed Algorithms | Mikls Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts |
| 1994 | PODC | Competitiveness in Distributed Algorithms. | Mikls Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts |
| 1994 | STOC | The independence of the modulo | Mikls Ajtai |
| 1992 | FOCS | Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths | Mikls Ajtai, Noga Alon, Jehoshua Bruck, Robert Cypher, Ching-Tien Ho, Moni Naor, Endre Szemerdi |
| 1992 | FOCS | Halvers and Expanders | Mikls Ajtai, Jnos Komls, Endre Szemerdi |
| 1992 | STOC | A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension | Mikls Ajtai, Nimrod Megiddo |
| 1989 | FOCS | Datalog vs. First-Order Logic | Mikls Ajtai, Yuri Gurevich |
| 1988 | FOCS | The Complexity of the Pigeonhole Principle | Mikls Ajtai |
| 1988 | FOCS | Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version) | Mikls Ajtai, Ronald Fagin |
| 1987 | FOCS | Recursive Construction for 3-Regular Expanders | Mikls Ajtai |
| 1987 | STOC | Deterministic Simulation in LOGSPACE | Mikls Ajtai, Jnos Komls, Endre Szemerdi |
| 1986 | STOC | Two lower bounds for branching programs | Mikls Ajtai, Lszl Babai, Pter Hajnal, Jnos Komls, Pavel Pudlk, Vojtech Rdl, Endre Szemerdi, Gyrgy Turn |
| 1986 | STOC | Deterministic Selection in O(log log N) Parallel Time | Mikls Ajtai, Jnos Komls, William L. Steiger, Endre Szemerdi |
| 1985 | FOCS | Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version) | Mikls Ajtai, Avi Wigderson |
| 1984 | STOC | A Theorem on Probabilistic Constant Depth Computations | Mikls Ajtai, Michael Ben-Or |
| 1983 | FOCS | Hash Functions for Priority Queues | Mikls Ajtai, Michael L. Fredman, Jnos Komls |
| 1983 | STOC | An O(n log n) Sorting Network | Mikls Ajtai, Jnos Komls, Endre Szemerdi |