Miklós Ajtai

According to our database, Miklós Ajtai authored at least 77 papers between 1978 and 2022.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of one.

2022

The White-Box Adversarial Data Stream Model.

Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

2016

Sorting and Selection with Imprecise Comparisons.

Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson

ACM Trans. Algorithms, 2016

2013

Lower Bounds for RAMs and Quantifier Elimination.

Miklós Ajtai

Electron. Colloquium Comput. Complex., 2013

2012

Determinism versus nondeterminism with arithmetic tests and computation: extended abstract.

Miklós Ajtai

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

Determinism Versus Nondeterminism with Arithmetic Tests and Computation.

Miklós Ajtai

Electron. Colloquium Comput. Complex., 2011

Secure Computation with Information Leaking to an Adversary.

Miklós Ajtai

Electron. Colloquium Comput. Complex., 2011

2010

Oblivious RAMs without Cryptographic Assumptions.

Miklós Ajtai

Electron. Colloquium Comput. Complex., 2010

Oblivious RAMs without cryptogrpahic assumptions.

Miklós Ajtai

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

2008

Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem.

Miklós Ajtai

Theory Comput., 2008

Representing Hard Lattices with O(nlog n) Bits.

Miklós Ajtai

Chic. J. Theor. Comput. Sci., 2008

2007

The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence..

Miklós Ajtai, Cynthia Dwork

Electron. Colloquium Comput. Complex., 2007

Generalizations of the Compactness Theorem and Gödel's Completeness Theorem for Nonstandard Finite Structures.

Miklós Ajtai

Proceedings of the Theory and Applications of Models of Computation, 2007

2006

An Architecture for Provably Secure Computation.

Miklós Ajtai, Cynthia Dwork, Larry J. Stockmeyer

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

2005

Representing hard lattices with O(n log n) bits.

Miklós Ajtai

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004

A conjecture about polynomial time computable lattice-lattice functions.

Miklós Ajtai

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

2003

The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice.

Miklós Ajtai

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions.

Miklós Ajtai

J. Comput. Syst. Sci., 2002

Compactly encoding unstructured inputs with differential compression.

Miklós Ajtai, Randal C. Burns, Ronald Fagin, Darrell D. E. Long, Larry J. Stockmeyer

J. ACM, 2002

A conjectured 0-1 law about the polynomial time computable properties of random lattices, I.

Miklós Ajtai

Electron. Colloquium Comput. Complex., 2002

Approximate counting of inversions in a data stream.

Miklós Ajtai, T. S. Jayram, Ravi Kumar, D. Sivakumar

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

The invasiveness of off-line memory checking.

Miklós Ajtai

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties.

Miklós Ajtai

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Sampling Short Lattice Vectors and the Closest Lattice Vector Problem.

Miklós Ajtai, Ravi Kumar, D. Sivakumar

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

Improved Algorithms and Analysis for Secretary Problems and Generalizations.

Miklós Ajtai, Nimrod Megiddo, Orli Waarts

SIAM J. Discret. Math., 2001

A sieve algorithm for the shortest lattice vector problem.

Miklós Ajtai, Ravi Kumar, D. Sivakumar

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

An Overview of the Sieve Algorithm for the Shortest Lattice Vector Problem.

Miklós Ajtai, Ravi Kumar, D. Sivakumar

Proceedings of the Cryptography and Lattices, International Conference, 2001

2000

The Closure of Monadic NP.

Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer

J. Comput. Syst. Sci., 2000

1999

A Non-linear Time Lower Bound for Boolean Branching Programs

Miklós Ajtai

Electron. Colloquium Comput. Complex., 1999

Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract).

Miklós Ajtai

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Generating Hard Instances of the Short Basis Problem.

Miklós Ajtai

Proceedings of the Automata, 1999

1998

Fairness in Scheduling

Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts

J. Algorithms, 1998

Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions

Miklós Ajtai

Electron. Colloquium Comput. Complex., 1998

The Closure of Monadic NP (Extended Abstract).

Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

The Shortest Vector Problem in <i>L₂</i> is <i>NP</i>-hard for Randomized Reductions (Extended Abstract).

Miklós Ajtai

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

1997

The Shortest Vector Problem in L₂ is NP-hard for Randomized Reductions.

Miklós Ajtai

Electron. Colloquium Comput. Complex., 1997

1996

A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimensions.

Miklós Ajtai, Nimrod Megiddo

SIAM J. Comput., 1996

A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence

Miklós Ajtai, Cynthia Dwork

Electron. Colloquium Comput. Complex., 1996

Generating Hard Instances of Lattice Problems

