Miklós Ajtai

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

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2013
Lower bounds for RAMs and quantifier elimination.
Proceedings of the Symposium on Theory of Computing Conference, 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.
Electronic Colloquium on Computational Complexity (ECCC), 2011

Secure computation with information leaking to an adversary.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010
Oblivious RAMs without Cryptographic Assumptions.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Oblivious RAMs without cryptogrpahic assumptions.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

2009
Sorting and Selection with Imprecise Comparisons.
Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

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

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

2007
The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence..
Electronic Colloquium on Computational Complexity (ECCC), 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.
Electronic Colloquium on Computational Complexity (ECCC), 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
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
Electronic Colloquium on Computational Complexity (ECCC), 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

A Non-linear Time Lower Bound for Boolean Branching Programs.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998
Fairness in Scheduling
J. Algorithms, 1998

Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions
Electronic Colloquium on Computational Complexity (ECCC), 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 L2 is NP-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 L2 is NP-hard for Randomized Reductions.
Electronic Colloquium on Computational Complexity (ECCC), 1997

A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 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
Electronic Colloquium on Computational Complexity (ECCC), 1996

Generating Hard Instances of Lattice Problems
Electronic Colloquium on Computational Complexity (ECCC), 1996

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

1995
Fairness in Scheduling.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Improved Algorithms and Analysis for Secretary Problems and Generalizations.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

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

Symmetric Systems of Linear Equations modulo p.
Electronic Colloquium on Computational Complexity (ECCC), 1994

The Independence of the modulo p Counting Principles
Electronic Colloquium on Computational Complexity (ECCC), 1994

The Complexity of the Pigeonhole Principle.
Combinatorica, 1994

Recursive Construction for 3-Regular Expanders.
Combinatorica, 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.
Combinatorica, 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. Discrete 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. Logic, 1989

Deterministic Simulation of Probabilistic Constant Depth Circuits.
Advances in Computing Research, 1989

Almost Sorting in one Round.
Advances in Computing Research, 1989

Datalog vs. First-Order Logic
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988
A lower bound for finding predecessors in Yao's call probe model.
Combinatorica, 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

The Complexity of the Pigeonhole Principle
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

Recursive Construction for 3-Regular Expanders
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 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
On optimal matchings.
Combinatorica, 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.
Combinatorica, 1983

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

Hash Functions for Priority Queues
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

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

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

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

The longest path in a random graph.
Combinatorica, 1981

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

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

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


  Loading...