Miklós Ajtai | Academic Influence

Miklós Ajtai's AcademicInfluence.com Rankings

Miklós Ajtai

Computer Science

#1010

World Rank

#1047

Historical Rank

Theoretical Computer Science

#23

World Rank

#23

Historical Rank

Database

#5536

World Rank

#5743

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Miklós Ajtai's Degrees

PhD Computer Science Eötvös Loránd University

Similar Degrees You Can Earn

Best Online PhD of Computer Science (Doctorates) 2025

Why Is Miklós Ajtai Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Miklós Ajtai is a computer scientist at the IBM Almaden Research Center, United States. In 2003, he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm , exponential lower bounds, superlinear time-space tradeoffs for branching programs, and other "unique and spectacular" results. He is a member of the U.S. National Academy of Sciences.

(See a Problem?)

Miklós Ajtai's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Generating hard instances of lattice problems (extended abstract) (1996) (988)
Generating Hard Instances of Lattice Problems (1996) (843)
A public-key cryptosystem with worst-case/average-case equivalence (1997) (684)
An 0(n log n) sorting network (1983) (598)
∑11-Formulae on finite structures (1983) (580)
A sieve algorithm for the shortest lattice vector problem (2001) (546)
The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract) (1998) (530)
O(n LOG n) SORTING NETWORK. (1983) (467)
A Note on Ramsey Numbers (1980) (365)
Sorting inc logn parallel steps (1983) (361)
Generating Hard Instances of the Short Basis Problem (1999) (354)
Crossing-Free Subgraphs (1982) (336)
The complexity of the Pigeonhole Principle (1988) (250)
On optimal matchings (1984) (240)
Deterministic simulation in LOGSPACE (1987) (237)
Sorting in c log n parallel sets (1983) (226)
A Dense Infinite Sidon Sequence (1981) (154)
Reachability is harder for directed than for undirected finite graphs (1988) (150)
A theorem on probabilistic constant depth Computations (1984) (135)
Largest random component of ak-cube (1982) (127)
The longest path in a random graph (1981) (116)
First Occurrence of Hamilton Cycles in Random Graphs (1985) (112)
Monotone versus positive (1987) (111)
Deterministic simulation of probabilistic constant depth circuits (1985) (106)
A non-linear time lower bound for Boolean branching programs (1999) (101)
A lower bound for finding predecessors in Yao's cell probe model (1988) (101)
Compactly encoding unstructured inputs with differential compression (2002) (96)
Datalog vs. first-order logic (1989) (95)
Sampling short lattice vectors and the closest lattice vector problem (2002) (92)
Extremal Uncrowded Hypergraphs (1982) (90)
Two lower bounds for branching programs (1986) (77)
A theory of competitive analysis for distributed algorithms (1994) (75)
Oblivious RAMs without cryptogrpahic assumptions (2010) (67)
The influence of large coalitions (1993) (65)
On Turán’s theorem for sparse graphs (1981) (64)
Hash functions for priority queues (1983) (59)
Sorting and Selection with Imprecise Comparisons (2009) (59)
Approximate Counting with Uniform Constant-Depth Circuits (1990) (56)
The Closure of Monadic NP (2000) (56)
Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions (2002) (55)
Improved algorithms and analysis for secretary problems and generalizations (1995) (53)
Approximate counting of inversions in a data stream (2002) (52)
Recursive construction for 3-regular expanders (1987) (50)
Fairness in scheduling (1995) (50)
Parity and the Pigeonhole Principle (1990) (47)
The independence of the modulo p counting principles (1994) (43)
Every group admits a bad topology (1983) (43)
The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice (2003) (40)
Representing hard lattices with O(n log n) bits (2005) (40)
Construction of a thin set with small fourier coefficients (1990) (37)
Determinism versus non-determinism for linear time RAMs (extended abstract) (1999) (34)
Fault tolerant graphs, perfect hash functions and disjoint paths (1992) (33)
Generalizations of the Compactness Theorem and Gödel's Completeness Theorem for Nonstandard Finite Structures (2007) (33)
Secure computation with information leaking to an adversary (2011) (31)
Deterministic selection in O(loglog N) parallel time (1986) (30)
Optimal Parallel Selection has Complexity O(Log Log n) (1989) (28)
A deterministic poly(log log N)-time N-processor algorithm for linear programming in fixed dimension (1992) (27)
First-Order Definability on Finite Structures (1989) (27)
Random lattices and a conjectured 0 - 1 law about their polynomial time computable properties (2002) (23)
The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence (2007) (23)
Symmetric Systems of Linear Equations modulo p (1994) (19)
Almost Sorting in one Round (1989) (19)
Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem (2008) (17)
Isomorphism and higher order equivalence (1979) (17)
Halvers and Expanders (1992) (17)
On a class of finite lattices (1973) (16)
The Set of Continuous Functions with the Everywhere Convergent Fourier Series (1987) (15)
Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version) (1985) (14)
The closure of Monadic NP (extended abstract) (1998) (12)
A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimensions (1996) (11)
There is no Fast Single Hashing Algorithm (1978) (9)
The invasiveness of off-line memory checking (2002) (9)
On the Existence of modulo p Cardinality Functions (1995) (8)
Halvers and expanders (switching) (1992) (8)
On the boundedness of definable linear operators (1974) (8)
An Overview of the Sieve Algorithm for the Shortest Lattice Vector Problem (2001) (7)
The White-Box Adversarial Data Stream Model (2022) (6)
A Tribute to Paul Erdős: Generating expanders from two permutations (1990) (3)
Review: Alexander S. Kechris, Alain Louveau, Descriptive Set Theory and the Structure of Sets of Uniqueness (1991) (3)
On coverings of random graphs (1982) (2)
Competitiveness in distributed algorithms (1994) (1)
A conjectured 0-1 law about the polynomial time computable properties of random lattices, I (2002) (1)
Sorting in Average Time o(log) n (1989) (1)
Determinism versus nondeterminism with arithmetic tests and computation: extended abstract (2012) (1)
Lower bounds for RAMs and quantifier elimination (2013) (0)
A conjecture about polynomial time computable lattice-lattice functions (2004) (0)
Boolean complexity and probabilistic constructions (1992) (0)
The longest path in a random graph [WAIT to hear from author; wrong PDF sent] (2020) (0)
On the Carpool ProblemorLong-Term Behaviour of a Chip Game Concerning Scheduling (2007) (0)
An Architecture for Provably Secure Computation (2006) (0)
Divisibility properties of recurring sequences (1969) (0)
Kechris Alexander S. and Louveau Alain. Descriptive set theory and the structure of sets of uniqueness. London Mathematical Society lecture note series, no. 128. Cambridge University Press, Cambridge etc. 1987, vii + 367 pp. (1991) (0)
The Influence of Large Coalitions Miklos Ajtai* and Nathal Linialt (2005) (0)

This paper list is powered by the following services:

Other Resources About Miklós Ajtai

en.wikipedia.org

What Schools Are Affiliated With Miklós Ajtai?

Miklós Ajtai is affiliated with the following schools: