John Kallaugher

According to our database, John Kallaugher authored at least 17 papers between 2016 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of four.

2025

Hamiltonian Locality Testing via Trotterized Postselection.

John Kallaugher, Daniel Liang

Proceedings of the 20th Conference on the Theory of Quantum Computation, 2025

How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing.

Ojas Parekh, John Kallaugher, Nadezhda Voronova

Proceedings of the 2025 Symposium on Simplicity in Algorithms, 2025

Complexity Classification of Product State Problems for Local Hamiltonians.

John Kallaugher, Ojas Parekh, Kevin Thompson, Yipu Wang, Justin Yirka

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

2024

Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model.

John Kallaugher, Ojas Parekh, Nadezhda Voronova

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2022

Simulating Random Walks in Random Streams.

John Kallaugher, Michael Kapralov, Eric Price

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

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

John Kallaugher, Ojas Parekh

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Factorial Lower Bounds for (Almost) Random Order Streams.

Ashish Chiplunkar, John Kallaugher, Michael Kapralov, Eric Price

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Approximating Local Graph Structure in Almost Random Order Streams.

Ashish Chiplunkar, John Kallaugher, Michael Kapralov, Eric Price

CoRR, 2021

An Optimal Algorithm for Triangle Counting.

Rajesh Jayaram, John Kallaugher

CoRR, 2021

A Quantum Advantage for a Natural Streaming Problem.

John Kallaugher

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

An Optimal Algorithm for Triangle Counting in the Stream.

Rajesh Jayaram, John Kallaugher

Proceedings of the Approximation, 2021

2020

Separations and equivalences between turnstile streaming and linear sketching.

John Kallaugher, Eric Price

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

Exponential Separations Between Turnstile Streaming and Linear Sketching.

John Kallaugher, Eric Price

CoRR, 2019

The Complexity of Counting Cycles in the Adjacency List Streaming Model.

John Kallaugher, Andrew McGregor, Eric Price, Sofya Vorotnikova

Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

2018

The Sketching Complexity of Graph and Hypergraph Counting.

John Kallaugher, Michael Kapralov, Eric Price

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

A Hybrid Sampling Scheme for Triangle Counting.

John Kallaugher, Eric Price

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

Improved graph sampling for triangle counting.

John Kallaugher, Eric Price

CoRR, 2016