| 2008 |
|---|
| 72 | EE | 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 | EE | Miklós Ajtai:
Generalizations of the Compactness Theorem and Gödel's Completeness Theorem for Nonstandard Finite Structures.
TAMC 2007: 13-33 |
| 70 | EE | 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 | EE | Miklós Ajtai,
Cynthia Dwork,
Larry J. Stockmeyer:
An Architecture for Provably Secure Computation.
LATIN 2006: 56-67 |
| 2005 |
|---|
| 68 | EE | Miklós Ajtai:
Representing hard lattices with O(n log n) bits.
STOC 2005: 94-103 |
| 67 | EE | Miklós Ajtai:
A Non-linear Time Lower Bound for Boolean Branching Programs.
Theory of Computing 1(1): 149-176 (2005) |
| 2004 |
|---|
| 66 | EE | Miklós Ajtai:
A conjecture about polynomial time computable lattice-lattice functions.
STOC 2004: 486-493 |
| 2003 |
|---|
| 65 | EE | 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 | EE | Miklós Ajtai:
Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties.
FOCS 2002: 733-742 |
| 63 | EE | 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 | EE | Miklós Ajtai,
T. S. Jayram,
Ravi Kumar,
D. Sivakumar:
Approximate counting of inversions in a data stream.
STOC 2002: 370-379 |
| 61 | EE | Miklós Ajtai:
The invasiveness of off-line memory checking.
STOC 2002: 504-513 |
| 60 | EE | 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 | EE | 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 | EE | Miklós Ajtai:
Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions.
J. Comput. Syst. Sci. 65(1): 2-37 (2002) |
| 2001 |
|---|
| 57 | EE | Miklós Ajtai,
Ravi Kumar,
D. Sivakumar:
An Overview of the Sieve Algorithm for the Shortest Lattice Vector Problem.
CaLC 2001: 1-3 |
| 56 | EE | Miklós Ajtai,
Ravi Kumar,
D. Sivakumar:
A sieve algorithm for the shortest lattice vector problem.
STOC 2001: 601-610 |
| 55 | EE | 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 | EE | Miklós Ajtai:
A Non-linear Time Lower Bound for Boolean Branching Programs.
FOCS 1999: 60-70 |
| 52 | EE | Miklós Ajtai:
Generating Hard Instances of the Short Basis Problem.
ICALP 1999: 1-9 |
| 51 | EE | Miklós Ajtai:
Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract).
STOC 1999: 632-641 |
| 50 | EE | Miklós Ajtai:
A Non-linear Time Lower Bound for Boolean Branching Programs
Electronic Colloquium on Computational Complexity (ECCC) 6(26): (1999) |
| 1998 |
|---|
| 49 | EE | Miklós Ajtai:
The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions (Extended Abstract).
STOC 1998: 10-19 |
| 48 | EE | Miklós Ajtai,
Ronald Fagin,
Larry J. Stockmeyer:
The Closure of Monadic NP (Extended Abstract).
STOC 1998: 309-318 |
| 47 | EE | 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 | EE | Miklós Ajtai,
Cynthia Dwork:
A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence.
STOC 1997: 284-293 |
| 44 | EE | 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 | EE | Miklós Ajtai:
Generating Hard Instances of Lattice Problems (Extended Abstract).
STOC 1996: 99-108 |
| 42 | EE | 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 | EE | 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 | EE | Miklós Ajtai:
The Independence of the modulo p Counting Principles
Electronic Colloquium on Computational Complexity (ECCC) 1(14): (1994) |
| 32 | EE | 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 | EE | 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) |
