Michael Whitmeyer

collaborators

Showing cs.CCShow all

2 papers · 1 filter

cs.CC2026

Multiparty Communication Complexity of Collision Finding

Paul Beame, Michael Whitmeyer

We prove an $I^c ◯ (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…

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…