| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Miklós Ajtai |
Determinism versus nondeterminism with arithmetic tests and computation: extended abstract.  |
STOC  |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
Secure Computation with Information Leaking to an Adversary. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Miklós Ajtai |
Determinism Versus Nondeterminism with Arithmetic Tests and Computation. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Miklós Ajtai |
Secure computation with information leaking to an adversary. |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
Oblivious RAMs without Cryptographic Assumptions. |
Electronic Colloquium on Computational Complexity (ECCC) |
2010 |
DBLP BibTeX RDF |
|
| 1 | Miklós Ajtai |
Oblivious RAMs without cryptogrpahic assumptions. |
STOC |
2010 |
DBLP DOI BibTeX RDF |
RAM, oblivious |
| 1 | Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, Jelani Nelson |
Sorting and Selection with Imprecise Comparisons. |
ICALP |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
Representing Hard Lattices with O(nlog n) Bits. |
Chicago J. Theor. Comput. Sci. |
2008 |
DBLP BibTeX RDF |
|
| 1 | Miklós Ajtai |
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 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Cynthia Dwork |
The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.. |
Electronic Colloquium on Computational Complexity (ECCC) |
2007 |
DBLP BibTeX RDF |
|
| 1 | Miklós Ajtai |
Generalizations of the Compactness Theorem and Gödel's Completeness Theorem for Nonstandard Finite Structures. |
TAMC |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Cynthia Dwork, Larry J. Stockmeyer |
An Architecture for Provably Secure Computation. |
LATIN |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
A Non-linear Time Lower Bound for Boolean Branching Programs. |
Theory of Computing |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
Representing hard lattices with O(n log n) bits. |
STOC |
2005 |
DBLP DOI BibTeX RDF |
algorithm, lattice, public-key cryptosystem |
| 1 | Miklós Ajtai |
A conjecture about polynomial time computable lattice-lattice functions. |
STOC |
2004 |
DBLP DOI BibTeX RDF |
axiom of choice, algorithm, lattice |
| 1 | Miklós Ajtai |
The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice. |
STOC |
2003 |
DBLP DOI BibTeX RDF |
algorithm, lattice, basis |
| 1 | Miklós Ajtai |
A conjectured 0-1 law about the polynomial time computable properties of random lattices, I. |
Electronic Colloquium on Computational Complexity (ECCC) |
2002 |
DBLP BibTeX RDF |
|
| 1 | Miklós Ajtai, Randal C. Burns, Ronald Fagin, Darrell D. E. Long, Larry J. Stockmeyer |
Compactly encoding unstructured inputs with differential compression. |
J. ACM |
2002 |
DBLP DOI BibTeX RDF |
Delta compression, differential compression, differencing |
| 1 | Miklós Ajtai |
Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions. |
J. Comput. Syst. Sci. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties. |
FOCS |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Ravi Kumar, D. Sivakumar |
Sampling Short Lattice Vectors and the Closest Lattice Vector Problem. (PDF / PS) |
IEEE Conference on Computational Complexity |
2002 |
DBLP DOI BibTeX RDF |
SVP, CVP, Lattice, shortest vector problem, closest vector problem |
| 1 | Miklós Ajtai |
The invasiveness of off-line memory checking. |
STOC |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, T. S. Jayram, Ravi Kumar, D. Sivakumar |
Approximate counting of inversions in a data stream. |
STOC |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Nimrod Megiddo, Orli Waarts |
Improved Algorithms and Analysis for Secretary Problems and Generalizations. |
SIAM J. Discrete Math. |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Ravi Kumar, D. Sivakumar |
An Overview of the Sieve Algorithm for the Shortest Lattice Vector Problem. |
CaLC |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Ravi Kumar, D. Sivakumar |
A sieve algorithm for the shortest lattice vector problem. |
STOC |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer |
The Closure of Monadic NP. |
J. Comput. Syst. Sci. |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
A Non-linear Time Lower Bound for Boolean Branching Programs |
Electronic Colloquium on Computational Complexity (ECCC) |
1999 |
DBLP BibTeX RDF |
|
| 1 | Miklós Ajtai |
Generating Hard Instances of the Short Basis Problem. |
ICALP |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
A Non-linear Time Lower Bound for Boolean Branching Programs. |
FOCS |
1999 |
DBLP DOI BibTeX RDF |
Hankel matrix, lower bound, branching program |
| 1 | Miklós Ajtai |
Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract). |
STOC |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions |
Electronic Colloquium on Computational Complexity (ECCC) |
1998 |
DBLP BibTeX RDF |
|
| 1 | Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts |
Fairness in Scheduling |
J. Algorithms |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Ronald Fagin, Larry J. Stockmeyer |
The Closure of Monadic NP (Extended Abstract). |
STOC |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions (Extended Abstract). |
STOC |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions. |
Electronic Colloquium on Computational Complexity (ECCC) |
1997 |
DBLP BibTeX RDF |
|
| 1 | Miklós Ajtai, Cynthia Dwork |
A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. |
STOC |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Cynthia Dwork |
A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence |
Electronic Colloquium on Computational Complexity (ECCC) |
1996 |
DBLP BibTeX RDF |
|
| 1 | Miklós Ajtai |
Generating Hard Instances of Lattice Problems |
Electronic Colloquium on Computational Complexity (ECCC) |
1996 |
DBLP BibTeX RDF |
|
| 1 | Miklós Ajtai, Nimrod Megiddo |
A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimensions. |
SIAM J. Comput. |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
Generating Hard Instances of Lattice Problems (Extended Abstract). |
STOC |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, Orli Waarts |
Fairness in Scheduling. |
SODA |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Nimrod Megiddo, Orli Waarts |
Improved Algorithms and Analysis for Secretary Problems and Generalizations. |
FOCS |
1995 |
DBLP DOI BibTeX RDF |
secretary problems, random order, expected sum, zth powers, expected rank, lower bound, probability, probability, generalizations, optimal algorithms, operations research, large data set |
| 1 | Miklós Ajtai |
The Independence of the modulo p Counting Principles |
Electronic Colloquium on Computational Complexity (ECCC) |
1994 |
DBLP BibTeX RDF |
|
| 1 | Miklós Ajtai |
Symmetric Systems of Linear Equations modulo p. |
Electronic Colloquium on Computational Complexity (ECCC) |
1994 |
DBLP BibTeX RDF |
|
| 1 | Miklós Ajtai |
Recursive Construction for 3-Regular Expanders. |
Combinatorica |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
The Complexity of the Pigeonhole Principle. |
Combinatorica |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Yuri Gurevich |
Datalog vs First-Order Logic. |
J. Comput. Syst. Sci. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts |
Competitiveness in Distributed Algorithms. |
PODC |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, James Aspnes, Cynthia Dwork, Orli Waarts |
A Theory of Competitive Analysis for Distributed Algorithms |
FOCS |
1994 |
DBLP DOI BibTeX RDF |
distributed on-line algorithm, optimal global-control algorithm, distributed algorithms, data management, competitive analysis, competitiveness, job scheduling |
| 1 | Miklós Ajtai, Nathan Linial |
The influence of large coalitions. |
Combinatorica |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Noga Alon, Jehoshua Bruck, Robert Cypher, Ching-Tien Ho, Moni Naor, Endre Szemerédi |
Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths |
FOCS |
1992 |
DBLP DOI BibTeX RDF |
k-fault tolerant graph, performance degradation, disjoint paths, perfect hash functions |
| 1 | Miklós Ajtai, János Komlós, Endre Szemerédi |
Halvers and Expanders |
FOCS |
1992 |
DBLP DOI BibTeX RDF |
k-sorter switches, comparator switch, asymptotic efficiency, combinatorial networks, halvers, parallel algorithms, building blocks, expanders, combinatorial circuits |
| 1 | Miklós Ajtai, Nimrod Megiddo |
A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension |
STOC |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Ronald Fagin |
Reachability Is Harder for Directed than for Undirected Finite Graphs. |
J. Symb. Log. |
1990 |
DBLP BibTeX RDF |
|
| 1 | Miklós Ajtai |
First-Order Definability on Finite Structures. |
Ann. Pure Appl. Logic |
1989 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, D. Karabeg, János Komlós, Endre Szemerédi |
Sorting in Average Time o(log) n. |
SIAM J. Discrete Math. |
1989 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi |
Optimal Parallel Selection has Complexity O(Log Log n). |
J. Comput. Syst. Sci. |
1989 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Yuri Gurevich |
Datalog vs. First-Order Logic |
FOCS |
1989 |
DBLP DOI BibTeX RDF |
finite structure, first-order languages, first-order expressible datalog query, compactness theorem, first-order logic, bounded |
| 1 | Miklós Ajtai |
A lower bound for finding predecessors in Yao's call probe model. |
Combinatorica |
1988 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
The Complexity of the Pigeonhole Principle |
FOCS |
1988 |
DBLP DOI BibTeX RDF |
PHP/sub n/, complexity, inference rule, Boolean formula, propositional calculus, pigeonhole principle |
| 1 | Miklós Ajtai, Ronald Fagin |
Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version) |
FOCS |
1988 |
DBLP DOI BibTeX RDF |
efficiency of algorithms, undirected finite graphs, Ehrenfeucht-Fraisse games, directed graphs, reachability |
| 1 | Miklós Ajtai, Yuri Gurevich |
Monotone versus positive. |
J. ACM |
1987 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai |
Recursive Construction for 3-Regular Expanders |
FOCS |
1987 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, János Komlós, Endre Szemerédi |
Deterministic Simulation in LOGSPACE |
STOC |
1987 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi |
Deterministic Selection in O(log log N) Parallel Time |
STOC |
1986 |
DBLP DOI BibTeX RDF |
|
| 1 | 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 |
Two lower bounds for branching programs |
STOC |
1986 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Avi Wigderson |
Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version) |
FOCS |
1985 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Michael L. Fredman, János Komlós |
Hash Functions for Priority Queues |
Information and Control |
1984 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, János Komlós, Gábor E. Tusnády |
On optimal matchings. |
Combinatorica |
1984 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Michael Ben-Or |
A Theorem on Probabilistic Constant Depth Computations |
STOC |
1984 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, János Komlós, Endre Szemerédi |
Sorting in c log n parallel sets. |
Combinatorica |
1983 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Michael L. Fredman, János Komlós |
Hash Functions for Priority Queues |
FOCS |
1983 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, János Komlós, Endre Szemerédi |
An O(n log n) Sorting Network |
STOC |
1983 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, János Komlós, Janos Pintz, Joel Spencer, Endre Szemerédi |
Extremal Uncrowded Hypergraphs. |
J. Comb. Theory, Ser. A |
1982 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, János Komlós, Endre Szemerédi |
Largest random component of a k-cube. |
Combinatorica |
1982 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, János Komlós, Endre Szemerédi |
The longest path in a random graph. |
Combinatorica |
1981 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, Paul Erdös, János Komlós, Endre Szemerédi |
On Turáns theorem for sparse graphs. |
Combinatorica |
1981 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, János Komlós, Endre Szemerédi |
A Note on Ramsey Numbers. |
J. Comb. Theory, Ser. A |
1980 |
DBLP DOI BibTeX RDF |
|
| 1 | Miklós Ajtai, János Komlós, Endre Szemerédi |
There is no Fast Single Hashing Algorithm. |
Inf. Process. Lett. |
1978 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")