default search action
Miklós Ajtai
Person information
- award (2003): Knuth Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2022
- [c43]Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou:
The White-Box Adversarial Data Stream Model. PODS 2022: 15-27 - [i16]Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou:
The White-Box Adversarial Data Stream Model. CoRR abs/2204.09136 (2022)
2010 – 2019
- 2016
- [j33]Miklós Ajtai, Vitaly Feldman
, Avinatan Hassidim, Jelani Nelson:
Sorting and Selection with Imprecise Comparisons. ACM Trans. Algorithms 12(2): 19:1-19:19 (2016) - 2015
- [i15]Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson:
Sorting and Selection with Imprecise Comparisons. CoRR abs/1501.02911 (2015) - 2013
- [c42]Miklós Ajtai:
Lower bounds for RAMs and quantifier elimination. STOC 2013: 803-812 - [i14]Miklós Ajtai:
Lower Bounds for RAMs and Quantifier Elimination. CoRR abs/1306.0153 (2013) - [i13]Miklós Ajtai:
Lower Bounds for RAMs and Quantifier Elimination. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [c41]Miklós Ajtai:
Determinism versus nondeterminism with arithmetic tests and computation: extended abstract. STOC 2012: 249-268 - 2011
- [c40]Miklós Ajtai:
Secure computation with information leaking to an adversary. STOC 2011: 715-724 - [i12]Miklós Ajtai:
Secure Computation with Information Leaking to an Adversary. Electron. Colloquium Comput. Complex. TR11 (2011) - [i11]Miklós Ajtai:
Determinism Versus Nondeterminism with Arithmetic Tests and Computation. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [c39]Miklós Ajtai:
Oblivious RAMs without cryptogrpahic assumptions. STOC 2010: 181-190 - [i10]Miklós Ajtai:
Oblivious RAMs without Cryptographic Assumptions. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [c38]Miklós Ajtai, Vitaly Feldman
Sorting and Selection with Imprecise Comparisons. ICALP (1) 2009: 37-48 - 2008
- [j32]Miklós Ajtai:
Representing Hard Lattices with O(nlog n) Bits. Chic. J. Theor. Comput. Sci. 2008 (2008) - [j31]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 Comput. 4(1): 21-51 (2008) - 2007
- [c37]Miklós Ajtai:
Generalizations of the Compactness Theorem and Gödel's Completeness Theorem for Nonstandard Finite Structures. TAMC 2007: 13-33 - [i9]Miklós Ajtai, Cynthia Dwork:
The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [c36]Miklós Ajtai, Cynthia Dwork, Larry J. Stockmeyer:
An Architecture for Provably Secure Computation. LATIN 2006: 56-67 - 2005
- [j30]Miklós Ajtai:
A Non-linear Time Lower Bound for Boolean Branching Programs. Theory Comput. 1(1): 149-176 (2005) - [c35]Miklós Ajtai:
Representing hard lattices with O(n log n) bits. STOC 2005: 94-103 - 2004
- [c34]Miklós Ajtai:
A conjecture about polynomial time computable lattice-lattice functions. STOC 2004: 486-493 - 2003
- [c33]Miklós Ajtai:
The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice. STOC 2003: 396-406 - 2002
- [j29]Miklós Ajtai, Randal C. Burns
Compactly encoding unstructured inputs with differential compression. J. ACM 49(3): 318-367 (2002) - [j28]Miklós Ajtai:
Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions. J. Comput. Syst. Sci. 65(1): 2-37 (2002) - [c32]Miklós Ajtai, Ravi Kumar, D. Sivakumar:
Sampling Short Lattice Vectors and the Closest Lattice Vector Problem. CCC 2002: 53-57 - [c31]Miklós Ajtai:
Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties. FOCS 2002: 733-742 - [c30]Miklós Ajtai, T. S. Jayram, Ravi Kumar, D. Sivakumar:
Approximate counting of inversions in a data stream. STOC 2002: 370-379 - [c29]Miklós Ajtai:
The invasiveness of off-line memory checking. STOC 2002: 504-513 - [i8]Miklós Ajtai:
A conjectured 0-1 law about the polynomial time computable properties of random lattices, I. Electron. Colloquium Comput. Complex. TR02 (2002) - 2001
- [j27]Miklós Ajtai, Nimrod Megiddo, Orli Waarts:
Improved Algorithms and Analysis for Secretary Problems and Generalizations. SIAM J. Discret. Math. 14(1): 1-27 (2001) - [c28]Miklós Ajtai, Ravi Kumar, D. Sivakumar:
An Overview of the Sieve Algorithm for the Shortest Lattice Vector Problem. CaLC 2001: 1-3 - [c27]Miklós Ajtai, Ravi Kumar, D. Sivakumar:
A sieve algorithm for the shortest lattice vector problem. STOC 2001: 601-610 - 2000
- [j26]Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer:
The Closure of Monadic NP. J. Comput. Syst. Sci. 60(3): 660-716 (2000)
1990 – 1999
- 1999
- [c26]Miklós Ajtai:
A Non-linear Time Lower Bound for Boolean Branching Programs. FOCS 1999: 60-70 - [c25]Miklós Ajtai:
Generating Hard Instances of the Short Basis Problem. ICALP 1999: 1-9 - [c24]Miklós Ajtai:
Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract). STOC 1999: 632-641 - [i7]Miklós Ajtai:
A Non-linear Time Lower Bound for Boolean Branching Programs. Electron. Colloquium Comput. Complex. TR99 (1999) - 1998
- [j25]Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani
Fairness in Scheduling. J. Algorithms 29(2): 306-357 (1998) - [c23]Miklós Ajtai:
The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions (Extended Abstract). STOC 1998: 10-19 - [c22]Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer:
The Closure of Monadic NP (Extended Abstract). STOC 1998: 309-318 - [i6]Miklós Ajtai:
Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [c21]Miklós Ajtai, Cynthia Dwork:
A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. STOC 1997: 284-293 - [i5]Miklós Ajtai:
The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions. Electron. Colloquium Comput. Complex. TR97 (1997) - 1996
- [j24]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) - [c20]Miklós Ajtai:
Generating Hard Instances of Lattice Problems (Extended Abstract). STOC 1996: 99-108 - [i4]Miklós Ajtai:
Generating Hard Instances of Lattice Problems. Electron. Colloquium Comput. Complex. TR96 (1996) - [i3]Miklós Ajtai, Cynthia Dwork:
A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. Electron. Colloquium Comput. Complex. TR96 (1996) - 1995
- [c19]Miklós Ajtai, Nimrod Megiddo, Orli Waarts:
Improved Algorithms and Analysis for Secretary Problems and Generalizations. FOCS 1995: 473-482 - [c18]Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts:
Fairness in Scheduling. SODA 1995: 477-485 - 1994
- [j23]Miklós Ajtai:
Recursive Construction for 3-Regular Expanders. Comb. 14(4): 379-416 (1994) - [j22]Miklós Ajtai:
The Complexity of the Pigeonhole Principle. Comb. 14(4): 417-433 (1994) - [j21]Miklós Ajtai, Yuri Gurevich:
Datalog vs First-Order Logic. J. Comput. Syst. Sci. 49(3): 562-588 (1994) - [c17]Miklós Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts:
A Theory of Competitive Analysis for Distributed Algorithms. FOCS 1994: 401-411 - [c16]Miklós Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts:
Competitiveness in Distributed Algorithms. PODC 1994: 398 - [i2]Miklós Ajtai:
The Independence of the modulo p Counting Principles. Electron. Colloquium Comput. Complex. TR94 (1994) - [i1]Miklós Ajtai:
Symmetric Systems of Linear Equations modulo p. Electron. Colloquium Comput. Complex. TR94 (1994) - 1993
- [j20]Miklós Ajtai, Nathan Linial:
The influence of large coalitions. Comb. 13(2): 129-145 (1993) - 1992
- [c15]Miklós Ajtai, János Komlós, Endre Szemerédi:
Halvers and Expanders. FOCS 1992: 686-692 - [c14]Miklós Ajtai, Noga Alon, Jehoshua Bruck
Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths. FOCS 1992: 693-702 - [c13]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
- [j19]Miklós Ajtai, Ronald Fagin:
Reachability Is Harder for Directed than for Undirected Finite Graphs. J. Symb. Log. 55(1): 113-150 (1990) - [c12]Miklós Ajtai:
Approximate Counting with Uniform Constant-Depth Circuits. Advances In Computational Complexity Theory 1990: 1-20
1980 – 1989
- 1989
- [j18]Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi:
Almost Sorting in one Round. Adv. Comput. Res. 5: 117-125 (1989) - [j17]Miklós Ajtai, Avi Wigderson:
Deterministic Simulation of Probabilistic Constant Depth Circuits. Adv. Comput. Res. 5: 199-222 (1989) - [j16]Miklós Ajtai:
First-Order Definability on Finite Structures. Ann. Pure Appl. Log. 45(3): 211-225 (1989) - [j15]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) - [j14]Miklós Ajtai, D. Karabeg, János Komlós, Endre Szemerédi:
Sorting in Average Time o(log) n. SIAM J. Discret. Math. 2(3): 285-292 (1989) - [c11]Miklós Ajtai, Yuri Gurevich:
Datalog vs. First-Order Logic. FOCS 1989: 142-147 - 1988
- [j13]Miklós Ajtai:
A lower bound for finding predecessors in Yao's call probe model. Comb. 8(3): 235-247 (1988) - [c10]Miklós Ajtai:
The Complexity of the Pigeonhole Principle. FOCS 1988: 346-355 - [c9]Miklós Ajtai, Ronald Fagin:
Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version). FOCS 1988: 358-367 - 1987
- [j12]Miklós Ajtai, Yuri Gurevich:
Monotone versus positive. J. ACM 34(4): 1004-1015 (1987) - [c8]Miklós Ajtai:
Recursive Construction for 3-Regular Expanders. FOCS 1987: 295-304 - [c7]Miklós Ajtai, János Komlós, Endre Szemerédi:
Deterministic Simulation in LOGSPACE. STOC 1987: 132-140 - 1986
- [c6]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 - [c5]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 - 1985
- [c4]Miklós Ajtai, Avi Wigderson:
Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version). FOCS 1985: 11-19 - 1984
- [j11]Miklós Ajtai, János Komlós, Gábor E. Tusnády:
On optimal matchings. Comb. 4(4): 259-264 (1984) - [j10]Miklós Ajtai, Michael L. Fredman, János Komlós:
Hash Functions for Priority Queues. Inf. Control. 63(3): 217-225 (1984) - [c3]Miklós Ajtai, Michael Ben-Or:
A Theorem on Probabilistic Constant Depth Computations. STOC 1984: 471-474 - 1983
- [j9]Miklós Ajtai:
∑11-Formulae on finite structures. Ann. Pure Appl. Log. 24(1): 1-48 (1983) - [j8]Miklós Ajtai, János Komlós, Endre Szemerédi:
Sorting in c log n parallel sets. Comb. 3(1): 1-19 (1983) - [c2]Miklós Ajtai, Michael L. Fredman, János Komlós:
Hash Functions for Priority Queues. FOCS 1983: 299-303 - [c1]Miklós Ajtai, János Komlós, Endre Szemerédi:
An O(n log n) Sorting Network. STOC 1983: 1-9 - 1982
- [j7]Miklós Ajtai, János Komlós, Endre Szemerédi:
Largest random component of a k-cube. Comb. 2(1): 1-7 (1982) - [j6]Miklós Ajtai, János Komlós, Janos Pintz, Joel Spencer, Endre Szemerédi:
Extremal Uncrowded Hypergraphs. J. Comb. Theory A 32(3): 321-335 (1982) - 1981
- [j5]Miklós Ajtai, János Komlós, Endre Szemerédi:
The longest path in a random graph. Comb. 1(1): 1-12 (1981) - [j4]Miklós Ajtai, Paul Erdös, János Komlós, Endre Szemerédi:
On Turáns theorem for sparse graphs. Comb. 1(4): 313-317 (1981) - [j3]Miklós Ajtai, János Komlós, Endre Szemerédi:
A Dense Infinite Sidon Sequence. Eur. J. Comb. 2(1): 1-11 (1981) - 1980
- [j2]Miklós Ajtai, János Komlós, Endre Szemerédi:
A Note on Ramsey Numbers. J. Comb. Theory A 29(3): 354-360 (1980)
1970 – 1979
- 1978
- [j1]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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-05 20:23 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: