John Kallaugher, Daniel Liang
Hamiltonian Locality Testing via Trotterized Postselection https://arxiv.org/abs/2505.06478
TQC 2025John Kallaugher, Ojas Parekh, Nadezhda Voronova
How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing https://arxiv.org/abs/2410.18922
SOSA 2025John Kallaugher, Ojas Parekh, Kevin Thompson, Yipu Wang, Justin Yirka
Complexity Classification of Product State Problems for Local Hamiltonians https://arxiv.org/abs/2401.06725
ITCS 2025John Kallaugher, Ojas Parekh, Nadezhda Voronova
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model https://arxiv.org/abs/2311.14123
STOC 2024John Kallaugher, Ojas Parekh
The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut https://arxiv.org/abs/2206.00213
FOCS 2022Ashish Chiplunkar, John Kallaugher, Michael Kapralov, Eric Price
Factorial Lower Bounds for (Almost) Random Order Streams https://arxiv.org/abs/2110.10091
FOCS 2022John Kallaugher, Michael Kapralov, Eric Price
Simulating Random Walks in Random Streams https://arxiv.org/abs/2112.07532
SODA 2022John Kallaugher
A Quantum Advantage for a Natural Streaming Problem https://arxiv.org/abs/2106.04633
FOCS 2021Rajesh Jayaram, John Kallaugher
An Optimal Algorithm for Triangle Counting in the Stream https://arxiv.org/abs/2105.01785
APPROX 2021John Kallaugher, Eric Price
Separations and Equivalences between Turnstile Streaming and Linear Sketching https://arxiv.org/abs/1905.02358
STOC 2020John Kallaugher, Andrew McGregor, Eric Price, Sofya Vorotnikova
The Complexity of Counting Cycles in the Adjacency List Streaming Model https://dl.acm.org/doi/10.1145/3294052.3319706
PODS 2019John Kallaugher, Michael Kapralov, Eric Price
The Sketching Complexity of Graph and Hypergraph Counting https://arxiv.org/abs/1808.04995
FOCS 2018John Kallaugher, Eric Price
A Hybrid Sampling Scheme for Triangle Counting https://arxiv.org/abs/1610.02066
SODA 2017