John Kallaugher

Separations and equivalences between turnstile streaming and linear sketching

2020

A longstanding observation, which was partially proven by Li, Nguyen, and Woodruff in 2014, and extended by Ai, Hu, Li, and Woodruff in 2016, is that any turnstile streaming algorithm can be implemented as a …

The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut

2022 · arXiv (Cornell University)

We investigate the space complexity of two graph streaming problems: Max-Cut and its quantum analogue, Quantum Max-Cut. Previous work by Kapralov and Krachun [STOC `19] resolved the classical complexity of the \emph{classical} problem, showing that …