The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Miklós Ajtai: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

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

  69. Sorting and Selection with Imprecise Comparisons. [Citation Graph (, )][DBLP]


  70. Oblivious RAMs without cryptogrpahic assumptions. [Citation Graph (, )][DBLP]


  71. The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.. [Citation Graph (, )][DBLP]


Search in 0.007secs, Finished in 0.010secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002