COM2-02-60
660 17596

John KALLAUGHER

Assistant Professor


John is an Assistant Professor in the Department of Computer Science. He obtained his PhD from the University of Texas at Austin in 2021, where he was advised by Eric Price. He then spent four years as a Senior Member of Technical Staff at Sandia National Laboratories in Albuquerque, New Mexico, USA, before joining NUS in 2025. His research interests are in quantum computing and sublinear algorithms, and in particular in problems at the intersection of the two fields, such as quantum streaming algorithms and the resource-efficient exploration of quantum objects.

RESEARCH AREAS

Algorithms & Theory
  • Combinatorial Algorithms
  • Graph Theory & Algorithms
  • Quantum Information & Algorithms

RESEARCH INTERESTS

  • Theoretical Computer Science, in particular quantum computing and sublinear algorithms

RESEARCH PROJECTS

RESEARCH GROUPS

TEACHING INNOVATIONS

SELECTED PUBLICATIONS

  • John Kallaugher, Ojas Parekh, Nadezhda Voronova, Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model, STOC 2024
  • John Kallaugher, A Quantum Advantage for a Natural Streaming Problem, FOCS 2021
  • John Kallaugher, Michael Kapralov, Eric Price, The Sketching Complexity of Graph and Hypergraph Counting, FOCS 2018

AWARDS & HONOURS

COURSES TAUGHT