P. Beame

activity

20092026

most citedTowards Understanding and Harnessing the Potential of Clause Learning

291 citations · 445 across the 25 of their papers we have counts for

collaborators

Showing 2024 · cs.CCShow all

2 papers · 2 filters

cs.CC2024

Multiparty Communication Complexity of Collision Finding

Paul Beame, Michael Whitmeyer

We prove an $Ω (n^{1 - 1/ k} lo g k / 2^{k})$ lower bound on the $k$ -party number-in-hand communication complexity of collision-finding. This implies a $2^{n^{1 - o (1)}}$ 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…