291 citations · 445 across the 25 of their papers we have counts for
29 papers
A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds
Paul Beame, Blake Holman, Niels Kornerup
Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeo…
Strong Selective and List-Decoding Direct Product Theorems for Quantum Query Complexity
Paul Beame, Niels Kornerup, Michael Whitmeyer
Quantum strong direct-product theorems for specific functions have been known for nearly two decades. These have been extended to general results for function computation and state…
Extending CDCL to disjunctions of parity equations
Paul Beame, Glenn Sun
Because CDCL produces proofs in the Resolution proof system, problems provably hard for Resolution are also provably hard for CDCL. Exponentially shorter proofs can sometimes be fo…
Multiparty Communication Complexity of Collision Finding
Paul Beame, Michael Whitmeyer
We prove an lower bound on the -party number-in-hand communication complexity of collision-finding. This implies a lower bound on t…
Quantum Time-Space Tradeoffs for Matrix Problems
Paul Beame, Niels Kornerup, Michael Whitmeyer
We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior wor…
Cumulative Memory Lower Bounds for Randomized and Quantum Computation
Paul Beame, Niels Kornerup
Cumulative memory -- the sum of space used per step over the duration of a computation -- is a fine-grained measure of time-space complexity that was introduced to analyze cryptogr…