3 papers
cs.CC2026
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…
cs.CC2024
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…
cs.CC2024
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…