Travelled to:1 × Czech Republic
15 × USA
2 × Canada
2 × Greece
Collaborated with:∅ J.Komlós E.Szemerédi R.Kumar D.Sivakumar C.Dwork N.Megiddo M.Ben-Or R.Fagin L.J.Stockmeyer V.Feldman A.Hassidim J.Nelson T.S.Jayram W.L.Steiger L.Babai P.Hajnal P.Pudlák V.Rödl G.Turán
Talks about:lattic (6) log (6) problem (4) comput (4) time (4) hard (4) determinist (3) algorithm (3) shortest (3) determin (3)
Person: Miklós Ajtai
DBLP: Ajtai:Mikl=oacute=s
Contributed to:
2013201220112010
2009200520042003200220011999199919981997199619921987198619841983Wrote 23 papers:
- STOC-2013-Ajtai #bound #quantifier
- Lower bounds for RAMs and quantifier elimination (MA), pp. 803–812.
- STOC-2012-Ajtai #nondeterminism #testing
- Determinism versus nondeterminism with arithmetic tests and computation: extended abstract (MA), pp. 249–268.
- STOC-2011-Ajtai
- Secure computation with information leaking to an adversary (MA), pp. 715–724.
- STOC-2010-Ajtai
- Oblivious RAMs without cryptogrpahic assumptions (MA), pp. 181–190.
- ICALP-v1-2009-AjtaiFHN #sorting
- Sorting and Selection with Imprecise Comparisons (MA, VF, AH, JN), pp. 37–48.
- STOC-2005-Ajtai #representation
- Representing hard lattices with O(n log n) bits (MA), pp. 94–103.
- STOC-2004-Ajtai #polynomial
- A conjecture about polynomial time computable lattice-lattice functions (MA), pp. 486–493.
- STOC-2003-Ajtai #algorithm #approximate #behaviour #worst-case
- The worst-case behavior of schnorr’s algorithm approximating the shortest nonzero vector in a lattice (MA), pp. 396–406.
- STOC-2002-Ajtai #memory management
- The invasiveness of off-line memory checking (MA), pp. 504–513.
- STOC-2002-AjtaiJKS #approximate #data type
- Approximate counting of inversions in a data stream (MA, TSJ, RK, DS), pp. 370–379.
- STOC-2001-AjtaiKS #algorithm #problem
- A sieve algorithm for the shortest lattice vector problem (MA, RK, DS), pp. 601–610.
- ICALP-1999-Ajtai #generative #problem
- Generating Hard Instances of the Short Basis Problem (MA), pp. 1–9.
- STOC-1999-Ajtai #linear #nondeterminism
- Determinism versus Non-Determinism for Linear Time RAMs (MA), pp. 632–641.
- STOC-1998-Ajtai #np-hard #problem #random #reduction
- The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions (MA), pp. 10–19.
- STOC-1998-AjtaiFS #monad
- The Closure of Monadic NP (MA, RF, LJS), pp. 309–318.
- STOC-1997-AjtaiD #equivalence #worst-case
- A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence (MA, CD), pp. 284–293.
- STOC-1996-Ajtai #generative #problem
- Generating Hard Instances of Lattice Problems (MA), pp. 99–108.
- STOC-1992-AjtaiM #algorithm #linear #programming
- A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension (MA, NM), pp. 327–338.
- STOC-1987-AjtaiKS #simulation
- Deterministic Simulation in LOGSPACE (MA, JK, ES), pp. 132–140.
- STOC-1986-AjtaiBHKPRST #bound #branch #source code
- Two lower bounds for branching programs (MA, LB, PH, JK, PP, VR, ES, GT), pp. 30–38.
- STOC-1986-AjtaiKSS #parallel
- Deterministic Selection in O(log log N) Parallel Time (MA, JK, WLS, ES), pp. 188–195.
- STOC-1984-AjtaiB #constant #probability #theorem
- A Theorem on Probabilistic Constant Depth Computations (MA, MBO), pp. 471–474.
- STOC-1983-AjtaiKS #network #sorting
- An O(n log n) Sorting Network (MA, JK, ES), pp. 1–9.