Miklós Ajtai

	2009
73		Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson: Sorting and Selection with Imprecise Comparisons. ICALP (1) 2009: 37-48
	2008
72		Miklós Ajtai: Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem. Theory of Computing 4(1): 21-51 (2008)
	2007
71		Miklós Ajtai: Generalizations of the Compactness Theorem and Gödel's Completeness Theorem for Nonstandard Finite Structures. TAMC 2007: 13-33
70		Miklós Ajtai, Cynthia Dwork: The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.. Electronic Colloquium on Computational Complexity (ECCC) 14(097): (2007)
	2006
69		Miklós Ajtai, Cynthia Dwork, Larry J. Stockmeyer: An Architecture for Provably Secure Computation. LATIN 2006: 56-67
	2005
68		Miklós Ajtai: Representing hard lattices with O(n log n) bits. STOC 2005: 94-103
67		Miklós Ajtai: A Non-linear Time Lower Bound for Boolean Branching Programs. Theory of Computing 1(1): 149-176 (2005)
	2004
66		Miklós Ajtai: A conjecture about polynomial time computable lattice-lattice functions. STOC 2004: 486-493
	2003
65		Miklós Ajtai: The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice. STOC 2003: 396-406
	2002
64		Miklós Ajtai: Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties. FOCS 2002: 733-742
63		Miklós Ajtai, Ravi Kumar, D. Sivakumar: Sampling Short Lattice Vectors and the Closest Lattice Vector Problem. IEEE Conference on Computational Complexity 2002: 53-57
62		Miklós Ajtai, T. S. Jayram, Ravi Kumar, D. Sivakumar: Approximate counting of inversions in a data stream. STOC 2002: 370-379
61		Miklós Ajtai: The invasiveness of off-line memory checking. STOC 2002: 504-513
60		Miklós Ajtai: A conjectured 0-1 law about the polynomial time computable properties of random lattices, I. Electronic Colloquium on Computational Complexity (ECCC)(061): (2002)
59		Miklós Ajtai, Randal C. Burns, Ronald Fagin, Darrell D. E. Long, Larry J. Stockmeyer: Compactly encoding unstructured inputs with differential compression. J. ACM 49(3): 318-367 (2002)
58		Miklós Ajtai: Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions. J. Comput. Syst. Sci. 65(1): 2-37 (2002)
	2001
57		Miklós Ajtai, Ravi Kumar, D. Sivakumar: An Overview of the Sieve Algorithm for the Shortest Lattice Vector Problem. CaLC 2001: 1-3
56		Miklós Ajtai, Ravi Kumar, D. Sivakumar: A sieve algorithm for the shortest lattice vector problem. STOC 2001: 601-610
55		Miklós Ajtai, Nimrod Megiddo, Orli Waarts: Improved Algorithms and Analysis for Secretary Problems and Generalizations. SIAM J. Discrete Math. 14(1): 1-27 (2001)
	2000
54		Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer: The Closure of Monadic NP. J. Comput. Syst. Sci. 60(3): 660-716 (2000)
	1999
53		Miklós Ajtai: A Non-linear Time Lower Bound for Boolean Branching Programs. FOCS 1999: 60-70
52		Miklós Ajtai: Generating Hard Instances of the Short Basis Problem. ICALP 1999: 1-9
51		Miklós Ajtai: Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract). STOC 1999: 632-641
50		Miklós Ajtai: A Non-linear Time Lower Bound for Boolean Branching Programs Electronic Colloquium on Computational Complexity (ECCC) 6(26): (1999)
	1998
49		Miklós Ajtai: The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions (Extended Abstract). STOC 1998: 10-19
48		Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer: The Closure of Monadic NP (Extended Abstract). STOC 1998: 309-318
47		Miklós Ajtai: Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions Electronic Colloquium on Computational Complexity (ECCC) 5(77): (1998)
46		Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts: Fairness in Scheduling J. Algorithms 29(2): 306-357 (1998)
	1997
45		Miklós Ajtai, Cynthia Dwork: A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. STOC 1997: 284-293
44		Miklós Ajtai: The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions. Electronic Colloquium on Computational Complexity (ECCC) 4(47): (1997)
	1996
