| Publication | Date of Publication | Type |
|---|
| Algorithms to tile the infinite grid with finite clusters | 2025-10-29 | Paper |
| Local tests of global entanglement and a counterexample to the generalized area law | 2025-08-05 | Paper |
| Randomized greedy algorithms for the maximum matching problem with new analysis | 2025-05-05 | Paper |
Repeated averages on graphs
The Annals of Applied Probability | 2024-10-09 | Paper |
| An initial study of budgeted Steiner networks | 2023-12-16 | Paper |
| Repeated Averages on Graphs | 2022-05-09 | Paper |
| Budgeted Steiner Networks: Three Terminals with Equal Path Weights | 2022-01-27 | Paper |
On rearrangement of items stored in stacks
Algorithmic Foundations of Robotics XIV | 2021-09-20 | Paper |
| Query Complexity | 2020-03-04 | Paper |
| What do QAOA energies reveal about graphs? | 2019-12-27 | Paper |
The Moser-Tardos Resample algorithm: Where is the limit? (an experimental inquiry)
2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX) | 2019-09-12 | Paper |
Long monotone paths in line arrangements
Proceedings of the nineteenth annual symposium on Computational geometry | 2017-09-29 | Paper |
Streaming algorithms for independent sets in sparse hypergraphs
Algorithmica | 2016-10-21 | Paper |
A new line of attack on the dichotomy conjecture
European Journal of Combinatorics | 2015-12-11 | Paper |
| Impossibility Theorems and the Universal Algebraic Toolkit | 2015-06-01 | Paper |
The garden hose complexity for the equality function
Algorithmic Aspects in Information and Management | 2015-05-20 | Paper |
Locality based graph coloring
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
A new line of attack on the dichotomy conjecture
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
The DLT priority sampling is essentially optimal
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
| Quantum algorithms for the triangle problem | 2014-10-13 | Paper |
Quantum Query Complexity of State Conversion
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
| A simplified proof of a Lee-Yang type theorem | 2014-07-22 | Paper |
Moser and tardos meet Lovász
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
Digital Signatures with Minimal Overhead from Indifferentiable Random Invertible Functions
Advances in Cryptology – CRYPTO 2013 | 2013-09-02 | Paper |
Streaming and communication complexity of clique approximation
Automata, Languages, and Programming | 2013-08-12 | Paper |
The Lovász Local Lemma – A Survey
Computer Science – Theory and Applications | 2013-06-14 | Paper |
A sharper local lemma with improved applications
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
scientific article; zbMATH DE number 5899240 (Why is no real title available?)
Theory of Computing | 2011-05-24 | Paper |
Streaming Algorithms for Independent Sets
Automata, Languages and Programming | 2010-09-07 | Paper |
Quantum and classical query complexities of local search are polynomially related
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
| scientific article; zbMATH DE number 5764872 (Why is no real title available?) | 2010-08-06 | Paper |
Quantum and classical query complexities of local search are polynomially related
Algorithmica | 2009-08-31 | Paper |
Geometric representation of cubic graphs with four directions
Computational Geometry | 2009-08-14 | Paper |
Amortized Communication Complexity of Distributions
Automata, Languages and Programming | 2009-07-14 | Paper |
Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles
Random Structures & Algorithms | 2009-03-04 | Paper |
On the Variance of Subset Sum Estimation
Algorithms – ESA 2007 | 2008-09-25 | Paper |
Quantum Algorithms for the Triangle Problem
SIAM Journal on Computing | 2008-04-22 | Paper |
Parallel Repetition of the Odd Cycle Game
Lecture Notes in Computer Science | 2008-04-15 | Paper |
Product Rules in Semidefinite Programming
Fundamentals of Computation Theory | 2008-02-26 | Paper |
The quantum adversary method and classical formula size power bounds
Computational Complexity | 2007-11-05 | Paper |
Languages with Bounded Multiparty Communication Complexity
STACS 2007 | 2007-09-03 | Paper |
Computing and Combinatorics
Lecture Notes in Computer Science | 2006-01-11 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2006-01-10 | Paper |
Probabilistic Verification and Non-Approximability
Handbook of Combinatorial Optimization | 2005-09-28 | Paper |
Long monotone paths in line arrangements
Discrete & Computational Geometry | 2005-02-11 | Paper |
Proof verification and the hardness of approximation problems
Journal of the ACM | 2005-01-25 | Paper |
| scientific article; zbMATH DE number 2086255 (Why is no real title available?) | 2004-08-11 | Paper |
Computing Boolean functions from multiple faulty copies of input bits
Theoretical Computer Science | 2004-08-10 | Paper |
| scientific article; zbMATH DE number 2068119 (Why is no real title available?) | 2004-05-27 | Paper |
| scientific article; zbMATH DE number 1305526 (Why is no real title available?) | 2003-05-04 | Paper |
Tracking join and self-join sizes in limited storage
Journal of Computer and System Sciences | 2002-09-12 | Paper |
Parent-identifying codes
Journal of Combinatorial Theory. Series A | 2002-03-06 | Paper |
| scientific article; zbMATH DE number 1256636 (Why is no real title available?) | 2002-01-17 | Paper |
Efficient testing of large graphs
Combinatorica | 2001-06-13 | Paper |
Regular languages are testable with a constant number of queries
SIAM Journal on Computing | 2001-03-19 | Paper |
| scientific article; zbMATH DE number 1305443 (Why is no real title available?) | 2000-11-12 | Paper |
| scientific article; zbMATH DE number 1405671 (Why is no real title available?) | 2000-06-22 | Paper |
| scientific article; zbMATH DE number 1256775 (Why is no real title available?) | 2000-05-22 | Paper |
| scientific article; zbMATH DE number 1256715 (Why is no real title available?) | 1999-10-04 | Paper |
The space complexity of approximating the frequency moments
Journal of Computer and System Sciences | 1999-09-22 | Paper |
| scientific article; zbMATH DE number 1305544 (Why is no real title available?) | 1999-09-15 | Paper |
| scientific article; zbMATH DE number 1305522 (Why is no real title available?) | 1999-06-17 | Paper |
Large sets of nearly orthogonal vectors
Graphs and Combinatorics | 1999-05-11 | Paper |
On Conway's thrackle conjecture
Discrete & Computational Geometry | 1998-03-11 | Paper |
Interactive proofs and the hardness of approximating cliques
Journal of the ACM | 1998-01-21 | Paper |
Applications of the crossing number
Algorithmica | 1996-08-12 | Paper |
| scientific article; zbMATH DE number 742967 (Why is no real title available?) | 1995-04-11 | Paper |
On the degree of Boolean functions as real polynomials
Computational Complexity | 1995-04-06 | Paper |
| scientific article; zbMATH DE number 549860 (Why is no real title available?) | 1994-12-08 | Paper |
| scientific article; zbMATH DE number 697824 (Why is no real title available?) | 1994-11-30 | Paper |
Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC
Journal of Computer and System Sciences | 1994-09-11 | Paper |
Lower bounds for on-line graph coloring
Theoretical Computer Science | 1994-08-29 | Paper |
Local Expansion of Symmetrical Graphs
Combinatorics, Probability and Computing | 1994-07-14 | Paper |
Threshold circuits of bounded depth
Journal of Computer and System Sciences | 1993-06-29 | Paper |
On the power of two-local random reductions
Information Processing Letters | 1993-05-16 | Paper |
On packing bipartite graphs
Combinatorica | 1993-01-17 | Paper |
Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
Journal of Computer and System Sciences | 1993-01-17 | Paper |
| scientific article; zbMATH DE number 65708 (Why is no real title available?) | 1992-09-27 | Paper |
| scientific article; zbMATH DE number 4115191 (Why is no real title available?) | 1988-01-01 | Paper |
a(mod p) ≤b(mod p) for all Primes p Implies a = b
The American Mathematical Monthly | 1987-01-01 | Paper |
The solution of Graham's greatest common divisor problem
Combinatorica | 1986-01-01 | Paper |
| scientific article; zbMATH DE number 3908449 (Why is no real title available?) | 1984-01-01 | Paper |
| scientific article; zbMATH DE number 3910097 (Why is no real title available?) | 1984-01-01 | Paper |
| scientific article; zbMATH DE number 3904909 (Why is no real title available?) | 1984-01-01 | Paper |
