John Kallaugher

26 papers A* 9A 1Journal 13Unranked 3

Year	Rank	Type	Title / Venue / Authors
2025	A	`conf`	Complexity Classification of Product State Problems for Local Hamiltonians. ITCS John Kallaugher, Ojas Parekh, Kevin Thompson, Yipu Wang, Justin Yirka
2025	—	`conf`	Hamiltonian Locality Testing via Trotterized Postselection. TQC John Kallaugher, Daniel Liang
2025	J	`jnl`	Hamiltonian Locality Testing via Trotterized Postselection. CoRR John Kallaugher, Daniel Liang
2025	—	`conf`	How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing. SOSA Ojas Parekh, John Kallaugher, Nadezhda Voronova
2024	J	`jnl`	Complexity Classification of Product State Problems for Local Hamiltonians. CoRR John Kallaugher, Ojas Parekh, Kevin Thompson, Yipu Wang, Justin Yirka
2024	A*	`conf`	Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model. STOC John Kallaugher, Ojas Parekh, Nadezhda Voronova
2024	J	`jnl`	How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing. CoRR John Kallaugher, Ojas Parekh, Nadezhda Voronova
2023	J	`jnl`	Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model. CoRR John Kallaugher, Ojas Parekh, Nadezhda Voronova
2023	J	`jnl`	Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model. Electron. Colloquium Comput. Complex. John Kallaugher, Ojas Parekh, Nadezhda Voronova
2022	A*	`conf`	Factorial Lower Bounds for (Almost) Random Order Streams. FOCS Ashish Chiplunkar, John Kallaugher, Michael Kapralov, Eric Price
2022	A*	`conf`	Simulating Random Walks in Random Streams. SODA John Kallaugher, Michael Kapralov, Eric Price
2022	A*	`conf`	The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut. FOCS John Kallaugher, Ojas Parekh
2022	J	`jnl`	The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut. CoRR John Kallaugher, Ojas Parekh
2021	A*	`conf`	A Quantum Advantage for a Natural Streaming Problem. FOCS John Kallaugher
2021	J	`jnl`	A Quantum Advantage for a Natural Streaming Problem. CoRR John Kallaugher
2021	—	`conf`	An Optimal Algorithm for Triangle Counting in the Stream. APPROX-RANDOM Rajesh Jayaram, John Kallaugher
2021	J	`jnl`	An Optimal Algorithm for Triangle Counting. CoRR Rajesh Jayaram, John Kallaugher
2021	J	`jnl`	Approximating Local Graph Structure in Almost Random Order Streams. CoRR Ashish Chiplunkar, John Kallaugher, Michael Kapralov, Eric Price
2021	J	`jnl`	Simulating Random Walks in Random Streams. CoRR John Kallaugher, Michael Kapralov, Eric Price
2020	A*	`conf`	Separations and equivalences between turnstile streaming and linear sketching. STOC John Kallaugher, Eric Price
2019	J	`jnl`	Exponential Separations Between Turnstile Streaming and Linear Sketching. CoRR John Kallaugher, Eric Price
2019	A*	`conf`	The Complexity of Counting Cycles in the Adjacency List Streaming Model. PODS John Kallaugher, Andrew McGregor, Eric Price, Sofya Vorotnikova
2018	A*	`conf`	The Sketching Complexity of Graph and Hypergraph Counting. FOCS John Kallaugher, Michael Kapralov, Eric Price
2018	J	`jnl`	The Sketching Complexity of Graph and Hypergraph Counting. CoRR John Kallaugher, Michael Kapralov, Eric Price
2017	A*	`conf`	A Hybrid Sampling Scheme for Triangle Counting. SODA John Kallaugher, Eric Price
2016	J	`jnl`	Improved graph sampling for triangle counting. CoRR John Kallaugher, Eric Price