2022
The White-Box Adversarial Data Stream Model.
Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022
2016
Sorting and Selection with Imprecise Comparisons.
ACM Trans. Algorithms, 2016
2013
Lower Bounds for RAMs and Quantifier Elimination.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 2011
Secure Computation with Information Leaking to an Adversary.
Electron. Colloquium Comput. Complex., 2011
2010
Oblivious RAMs without Cryptographic Assumptions.
Electron. Colloquium Comput. Complex., 2010
Oblivious RAMs without cryptogrpahic assumptions.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010
2008
Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem.
Theory Comput., 2008
Representing Hard Lattices with O(nlog n) Bits.
Chic. J. Theor. Comput. Sci., 2008
2007
The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence..
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 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, 2002
Sampling Short Lattice Vectors and the Closest Lattice Vector Problem.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002
2001
Improved Algorithms and Analysis for Secretary Problems and Generalizations.
SIAM J. Discret. Math., 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
Electron. Colloquium Comput. Complex., 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
1998
Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions
Electron. Colloquium Comput. Complex., 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 <i>L<sub>2</sub></i> is <i>NP</i>-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 L<sub>2</sub> is NP-hard for Randomized Reductions.
Electron. Colloquium Comput. Complex., 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
Electron. Colloquium Comput. Complex., 1996
Generating Hard Instances of Lattice Problems
Electron. Colloquium Comput. Complex., 1996
Generating Hard Instances of Lattice Problems (Extended Abstract).
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996
1994
Datalog vs First-Order Logic.
J. Comput. Syst. Sci., 1994
Symmetric Systems of Linear Equations modulo p.
Electron. Colloquium Comput. Complex., 1994
The Independence of the modulo p Counting Principles
Electron. Colloquium Comput. Complex., 1994
The Complexity of the Pigeonhole Principle.
Comb., 1994
Recursive Construction for 3-Regular Expanders.
Comb., 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.
Comb., 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
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. Discret. 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. Log., 1989
Deterministic Simulation of Probabilistic Constant Depth Circuits.
Adv. Comput. Res., 1989
Almost Sorting in one Round.
Adv. Comput. Res., 1989
1988
A lower bound for finding predecessors in Yao's call probe model.
Comb., 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
1987
Monotone versus positive.
J. ACM, 1987
Deterministic Simulation in LOGSPACE
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 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
Hash Functions for Priority Queues
Inf. Control., December, 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.
Comb., 1983
∑<sup>1</sup><sub>1</sub>-Formulae on finite structures.
Ann. Pure Appl. Log., 1983
An O(n log n) Sorting Network
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983
1982
Extremal Uncrowded Hypergraphs.
J. Comb. Theory A, 1982
Largest random component of a k-cube.
Comb., 1982
1981
A Dense Infinite Sidon Sequence.
Eur. J. Comb., 1981
The longest path in a random graph.
Comb., 1981
On Turáns theorem for sparse graphs.
Comb., 1981
1980
A Note on Ramsey Numbers.
J. Comb. Theory A, 1980
1978
There is no Fast Single Hashing Algorithm.
Inf. Process. Lett., 1978