Miklós Ajtai - RankMe

93 papers A* 38A 1B 1C 1Journal 49Unranked 3

Year	Rank	Type	Title / Venue / Authors
2022	A*	`conf`	The White-Box Adversarial Data Stream Model. PODS Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou
2022	J	`jnl`	The White-Box Adversarial Data Stream Model. CoRR Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou
2016	J	`jnl`	Sorting and Selection with Imprecise Comparisons. ACM Trans. Algorithms Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson
2015	J	`jnl`	Sorting and Selection with Imprecise Comparisons. CoRR Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson
2013	J	`jnl`	Lower Bounds for RAMs and Quantifier Elimination. CoRR Miklós Ajtai
2013	J	`jnl`	Lower Bounds for RAMs and Quantifier Elimination. Electron. Colloquium Comput. Complex. Miklós Ajtai
2013	A*	`conf`	Lower bounds for RAMs and quantifier elimination. STOC Miklós Ajtai
2012	A*	`conf`	Determinism versus nondeterminism with arithmetic tests and computation: extended abstract. STOC Miklós Ajtai
2011	J	`jnl`	Determinism Versus Nondeterminism with Arithmetic Tests and Computation. Electron. Colloquium Comput. Complex. Miklós Ajtai
2011	J	`jnl`	Secure Computation with Information Leaking to an Adversary. Electron. Colloquium Comput. Complex. Miklós Ajtai
2011	A*	`conf`	Secure computation with information leaking to an adversary. STOC Miklós Ajtai
2010	J	`jnl`	Oblivious RAMs without Cryptographic Assumptions. Electron. Colloquium Comput. Complex. Miklós Ajtai
2010	A*	`conf`	Oblivious RAMs without cryptogrpahic assumptions. STOC Miklós Ajtai
2009	—	`conf`	Sorting and Selection with Imprecise Comparisons. ICALP (1) Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson
2008	J	`jnl`	Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem. Theory Comput. Miklós Ajtai
2008	J	`jnl`	Representing Hard Lattices with O(nlog n) Bits. Chic. J. Theor. Comput. Sci. Miklós Ajtai
2007	C	`conf`	Generalizations of the Compactness Theorem and Gödel's Completeness Theorem for Nonstandard Finite Structures. TAMC Miklós Ajtai
2007	J	`jnl`	The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.. Electron. Colloquium Comput. Complex. Miklós Ajtai, Cynthia Dwork
2006	B	`conf`	An Architecture for Provably Secure Computation. LATIN Miklós Ajtai, Cynthia Dwork, Larry J. Stockmeyer
2005	J	`jnl`	A Non-linear Time Lower Bound for Boolean Branching Programs. Theory Comput. Miklós Ajtai
2005	A*	`conf`	Representing hard lattices with O(n log n) bits. STOC Miklós Ajtai
2004	A*	`conf`	A conjecture about polynomial time computable lattice-lattice functions. STOC Miklós Ajtai
2003	A*	`conf`	The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice. STOC Miklós Ajtai
2002	J	`jnl`	A conjectured 0-1 law about the polynomial time computable properties of random lattices, I. Electron. Colloquium Comput. Complex. Miklós Ajtai
2002	A*	`conf`	Approximate counting of inversions in a data stream. STOC Miklós Ajtai, T. S. Jayram, Ravi Kumar, D. Sivakumar
2002	J	`jnl`	Compactly encoding unstructured inputs with differential compression. J. ACM Miklós Ajtai, Randal C. Burns, Ronald Fagin, Darrell D. E. Long, Larry J. Stockmeyer
2002	J	`jnl`	Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions. J. Comput. Syst. Sci. Miklós Ajtai
2002	A*	`conf`	Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties. FOCS Miklós Ajtai
2002	A	`conf`	Sampling Short Lattice Vectors and the Closest Lattice Vector Problem. CCC Miklós Ajtai, Ravi Kumar, D. Sivakumar
2002	A*	`conf`	The invasiveness of off-line memory checking. STOC Miklós Ajtai
2001	A*	`conf`	A sieve algorithm for the shortest lattice vector problem. STOC Miklós Ajtai, Ravi Kumar, D. Sivakumar
2001	—	`conf`	An Overview of the Sieve Algorithm for the Shortest Lattice Vector Problem. CaLC Miklós Ajtai, Ravi Kumar, D. Sivakumar
2001	J	`jnl`	Improved Algorithms and Analysis for Secretary Problems and Generalizations. SIAM J. Discret. Math. Miklós Ajtai, Nimrod Megiddo, Orli Waarts
2000	J	`jnl`	The Closure of Monadic NP. J. Comput. Syst. Sci. Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer
1999	J	`jnl`	A Non-linear Time Lower Bound for Boolean Branching Programs Electron. Colloquium Comput. Complex. Miklós Ajtai
1999	A*	`conf`	A Non-linear Time Lower Bound for Boolean Branching Programs. FOCS Miklós Ajtai
1999	A*	`conf`	Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract). STOC Miklós Ajtai
1999	A*	`conf`	Generating Hard Instances of the Short Basis Problem. ICALP Miklós Ajtai
1998	J	`jnl`	Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions Electron. Colloquium Comput. Complex. Miklós Ajtai
1998	J	`jnl`	Fairness in Scheduling J. Algorithms Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts
1998	A*	`conf`	The Closure of Monadic NP (Extended Abstract). STOC Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer
1998	A*	`conf`	The Shortest Vector Problem in STOC Miklós Ajtai
1997	A*	`conf`	A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. STOC Miklós Ajtai, Cynthia Dwork
1997	J	`jnl`	The Shortest Vector Problem in L Electron. Colloquium Comput. Complex. Miklós Ajtai
1996	J	`jnl`	A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimensions. SIAM J. Comput. Miklós Ajtai, Nimrod Megiddo
1996	J	`jnl`	A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence Electron. Colloquium Comput. Complex. Miklós Ajtai, Cynthia Dwork
1996	J	`jnl`	Generating Hard Instances of Lattice Problems Electron. Colloquium Comput. Complex. Miklós Ajtai
1996	A*	`conf`	Generating Hard Instances of Lattice Problems (Extended Abstract). STOC Miklós Ajtai
1995	A*	`conf`	Fairness in Scheduling. SODA Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts
1995	A*	`conf`	Improved Algorithms and Analysis for Secretary Problems and Generalizations. FOCS Miklós Ajtai, Nimrod Megiddo, Orli Waarts
1994	A*	`conf`	A Theory of Competitive Analysis for Distributed Algorithms FOCS Miklós Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts
1994	A*	`conf`	Competitiveness in Distributed Algorithms. PODC Miklós Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts
1994	J	`jnl`	Datalog vs First-Order Logic. J. Comput. Syst. Sci. Miklós Ajtai, Yuri Gurevich
1994	J	`jnl`	Recursive Construction for 3-Regular Expanders. Comb. Miklós Ajtai
1994	J	`jnl`	Symmetric Systems of Linear Equations modulo p. Electron. Colloquium Comput. Complex. Miklós Ajtai
1994	J	`jnl`	The Complexity of the Pigeonhole Principle. Comb. Miklós Ajtai
1994	J	`jnl`	The Independence of the modulo p Counting Principles Electron. Colloquium Comput. Complex. Miklós Ajtai
1994	A*	`conf`	The independence of the modulo STOC Miklós Ajtai
1993	J	`jnl`	The influence of large coalitions. Comb. Miklós Ajtai, Nathan Linial
1992	A*	`conf`	A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension STOC Miklós Ajtai, Nimrod Megiddo
1992	A*	`conf`	Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths FOCS Miklós Ajtai, Noga Alon, Jehoshua Bruck, Robert Cypher, Ching-Tien Ho, Moni Naor, Endre Szemerédi
1992	A*	`conf`	Halvers and Expanders FOCS Miklós Ajtai, János Komlós, Endre Szemerédi
1990	—	`conf`	Approximate Counting with Uniform Constant-Depth Circuits. Advances In Computational Complexity Theory Miklós Ajtai
1990	J	`jnl`	Reachability Is Harder for Directed than for Undirected Finite Graphs. J. Symb. Log. Miklós Ajtai, Ronald Fagin
1989	J	`jnl`	Almost Sorting in one Round. Adv. Comput. Res. Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi
1989	A*	`conf`	Datalog vs. First-Order Logic FOCS Miklós Ajtai, Yuri Gurevich
1989	J	`jnl`	Deterministic Simulation of Probabilistic Constant Depth Circuits. Adv. Comput. Res. Miklós Ajtai, Avi Wigderson
1989	J	`jnl`	First-Order Definability on Finite Structures. Ann. Pure Appl. Log. Miklós Ajtai
1989	J	`jnl`	Optimal Parallel Selection has Complexity O(Log Log n). J. Comput. Syst. Sci. Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi
1989	J	`jnl`	Sorting in Average Time o(log) n. SIAM J. Discret. Math. Miklós Ajtai, D. Karabeg, János Komlós, Endre Szemerédi
1988	J	`jnl`	A lower bound for finding predecessors in Yao's call probe model. Comb. Miklós Ajtai
1988	A*	`conf`	Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version) FOCS Miklós Ajtai, Ronald Fagin
1988	A*	`conf`	The Complexity of the Pigeonhole Principle FOCS Miklós Ajtai
1987	A*	`conf`	Deterministic Simulation in LOGSPACE STOC Miklós Ajtai, János Komlós, Endre Szemerédi
1987	J	`jnl`	Monotone versus positive. J. ACM Miklós Ajtai, Yuri Gurevich
1987	A*	`conf`	Recursive Construction for 3-Regular Expanders FOCS Miklós Ajtai
1986	A*	`conf`	Deterministic Selection in O(log log N) Parallel Time STOC Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi
1986	A*	`conf`	Two lower bounds for branching programs STOC 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
1985	A*	`conf`	Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version) FOCS Miklós Ajtai, Avi Wigderson
1984	A*	`conf`	A Theorem on Probabilistic Constant Depth Computations STOC Miklós Ajtai, Michael Ben-Or
1984	J	`jnl`	Hash Functions for Priority Queues Inf. Control. Miklós Ajtai, Michael L. Fredman, János Komlós
1984	J	`jnl`	On optimal matchings. Comb. Miklós Ajtai, János Komlós, Gábor E. Tusnády
1983	A*	`conf`	An O(n log n) Sorting Network STOC Miklós Ajtai, János Komlós, Endre Szemerédi
1983	A*	`conf`	Hash Functions for Priority Queues FOCS Miklós Ajtai, Michael L. Fredman, János Komlós
1983	J	`jnl`	Sorting in c log n parallel sets. Comb. Miklós Ajtai, János Komlós, Endre Szemerédi
1983	J	`jnl`	∑ Ann. Pure Appl. Log. Miklós Ajtai
1982	J	`jnl`	Extremal Uncrowded Hypergraphs. J. Comb. Theory A Miklós Ajtai, János Komlós, Janos Pintz, Joel Spencer, Endre Szemerédi
1982	J	`jnl`	Largest random component of a k-cube. Comb. Miklós Ajtai, János Komlós, Endre Szemerédi
1981	J	`jnl`	A Dense Infinite Sidon Sequence. Eur. J. Comb. Miklós Ajtai, János Komlós, Endre Szemerédi
1981	J	`jnl`	On Turáns theorem for sparse graphs. Comb. Miklós Ajtai, Paul Erdös, János Komlós, Endre Szemerédi
1981	J	`jnl`	The longest path in a random graph. Comb. Miklós Ajtai, János Komlós, Endre Szemerédi
1980	J	`jnl`	A Note on Ramsey Numbers. J. Comb. Theory A Miklós Ajtai, János Komlós, Endre Szemerédi
1978	J	`jnl`	There is no Fast Single Hashing Algorithm. Inf. Process. Lett. Miklós Ajtai, János Komlós, Endre Szemerédi