43		Miklós Ajtai: Generating Hard Instances of Lattice Problems (Extended Abstract). STOC 1996: 99-108
42		Miklós Ajtai, Cynthia Dwork: A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence Electronic Colloquium on Computational Complexity (ECCC) 3(65): (1996)
41		Miklós Ajtai: Generating Hard Instances of Lattice Problems Electronic Colloquium on Computational Complexity (ECCC) 3(7): (1996)
40		Miklós Ajtai, Nimrod Megiddo: A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimensions. SIAM J. Comput. 25(6): 1171-1195 (1996)
	1995
39		Miklós Ajtai, Nimrod Megiddo, Orli Waarts: Improved Algorithms and Analysis for Secretary Problems and Generalizations. FOCS 1995: 473-482
38		Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts: Fairness in Scheduling. SODA 1995: 477-485
	1994
37		Miklós Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts: A Theory of Competitive Analysis for Distributed Algorithms FOCS 1994: 401-411
36		Miklós Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts: Competitiveness in Distributed Algorithms. PODC 1994: 398
35		Miklós Ajtai: Recursive Construction for 3-Regular Expanders. Combinatorica 14(4): 379-416 (1994)
34		Miklós Ajtai: The Complexity of the Pigeonhole Principle. Combinatorica 14(4): 417-433 (1994)
33		Miklós Ajtai: The Independence of the modulo p Counting Principles Electronic Colloquium on Computational Complexity (ECCC) 1(14): (1994)
32		Miklós Ajtai: Symmetric Systems of Linear Equations modulo p. Electronic Colloquium on Computational Complexity (ECCC) 1(15): (1994)
31		Miklós Ajtai, Yuri Gurevich: Datalog vs First-Order Logic. J. Comput. Syst. Sci. 49(3): 562-588 (1994)
	1993
30		Miklós Ajtai, Nathan Linial: The influence of large coalitions. Combinatorica 13(2): 129-145 (1993)
	1992
29		Miklós Ajtai, János Komlós, Endre Szemerédi: Halvers and Expanders FOCS 1992: 686-692
28		Miklós Ajtai, Noga Alon, Jehoshua Bruck, Robert Cypher, Ching-Tien Ho, Moni Naor, Endre Szemerédi: Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths FOCS 1992: 693-702
27		Miklós Ajtai, Nimrod Megiddo: A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension STOC 1992: 327-338
	1990
26		Miklós Ajtai, Ronald Fagin: Reachability Is Harder for Directed than for Undirected Finite Graphs. J. Symb. Log. 55(1): 113-150 (1990)
	1989
25		Miklós Ajtai, Yuri Gurevich: Datalog vs. First-Order Logic FOCS 1989: 142-147
24		Miklós Ajtai: First-Order Definability on Finite Structures. Ann. Pure Appl. Logic 45(3): 211-225 (1989)
23		Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi: Optimal Parallel Selection has Complexity O(Log Log n). J. Comput. Syst. Sci. 38(1): 125-133 (1989)
22		Miklós Ajtai, D. Karabeg, János Komlós, Endre Szemerédi: Sorting in Average Time o(log) n. SIAM J. Discrete Math. 2(3): 285-292 (1989)
	1988
21		Miklós Ajtai: The Complexity of the Pigeonhole Principle FOCS 1988: 346-355
20		Miklós Ajtai, Ronald Fagin: Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version) FOCS 1988: 358-367
19		Miklós Ajtai: A lower bound for finding predecessors in Yao's call probe model. Combinatorica 8(3): 235-247 (1988)
	1987
18		Miklós Ajtai: Recursive Construction for 3-Regular Expanders FOCS 1987: 295-304
17		Miklós Ajtai, János Komlós, Endre Szemerédi: Deterministic Simulation in LOGSPACE STOC 1987: 132-140
16		Miklós Ajtai, Yuri Gurevich: Monotone versus positive. J. ACM 34(4): 1004-1015 (1987)
	1986
15		Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi: Deterministic Selection in O(log log N) Parallel Time STOC 1986: 188-195
14		Miklós Ajtai, László Babai, Péter Hajnal, János Komlós, Pavel Pudlák, Vojtech Rödl, Endre Szemerédi, György Turán: Two lower bounds for branching programs STOC 1986: 30-38
	1985
