I am an assistant professor at Lund University in the department of Computer Science and a visiting professor at Columbia University.
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.
For my academic past life, you can see my curriculum vitae.
Email: noah.fleming@cs.lth.se
- 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).
-
Sensitivity Lower Bounds for Approximation Algorithms
Noah Fleming, Yuichi Yoshida
SODA 2026. -
Total Search Problems in ZPP
Noah Fleming, Stefan Grosser, Hanlin Ren, Siddhartha Jain, Jiawei Li, Morgan Shirley, Weiqiang Yuan
In Submission. -
Provably Total Functions in the Polynomial Hierarchy
Noah Fleming, Deniz Imrek, Christophe Marciot
⊳CCC 2025. -
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!
