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 - Present).
- Michael Gregory. Undergraduate (2024 - Present).
Provably Total Functions in the Polynomial Hierarchy
Noah Fleming, Deniz Imrek, Christophe Marciot
In Submission.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!
