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