Miklós Ajtai

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

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of one.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2022
The White-Box Adversarial Data Stream Model.
Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

2016
Sorting and Selection with Imprecise Comparisons.
ACM Trans. Algorithms, 2016

2013
Lower Bounds for RAMs and Quantifier Elimination.
Electron. Colloquium Comput. Complex., 2013

2012
Determinism versus nondeterminism with arithmetic tests and computation: extended abstract.
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011
Determinism Versus Nondeterminism with Arithmetic Tests and Computation.
Electron. Colloquium Comput. Complex., 2011

Secure Computation with Information Leaking to an Adversary.
Electron. Colloquium Comput. Complex., 2011

2010
Oblivious RAMs without Cryptographic Assumptions.
Electron. Colloquium Comput. Complex., 2010

Oblivious RAMs without cryptogrpahic assumptions.
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.
Theory Comput., 2008

Representing Hard Lattices with O(nlog n) Bits.
Chic. J. Theor. Comput. Sci., 2008

2007
The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence..
Electron. Colloquium Comput. Complex., 2007

Generalizations of the Compactness Theorem and Gödel's Completeness Theorem for Nonstandard Finite Structures.
Proceedings of the Theory and Applications of Models of Computation, 2007

2006
An Architecture for Provably Secure Computation.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

2005
Representing hard lattices with O(n log n) bits.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004
A conjecture about polynomial time computable lattice-lattice functions.
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.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002
Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions.
J. Comput. Syst. Sci., 2002

Compactly encoding unstructured inputs with differential compression.
J. ACM, 2002

A conjectured 0-1 law about the polynomial time computable properties of random lattices, I.
Electron. Colloquium Comput. Complex., 2002

Approximate counting of inversions in a data stream.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

The invasiveness of off-line memory checking.
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.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Sampling Short Lattice Vectors and the Closest Lattice Vector Problem.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001
Improved Algorithms and Analysis for Secretary Problems and Generalizations.
SIAM J. Discret. Math., 2001

A sieve algorithm for the shortest lattice vector problem.
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.
Proceedings of the Cryptography and Lattices, International Conference, 2001

2000
The Closure of Monadic NP.
J. Comput. Syst. Sci., 2000

1999
A Non-linear Time Lower Bound for Boolean Branching Programs
Electron. Colloquium Comput. Complex., 1999

Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Generating Hard Instances of the Short Basis Problem.
Proceedings of the Automata, 1999

1998
Fairness in Scheduling
J. Algorithms, 1998

Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions
Electron. Colloquium Comput. Complex., 1998

The Closure of Monadic NP (Extended Abstract).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

The Shortest Vector Problem in <i>L<sub>2</sub></i> is <i>NP</i>-hard for Randomized Reductions (Extended Abstract).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

1997
The Shortest Vector Problem in L<sub>2</sub> is NP-hard for Randomized Reductions.
Electron. Colloquium Comput. Complex., 1997

1996
A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimensions.
SIAM J. Comput., 1996

A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence
Electron. Colloquium Comput. Complex., 1996

Generating Hard Instances of Lattice Problems
Electron. Colloquium Comput. Complex., 1996

Generating Hard Instances of Lattice Problems (Extended Abstract).
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1994
Datalog vs First-Order Logic.
J. Comput. Syst. Sci., 1994

Symmetric Systems of Linear Equations modulo p.
Electron. Colloquium Comput. Complex., 1994

The Independence of the modulo p Counting Principles
Electron. Colloquium Comput. Complex., 1994

The Complexity of the Pigeonhole Principle.
Comb., 1994

Recursive Construction for 3-Regular Expanders.
Comb., 1994

Competitiveness in Distributed Algorithms.
Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, 1994

A Theory of Competitive Analysis for Distributed Algorithms
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
The influence of large coalitions.
Comb., 1993

1992
A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

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

Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1990
Reachability Is Harder for Directed than for Undirected Finite Graphs.
J. Symb. Log., 1990

Approximate Counting with Uniform Constant-Depth Circuits.
Proceedings of the Advances In Computational Complexity Theory, 1990

1989
Sorting in Average Time o(log) n.
SIAM J. Discret. Math., 1989

Optimal Parallel Selection has Complexity O(Log Log n).
J. Comput. Syst. Sci., 1989

First-Order Definability on Finite Structures.
Ann. Pure Appl. Log., 1989

Deterministic Simulation of Probabilistic Constant Depth Circuits.
Adv. Comput. Res., 1989

Almost Sorting in one Round.
Adv. Comput. Res., 1989

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

Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987
Monotone versus positive.
J. ACM, 1987

Deterministic Simulation in LOGSPACE
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1986
Deterministic Selection in O(log log N) Parallel Time
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Two lower bounds for branching programs
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

1985
Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version)
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984
Hash Functions for Priority Queues
Inf. Control., December, 1984

On optimal matchings.
Comb., 1984

A Theorem on Probabilistic Constant Depth Computations
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1983
Sorting in c log n parallel sets.
Comb., 1983

∑<sup>1</sup><sub>1</sub>-Formulae on finite structures.
Ann. Pure Appl. Log., 1983

An O(n log n) Sorting Network
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

1982
Extremal Uncrowded Hypergraphs.
J. Comb. Theory A, 1982

Largest random component of a k-cube.
Comb., 1982

1981
A Dense Infinite Sidon Sequence.
Eur. J. Comb., 1981

The longest path in a random graph.
Comb., 1981

On Turáns theorem for sparse graphs.
Comb., 1981

1980
A Note on Ramsey Numbers.
J. Comb. Theory A, 1980

1978
There is no Fast Single Hashing Algorithm.
Inf. Process. Lett., 1978


  Loading...