John Kallaugher

Publication Activity (10 Years)

Years Active: 2016-2024
Publications (10 Years): 22

Top Topics

Polynomial Time Complexity

Graph Structure

Top Venues

Publications

John Kallaugher, Ojas Parekh, Nadezhda Voronova
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model. STOC (2024)
John Kallaugher, Ojas Parekh, Kevin Thompson, Yipu Wang, Justin Yirka
Complexity Classification of Product State Problems for Local Hamiltonians. CoRR (2024)
John Kallaugher, Ojas Parekh, Nadezhda Voronova
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model. Electron. Colloquium Comput. Complex. (2023)
John Kallaugher, Ojas Parekh, Nadezhda Voronova
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model. CoRR (2023)
John Kallaugher
A Quantum Advantage for a Natural Streaming Problem. FOCS (2022)
John Kallaugher, Ojas Parekh
The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut. CoRR (2022)
Ashish Chiplunkar, John Kallaugher, Michael Kapralov, Eric Price
Factorial Lower Bounds for (Almost) Random Order Streams. FOCS (2022)
John Kallaugher, Ojas Parekh
The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut. FOCS (2022)
John Kallaugher, Michael Kapralov, Eric Price
Simulating Random Walks in Random Streams. SODA (2022)
John Kallaugher
A Quantum Advantage for a Natural Streaming Problem. CoRR (2021)
John Kallaugher, Michael Kapralov, Eric Price
Simulating Random Walks in Random Streams. CoRR (2021)
John Kallaugher
A Quantum Advantage for a Natural Streaming Problem. FOCS (2021)
Rajesh Jayaram, John Kallaugher
An Optimal Algorithm for Triangle Counting in the Stream. APPROX-RANDOM (2021)
Rajesh Jayaram, John Kallaugher
An Optimal Algorithm for Triangle Counting. CoRR (2021)
Ashish Chiplunkar, John Kallaugher, Michael Kapralov, Eric Price
Approximating Local Graph Structure in Almost Random Order Streams. CoRR (2021)
John Kallaugher, Eric Price
Separations and equivalences between turnstile streaming and linear sketching. STOC (2020)
John Kallaugher, Andrew McGregor, Eric Price, Sofya Vorotnikova
The Complexity of Counting Cycles in the Adjacency List Streaming Model. PODS (2019)
John Kallaugher, Eric Price
Exponential Separations Between Turnstile Streaming and Linear Sketching. CoRR (2019)
John Kallaugher, Michael Kapralov, Eric Price
The Sketching Complexity of Graph and Hypergraph Counting. CoRR (2018)
John Kallaugher, Michael Kapralov, Eric Price
The Sketching Complexity of Graph and Hypergraph Counting. FOCS (2018)
John Kallaugher, Eric Price
A Hybrid Sampling Scheme for Triangle Counting. SODA (2017)
John Kallaugher, Eric Price
Improved graph sampling for triangle counting. CoRR (2016)