BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter
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 DBLP: Ajtai:Mikl=oacute=s

Contributed to:

STOC 20132013
STOC 20122012
STOC 20112011
STOC 20102010
ICALP (1) 20092009
STOC 20052005
STOC 20042004
STOC 20032003
STOC 20022002
STOC 20012001
ICALP 19991999
STOC 19991999
STOC 19981998
STOC 19971997
STOC 19961996
STOC 19921992
STOC 19871987
STOC 19861986
STOC 19841984
STOC 19831983

Wrote 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.
Secure computation with information leaking to an adversary (MA), pp. 715–724.
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.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.