John Kallaugher

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