Miklós Ajtai

Electron. Colloquium Comput. Complex., 1996

Generating Hard Instances of Lattice Problems (Extended Abstract).

Miklós Ajtai

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1994

Datalog vs First-Order Logic.

Miklós Ajtai, Yuri Gurevich

J. Comput. Syst. Sci., 1994

Symmetric Systems of Linear Equations modulo p.

Miklós Ajtai

Electron. Colloquium Comput. Complex., 1994

The Independence of the modulo p Counting Principles

Miklós Ajtai

Electron. Colloquium Comput. Complex., 1994

The Complexity of the Pigeonhole Principle.

Miklós Ajtai

Comb., 1994

Recursive Construction for 3-Regular Expanders.

Miklós Ajtai

Comb., 1994

Competitiveness in Distributed Algorithms.

Miklós Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts

Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, 1994

A Theory of Competitive Analysis for Distributed Algorithms

Miklós Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

The influence of large coalitions.

Miklós Ajtai, Nathan Linial

Comb., 1993

1992

A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension

Miklós Ajtai, Nimrod Megiddo

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Halvers and Expanders

Miklós Ajtai, János Komlós, Endre Szemerédi

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths

Miklós Ajtai, Noga Alon, Jehoshua Bruck, Robert Cypher, Ching-Tien Ho, Moni Naor, Endre Szemerédi

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1990

Reachability Is Harder for Directed than for Undirected Finite Graphs.

Miklós Ajtai, Ronald Fagin

J. Symb. Log., 1990

Approximate Counting with Uniform Constant-Depth Circuits.

Miklós Ajtai

Proceedings of the Advances In Computational Complexity Theory, 1990

1989

Sorting in Average Time o(log) n.

Miklós Ajtai, D. Karabeg, János Komlós, Endre Szemerédi

SIAM J. Discret. Math., 1989

Optimal Parallel Selection has Complexity O(Log Log n).

Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi

J. Comput. Syst. Sci., 1989

First-Order Definability on Finite Structures.

Miklós Ajtai

Ann. Pure Appl. Log., 1989

Deterministic Simulation of Probabilistic Constant Depth Circuits.

Miklós Ajtai, Avi Wigderson

Adv. Comput. Res., 1989

Almost Sorting in one Round.

Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi

Adv. Comput. Res., 1989

1988

A lower bound for finding predecessors in Yao's call probe model.

Miklós Ajtai

Comb., 1988

Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version)

Miklós Ajtai, Ronald Fagin

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987

Monotone versus positive.

Miklós Ajtai, Yuri Gurevich

J. ACM, 1987

Deterministic Simulation in LOGSPACE

Miklós Ajtai, János Komlós, Endre Szemerédi

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1986

Deterministic Selection in O(log log N) Parallel Time

Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Two lower bounds for branching programs

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

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

1985

Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version)

Miklós Ajtai, Avi Wigderson

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984

Hash Functions for Priority Queues

Miklós Ajtai, Michael L. Fredman, János Komlós

Inf. Control., December, 1984

On optimal matchings.

Miklós Ajtai, János Komlós, Gábor E. Tusnády

Comb., 1984

A Theorem on Probabilistic Constant Depth Computations

Miklós Ajtai, Michael Ben-Or

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1983

Sorting in c log n parallel sets.

Miklós Ajtai, János Komlós, Endre Szemerédi

Comb., 1983

∑¹₁-Formulae on finite structures.

Miklós Ajtai

Ann. Pure Appl. Log., 1983

An O(n log n) Sorting Network

Miklós Ajtai, János Komlós, Endre Szemerédi

Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982

Extremal Uncrowded Hypergraphs.

Miklós Ajtai, János Komlós, Janos Pintz, Joel Spencer, Endre Szemerédi

J. Comb. Theory A, 1982

Largest random component of a k-cube.

Miklós Ajtai, János Komlós, Endre Szemerédi

Comb., 1982

1981

A Dense Infinite Sidon Sequence.

Miklós Ajtai, János Komlós, Endre Szemerédi

Eur. J. Comb., 1981

The longest path in a random graph.

Miklós Ajtai, János Komlós, Endre Szemerédi

Comb., 1981

On Turáns theorem for sparse graphs.

Miklós Ajtai, Paul Erdös, János Komlós, Endre Szemerédi

Comb., 1981

1980

A Note on Ramsey Numbers.

Miklós Ajtai, János Komlós, Endre Szemerédi

J. Comb. Theory A, 1980

1978

There is no Fast Single Hashing Algorithm.

Miklós Ajtai, János Komlós, Endre Szemerédi

Inf. Process. Lett., 1978