| Publication | Date of Publication | Type |
|---|
Cumulative memory lower bounds for randomized and quantum computation
| 2024-11-14 | Paper |
On disperser/lifting properties of the index and inner-product functions
| 2024-09-25 | Paper |
Edge Estimation with Independent Set Oracles
ACM Transactions on Algorithms | 2023-04-26 | Paper |
Separating the power of EREW and CREW PRAMs with small communication width
Lecture Notes in Computer Science | 2023-01-18 | Paper |
Distributed computing on transitive networks: the torus
STACS 89 | 2022-08-16 | Paper |
Towards verifying nonlinear integer arithmetic
Lecture Notes in Computer Science | 2022-08-12 | Paper |
Exact model counting of query expressions. Limitations of propositional methods
ACM Transactions on Database Systems | 2021-11-25 | Paper |
Edge estimation with independent set oracles
| 2021-06-15 | Paper |
Stabbing planes
| 2021-06-15 | Paper |
On the bias of Reed-Muller codes over odd prime fields
SIAM Journal on Discrete Mathematics | 2020-06-09 | Paper |
Toward verifying nonlinear integer arithmetic
Journal of the ACM | 2020-02-11 | Paper |
Nondeterminism and an abstract formulation of Nečiporuk's lower bound method
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
Massively-Parallel Similarity Join, Edge-Isoperimetry, and Distance Correlations on the Hypercube
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Communication steps for parallel query processing
Journal of the ACM | 2018-05-17 | Paper |
Worst-case optimal algorithms for parallel query processing
| 2017-07-14 | Paper |
Optimal bounds for the predecessor problem
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
SIAM Journal on Computing | 2016-09-02 | Paper |
Time-space trade-off lower bounds for randomized computation of decision problems
Journal of the ACM | 2015-12-07 | Paper |
Finding the Median (Obliviously) with Bounded Space
Automata, Languages, and Programming | 2015-10-27 | Paper |
The value of multiple read/write streams for approximating frequency moments
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
Formula Caching in DPLL
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
Hardness amplification in proof complexity
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Multiparty Communication Complexity and Threshold Circuit Size of AC^0
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Time-space tradeoffs in resolution, superpolynomial lower bounds for superlinear space
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Multiparty communication complexity and threshold circuit size of AC\(^0\)
SIAM Journal on Computing | 2012-09-12 | Paper |
The quantum query complexity of \(\mathrm{AC}^0\)
Quantum Information \& Computation | 2012-09-05 | Paper |
Separating deterministic from randomized multiparty communication complexity
Theory of Computing | 2011-05-24 | Paper |
Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Theory and Applications of Satisfiability Testing
Lecture Notes in Computer Science | 2009-07-24 | Paper |
Longest Common Subsequences in Sets of Permutations
| 2009-04-09 | Paper |
Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
SIAM Journal on Computing | 2008-06-19 | Paper |
The resolution complexity of independent sets and vertex covers in random graphs
Computational Complexity | 2008-03-05 | Paper |
Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
Automata, Languages and Programming | 2007-11-28 | Paper |
A strong direct product theorem for corruption and the multiparty communication complexity of disjointness
Computational Complexity | 2007-11-14 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2006-01-10 | Paper |
scientific article; zbMATH DE number 2243370 (Why is no real title available?)
| 2006-01-04 | Paper |
Theory and Applications of Satisfiability Testing
Lecture Notes in Computer Science | 2005-12-15 | Paper |
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles
SIAM Journal on Computing | 2005-02-21 | Paper |
scientific article; zbMATH DE number 2134905 (Why is no real title available?)
| 2005-02-18 | Paper |
Optimal bounds for the predecessor problem and related problems
Journal of Computer and System Sciences | 2003-05-04 | Paper |
scientific article; zbMATH DE number 1775444 (Why is no real title available?)
| 2002-08-01 | Paper |
Time-space tradeoffs for branching programs
Journal of Computer and System Sciences | 2002-07-04 | Paper |
The efficiency of resolution and Davis-Putnam procedures
SIAM Journal on Computing | 2002-04-23 | Paper |
scientific article; zbMATH DE number 1263206 (Why is no real title available?)
| 2002-01-30 | Paper |
scientific article; zbMATH DE number 1630128 (Why is no real title available?)
| 2001-10-23 | Paper |
scientific article; zbMATH DE number 1860652 (Why is no real title available?)
| 2001-01-01 | Paper |
Improved depth lower bounds for small distance connectivity
Computational Complexity | 2000-10-17 | Paper |
The relative complexity of NP search problems
Journal of Computer and System Sciences | 1999-09-13 | Paper |
scientific article; zbMATH DE number 1306902 (Why is no real title available?)
| 1999-08-31 | Paper |
scientific article; zbMATH DE number 1179974 (Why is no real title available?)
| 1999-03-14 | Paper |
A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata
SIAM Journal on Computing | 1999-02-22 | Paper |
Separating the power of EREW and CREW PRAMs with small communication width
Information and Computation | 1998-06-02 | Paper |
scientific article; zbMATH DE number 1114015 (Why is no real title available?)
| 1998-02-08 | Paper |
Time-space tradeoffs for undirected graph traversal by graph automata
Information and Computation | 1997-10-13 | Paper |
Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
Proceedings of the London Mathematical Society | 1996-12-05 | Paper |
An exponential separation between the parity principle and the pigeonhole principle
Annals of Pure and Applied Logic | 1996-11-25 | Paper |
Parallel algorithms for arrangements
Algorithmica | 1996-02-20 | Paper |
scientific article; zbMATH DE number 432767 (Why is no real title available?)
| 1994-09-19 | Paper |
scientific article; zbMATH DE number 619538 (Why is no real title available?)
| 1994-09-13 | Paper |
Communication-Space Tradeoffs for Unrestricted Protocols
SIAM Journal on Computing | 1994-08-14 | Paper |
Exponential lower bounds for the pigeonhole principle
Computational Complexity | 1993-10-18 | Paper |
The complexity of computing symmetric functions using threshold circuits
Theoretical Computer Science | 1992-09-27 | Paper |
Optimal bounds for decision problems on the CRCW PRAM
Journal of the ACM | 1992-06-25 | Paper |
A general Sequential Time-Space Tradeoff for Finding Unique Elements
SIAM Journal on Computing | 1991-01-01 | Paper |
Lower bounds for recognizing small cliques on CRCW PRAM's
Discrete Applied Mathematics | 1990-01-01 | Paper |
A note on error expressions for reflected and averaged implicit Runge- Kutta methods
BIT | 1989-01-01 | Paper |
Limits on the power of concurrent-write parallel machines
Information and Computation | 1988-01-01 | Paper |
Log Depth Circuits for Division and Related Problems
SIAM Journal on Computing | 1986-01-01 | Paper |
