John Kallaugher

According to our database, John Kallaugher authored at least 15 papers between 2016 and 2024.

Collaborative distances:

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

2024

Complexity Classification of Product State Problems for Local Hamiltonians.

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

CoRR, 2024

2023

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

John Kallaugher, Ojas Parekh, Nadezhda Voronova

Electron. Colloquium Comput. Complex., 2023

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