13		Miklós Ajtai, Avi Wigderson: Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version) FOCS 1985: 11-19
	1984
12		Miklós Ajtai, Michael Ben-Or: A Theorem on Probabilistic Constant Depth Computations STOC 1984: 471-474
11		Miklós Ajtai, János Komlós, Gábor E. Tusnády: On optimal matchings. Combinatorica 4(4): 259-264 (1984)
10		Miklós Ajtai, Michael L. Fredman, János Komlós: Hash Functions for Priority Queues Information and Control 63(3): 217-225 (1984)
	1983
9		Miklós Ajtai, Michael L. Fredman, János Komlós: Hash Functions for Priority Queues FOCS 1983: 299-303
8		Miklós Ajtai, János Komlós, Endre Szemerédi: An O(n log n) Sorting Network STOC 1983: 1-9
7		Miklós Ajtai, János Komlós, Endre Szemerédi: Sorting in c log n parallel sets. Combinatorica 3(1): 1-19 (1983)
	1982
6		Miklós Ajtai, János Komlós, Endre Szemerédi: Largest random component of a k-cube. Combinatorica 2(1): 1-7 (1982)
5		Miklós Ajtai, János Komlós, Janos Pintz, Joel Spencer, Endre Szemerédi: Extremal Uncrowded Hypergraphs. J. Comb. Theory, Ser. A 32(3): 321-335 (1982)
	1981
4		Miklós Ajtai, János Komlós, Endre Szemerédi: The longest path in a random graph. Combinatorica 1(1): 1-12 (1981)
3		Miklós Ajtai, Paul Erdös, János Komlós, Endre Szemerédi: On Turáns theorem for sparse graphs. Combinatorica 1(4): 313-317 (1981)
	1980
2		Miklós Ajtai, János Komlós, Endre Szemerédi: A Note on Ramsey Numbers. J. Comb. Theory, Ser. A 29(3): 354-360 (1980)
	1978
1		Miklós Ajtai, János Komlós, Endre Szemerédi: There is no Fast Single Hashing Algorithm. Inf. Process. Lett. 7(6): 270-273 (1978)

Coauthor Index

1	Noga Alon	[28]
2	James Aspnes	[36] [37] [38] [46]
3	László Babai	[14]
4	Michael Ben-Or	[12]
5	Jehoshua Bruck	[28]
6	Randal C. Burns	[59]
7	Robert Cypher	[28]
8	Cynthia Dwork	[36] [37] [42] [45] [69] [70]
9	Paul Erdös	[3]
10	Ronald Fagin	[20] [26] [48] [54] [59]
11	Vitaly Feldman	[73]
12	Michael L. Fredman	[9] [10]
13	Yuri Gurevich	[16] [25] [31]
14	Péter Hajnal	[14]
15	Avinatan Hassidim	[73]
16	C. T. Howard Ho (Howard Ho, Ching-Tien Ho)	[28]
17	T. S. Jayram (Jayram S. Thathachar)	[62]
18	D. Karabeg	[22]
19	János Komlós	[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [14] [15] [17] [22] [23] [29]
20	Ravi Kumar (S. Ravi Kumar)	[56] [57] [62] [63]
21	Nathan Linial (Nati Linial)	[30]
22	Darrell D. E. Long	[59]
23	Nimrod Megiddo	[27] [39] [40] [55]
24	Moni Naor	[28] [38] [46]
25	Jelani Nelson	[73]
26	Janos Pintz	[5]
27	Pavel Pudlák	[14]
28	Yuval Rabani	[38] [46]
29	Vojtech Rödl	[14]
30	Leonard J. Schulman	[38] [46]
31	D. Sivakumar	[56] [57] [62] [63]
32	Joel H. Spencer (Joel Spencer)	[5]
33	William L. Steiger	[15] [23]
34	Larry J. Stockmeyer	[48] [54] [59] [69]
35	Endre Szemerédi	[1] [2] [3] [4] [5] [6] [7] [8] [14] [15] [17] [22] [23] [28] [29]
36	György Turán	[14]
37	Gábor E. Tusnády	[11]
38	Orli Waarts	[36] [37] [38] [39] [46] [55]
39	Avi Wigderson	[13]