Miklós Ajtai

Publication Activity (10 Years)

Years Active: 1978-2022
Publications (10 Years): 4

Top Topics

Functional Programming

Quantifier Elimination

Selection Criteria

Top Venues

Electron. Colloquium Comput. Complex.

Publications

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 (2022)
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)
Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson
Sorting and Selection with Imprecise Comparisons. ACM Trans. Algorithms 12 (2) (2016)
Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson
Sorting and Selection with Imprecise Comparisons. CoRR (2015)
Miklós Ajtai
Lower Bounds for RAMs and Quantifier Elimination. Electron. Colloquium Comput. Complex. 20 (2013)
Miklós Ajtai
Lower bounds for RAMs and quantifier elimination. STOC (2013)
Miklós Ajtai
Lower Bounds for RAMs and Quantifier Elimination. CoRR (2013)
Miklós Ajtai
Determinism versus nondeterminism with arithmetic tests and computation: extended abstract. STOC (2012)
Miklós Ajtai
Secure computation with information leaking to an adversary. STOC (2011)
Miklós Ajtai
Secure Computation with Information Leaking to an Adversary. Electron. Colloquium Comput. Complex. 18 (2011)
Miklós Ajtai
Determinism Versus Nondeterminism with Arithmetic Tests and Computation. Electron. Colloquium Comput. Complex. 18 (2011)
Miklós Ajtai
Oblivious RAMs without Cryptographic Assumptions. Electron. Colloquium Comput. Complex. 17 (2010)
Miklós Ajtai
Oblivious RAMs without cryptogrpahic assumptions. STOC (2010)
Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson
Sorting and Selection with Imprecise Comparisons. ICALP (1) (2009)
Miklós Ajtai
Representing Hard Lattices with O(nlog n) Bits. Chic. J. Theor. Comput. Sci. 2008 (2008)
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) (2008)
Miklós Ajtai, Cynthia Dwork
The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.. Electron. Colloquium Comput. Complex. 14 (097) (2007)
Miklós Ajtai
Generalizations of the Compactness Theorem and Gödel's Completeness Theorem for Nonstandard Finite Structures. TAMC (2007)
Miklós Ajtai, Cynthia Dwork, Larry J. Stockmeyer
An Architecture for Provably Secure Computation. LATIN (2006)
Miklós Ajtai
Representing hard lattices with O(n log n) bits. STOC (2005)
Miklós Ajtai
A Non-linear Time Lower Bound for Boolean Branching Programs. Theory Comput. 1 (1) (2005)
Miklós Ajtai
A conjecture about polynomial time computable lattice-lattice functions. STOC (2004)
Miklós Ajtai
The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice. STOC (2003)
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) (2002)
Miklós Ajtai
The invasiveness of off-line memory checking. STOC (2002)
Miklós Ajtai, T. S. Jayram, Ravi Kumar, D. Sivakumar
Approximate counting of inversions in a data stream. STOC (2002)
Miklós Ajtai
A conjectured 0-1 law about the polynomial time computable properties of random lattices, I. Electron. Colloquium Comput. Complex. (061) (2002)
Miklós Ajtai, Ravi Kumar, D. Sivakumar
Sampling Short Lattice Vectors and the Closest Lattice Vector Problem. Computational Complexity Conference (2002)
Miklós Ajtai
Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties. FOCS (2002)
Miklós Ajtai
Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions. J. Comput. Syst. Sci. 65 (1) (2002)
Miklós Ajtai, Ravi Kumar, D. Sivakumar
A sieve algorithm for the shortest lattice vector problem. STOC (2001)
Miklós Ajtai, Nimrod Megiddo, Orli Waarts
Improved Algorithms and Analysis for Secretary Problems and Generalizations. SIAM J. Discret. Math. 14 (1) (2001)
Miklós Ajtai, Ravi Kumar, D. Sivakumar
An Overview of the Sieve Algorithm for the Shortest Lattice Vector Problem. CaLC (2001)
Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer
The Closure of Monadic NP. J. Comput. Syst. Sci. 60 (3) (2000)
Miklós Ajtai
A Non-linear Time Lower Bound for Boolean Branching Programs Electron. Colloquium Comput. Complex. 6 (26) (1999)
Miklós Ajtai
Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract). STOC (1999)
Miklós Ajtai
Generating Hard Instances of the Short Basis Problem. ICALP (1999)
Miklós Ajtai
A Non-linear Time Lower Bound for Boolean Branching Programs. FOCS (1999)
Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts
Fairness in Scheduling J. Algorithms 29 (2) (1998)
Miklós Ajtai
-hard for Randomized Reductions (Extended Abstract). STOC (1998)
Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer
The Closure of Monadic NP (Extended Abstract). STOC (1998)
Miklós Ajtai
Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions Electron. Colloquium Comput. Complex. 5 (77) (1998)
Miklós Ajtai, Cynthia Dwork
A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. STOC (1997)
Miklós Ajtai
is NP-hard for Randomized Reductions. Electron. Colloquium Comput. Complex. 4 (47) (1997)
Miklós Ajtai
Generating Hard Instances of Lattice Problems Electron. Colloquium Comput. Complex. 3 (7) (1996)
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) (1996)
Miklós Ajtai, Cynthia Dwork
A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence Electron. Colloquium Comput. Complex. 3 (65) (1996)
Miklós Ajtai
Generating Hard Instances of Lattice Problems (Extended Abstract). STOC (1996)
Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts
Fairness in Scheduling. SODA (1995)
Miklós Ajtai, Nimrod Megiddo, Orli Waarts
Improved Algorithms and Analysis for Secretary Problems and Generalizations. FOCS (1995)
Miklós Ajtai
Recursive Construction for 3-Regular Expanders. Comb. 14 (4) (1994)
Miklós Ajtai, Yuri Gurevich
Datalog vs First-Order Logic. J. Comput. Syst. Sci. 49 (3) (1994)
Miklós Ajtai
The Independence of the modulo p Counting Principles Electron. Colloquium Comput. Complex. 1 (14) (1994)
Miklós Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts
A Theory of Competitive Analysis for Distributed Algorithms FOCS (1994)
Miklós Ajtai
Symmetric Systems of Linear Equations modulo p. Electron. Colloquium Comput. Complex. 1 (15) (1994)
Miklós Ajtai
The Complexity of the Pigeonhole Principle. Comb. 14 (4) (1994)
Miklós Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts
Competitiveness in Distributed Algorithms. PODC (1994)
Miklós Ajtai, Nathan Linial
The influence of large coalitions. Comb. 13 (2) (1993)
Miklós Ajtai, Nimrod Megiddo
A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension STOC (1992)
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)
Miklós Ajtai, János Komlós, Endre Szemerédi
Halvers and Expanders FOCS (1992)
Miklós Ajtai
Approximate Counting with Uniform Constant-Depth Circuits. Advances In Computational Complexity Theory (1990)
Miklós Ajtai, Ronald Fagin
Reachability Is Harder for Directed than for Undirected Finite Graphs. J. Symb. Log. 55 (1) (1990)
Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi
Almost Sorting in one Round. Adv. Comput. Res. 5 (1989)
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) (1989)
Miklós Ajtai, Yuri Gurevich
Datalog vs. First-Order Logic FOCS (1989)
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) (1989)
Miklós Ajtai, Avi Wigderson
Deterministic Simulation of Probabilistic Constant Depth Circuits. Adv. Comput. Res. 5 (1989)
Miklós Ajtai
First-Order Definability on Finite Structures. Ann. Pure Appl. Log. 45 (3) (1989)
Miklós Ajtai
A lower bound for finding predecessors in Yao's call probe model. Comb. 8 (3) (1988)
Miklós Ajtai
The Complexity of the Pigeonhole Principle FOCS (1988)
Miklós Ajtai, Ronald Fagin
Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version) FOCS (1988)
Miklós Ajtai, Yuri Gurevich
Monotone versus positive. J. ACM 34 (4) (1987)
Miklós Ajtai, János Komlós, Endre Szemerédi
Deterministic Simulation in LOGSPACE STOC (1987)
Miklós Ajtai
Recursive Construction for 3-Regular Expanders FOCS (1987)
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)
Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi
Deterministic Selection in O(log log N) Parallel Time STOC (1986)
Miklós Ajtai, Avi Wigderson
Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version) FOCS (1985)
Miklós Ajtai, János Komlós, Gábor E. Tusnády
On optimal matchings. Comb. 4 (4) (1984)
Miklós Ajtai, Michael L. Fredman, János Komlós
Hash Functions for Priority Queues Inf. Control. 63 (3) (1984)
Miklós Ajtai, Michael Ben-Or
A Theorem on Probabilistic Constant Depth Computations STOC (1984)
Miklós Ajtai, János Komlós, Endre Szemerédi
Sorting in c log n parallel sets. Comb. 3 (1) (1983)
Miklós Ajtai, János Komlós, Endre Szemerédi
An O(n log n) Sorting Network STOC (1983)
Miklós Ajtai
-Formulae on finite structures. Ann. Pure Appl. Log. 24 (1) (1983)
Miklós Ajtai, Michael L. Fredman, János Komlós
Hash Functions for Priority Queues FOCS (1983)
Miklós Ajtai, János Komlós, Janos Pintz, Joel Spencer, Endre Szemerédi
Extremal Uncrowded Hypergraphs. J. Comb. Theory, Ser. A 32 (3) (1982)
Miklós Ajtai, János Komlós, Endre Szemerédi
Largest random component of a k-cube. Comb. 2 (1) (1982)
Miklós Ajtai, János Komlós, Endre Szemerédi
The longest path in a random graph. Comb. 1 (1) (1981)
Miklós Ajtai, János Komlós, Endre Szemerédi
A Dense Infinite Sidon Sequence. Eur. J. Comb. 2 (1) (1981)
Miklós Ajtai, Paul Erdös, János Komlós, Endre Szemerédi
On Turáns theorem for sparse graphs. Comb. 1 (4) (1981)
Miklós Ajtai, János Komlós, Endre Szemerédi
A Note on Ramsey Numbers. J. Comb. Theory, Ser. A 29 (3) (1980)
Miklós Ajtai, János Komlós, Endre Szemerédi
There is no Fast Single Hashing Algorithm. Inf. Process. Lett. 7 (6) (1978)