# John Kallaugher

R&D S&E, Computer Science

## R&D S&E, Computer Science

Sandia National Laboratories, New Mexico

P.O. Box 5800

Albuquerque, NM 87185-1327

## Biography

John is a theoretical computer scientist working on problems at the intersection of quantum and sublinear algorithms. Particular interests include quantum streaming algorithms, Hamiltonian sparsification, and provable techniques for characterizing quantum devices.

## Education

John earned an MMath in Mathematics from Oxford University in 2012. He completed his PhD in Computer Science at UT Austin in 2021, under the supervision of Eric Price. His dissertation was on “Models of Streaming Computation”.

## Publications

- John Kallaugher, Ojas Parekh

The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut https://arxiv.org/abs/2206.00213

FOCS 2022 - Ashish Chiplunkar, John Kallaugher, Michael Kapralov, Eric Price

Factorial Lower Bounds for (Almost) Random Order Streams https://arxiv.org/abs/2110.10091

FOCS 2022 - John Kallaugher, Michael Kapralov, Eric Price

Simulating Random Walks in Random Streams https://arxiv.org/abs/2112.07532

SODA 2022 - John Kallaugher

A Quantum Advantage for a Natural Streaming Problem https://arxiv.org/abs/2106.04633

FOCS 2021 - Rajesh Jayaram, John Kallaugher

An Optimal Algorithm for Triangle Counting in the Stream https://arxiv.org/abs/2105.01785

APPROX 2021 - John Kallaugher, Eric Price

Separations and Equivalences between Turnstile Streaming and Linear Sketching https://arxiv.org/abs/1905.02358

STOC 2020 - John 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 2019 - John Kallaugher, Michael Kapralov, Eric Price

The Sketching Complexity of Graph and Hypergraph Counting https://arxiv.org/abs/1808.04995

FOCS 2018 - John Kallaugher, Eric Price

A Hybrid Sampling Scheme for Triangle Counting https://arxiv.org/abs/1610.02066

SODA 2017