I am an assistant professor in the Department of Computer Science at Memorial University, where I am a member of the Theory Group.
I'm interested in computational complexity, where I focus mainly on proof complexity, circuit complexity, TFNP, and related areas. I also enjoy thinking about robust algorithms, such as those with low sensitivity, and property testing.
Previously, I was a postdoctoral researcher at UCSD and a research fellow at the Simons Institute at UC Berkeley. I received my PhD from the University of Toronto where I had the great fortune of being supervised by Toni Pitassi. For more of my academic past life, you can see my curriculum vitae.
- Christophe Marciot. PhD (2023 - Present).
- Deniz Imrek. PhD, co-supervised with Anna Gal (2023 - Present).
- Jordan Kilfoy. MSc, co-supervised with Antonina Kolokolova (2024 - Present).
- Parsa Esmkhani. Undergraduate, co-supervised with Antonina Kolokolova (2023 - Present).
- Grey Seaward. Undergraduate (2023 - 2025).
- Michael Gregory. Undergraduate (2024 - 2025).
Provably Total Functions in the Polynomial Hierarchy
Noah Fleming, Deniz Imrek, Christophe Marciot
⊳CCC 2025.Sensitivity Lower Bounds for Approximation Algorithms
Noah Fleming, Yuichi Yoshida
In Submission.Truly Supercritical Tradeoffs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
Susanna de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, Shuo Pang
⊳STOC 2025.Black-Box PPP is not Turing Closed
Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere
⊳STOC 2024.
Video: Stefan presenting at STOC.Limits of CDCL Learning Via Merge Resolution
Marc Vinyals, Chunxiao Li, Noah Fleming, Antonina Kolokolova, Vijay Ganesh
⊳SAT 2023.
Video: Marc presenting at the Simons Institute.TFNP Characterizations of Proof Systems and Monotone Circuits
Sam Buss, Noah Fleming, Russell Impagliazzo
⊳ITCS 2023.
Video: Presenting at ITCS.
Video: Presenting at the Simons Institute.Low Degree Testing over the Reals
Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshia
⊳SODA 2023.
Video: Esty presenting at the Simons Institute.
Video: Vipul presenting at the Bangalore Theory Seminar Series.
- Winter 2025: COMP 4742/6902
- Fall 2024: COMP 3602, COMP 6901
- Fall 2023: COMP 3602, COMP 6901
- Winter 2023: COMP 4742/6902
- Fall 2022: COMP 6901
- Presenting at my first conference.
- Check out some of my photography!
