Image

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


Current Team

Recent Publications

  1. Separations above TFNP from Sherali-Adams Lower Bounds
    Noah Fleming, Anna Gal, Deniz Imrek, Christophe Marciot

  2. Sensitivity Lower Bounds for Approximation Algorithms
    Noah Fleming, Yuichi Yoshida
    ⊳ SODA 2026.

  3. Total Search Problems in ZPP
    Noah Fleming, Stefan Grosser, Hanlin Ren, Siddhartha Jain, Jiawei Li, Morgan Shirley, Weiqiang Yuan
    ⊳ ITCS 2026.
    Videoa>: Morgan presenting at ITCS.

  4. Provably Total Functions in the Polynomial Hierarchy
    Noah Fleming, Deniz Imrek, Christophe Marciot
    ⊳CCC 2025.
    Video: Christophe presenting at CCC.
    Video: Presenting at MIAO Research Seminar.

  5. 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.
    Video: Duri presenting at MIAO Research Seminar.

  6. Black-Box PPP is not Turing Closed
    Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere
    ⊳STOC 2024.
    Video: Presenting at MFO Oberwolfach.
    Video: Stefan presenting at STOC.

  7. 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.

  8. 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.

  9. 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.

  10. Extremely Deep Proofs
    Noah Fleming, Toniann Pitassi, Robert Robere
    ⊳ITCS 2022.
    Video: Presenting at ITCS.

  11. On Semi-Algebraic Proofs and Algorithms
    Noah Fleming, Mika Göös, Stefan Grosser, Robert Robere
    ⊳ITCS 2022.
    Video: Stefan presenting at ITCS

  12. Reflections on Proof Complexity and Counting Principles
    Noah Fleming, Toniann Pitassi
    ⊳Alasdair Urquhart on Nonclassical and Algebraic Logic and Complexity of Proofs, Outstanding Contributions to Logic 2022.

  13. On the Power and Limitations of Branch and Cut
    Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
    ⊳CCC 2021.
    ⊳Invited to the special journal issue for CCC 2021.
    Video: Presenting at the Simons Institute.
    Video: Presenting at MIAO Research Seminar.
    Video: Presenting at CCC.

  14. On the Hierarchical Community Structure of Practical SAT Formulas
    Chunxiao Li, Jonathan Chung, Soham Mukherjee, Marc Vinyals, Noah Fleming, Antonina Kolokolova, Alice Mu, Vijay Ganesh
    ⊳SAT 2021.

  15. Towards a Complexity-Theoretic Understanding of Restarts in SAT Solvers
    Chunxiao Li, Noah Fleming, Marc Vinyals, Toniann Pitassi, Vijay Ganesh
    ⊳SAT 2020.
    Video: Ian presenting at the Simons Institute.

  16. Distribution-Free Testing of Linear Functions on R^n
    Noah Fleming, Yuichi Yoshida
    ⊳ITCS 2020.

  17. Semialgebraic Proofs and Efficient Algorithm Design
    Noah Fleming, Pravesh Kothari, Toniann Pitassi
    ⊳Foundations and Trends in Theoretical Computer Science.

  18. Stabbing Planes
    Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere
    ⊳ITCS 2018.
    Video: Presenting at ITCS.

  19. Random Ⲑ(log n)-CNFs are Hard for Cutting Planes
    Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere
    ⊳FOCS 2017.
    ⊳Journal of the ACM.

  20. Complexity of alignment and decoding problems: restrictions and approximations
    Noah Fleming, Antonina Kolokolova, Renesa Nizamee
    ⊳ Machine Translation.


Fun Stuff