1. Sensitivity Lower Bounds for Approximation Algorithms
    Noah Fleming, Yuichi Yoshida
    In Submission.

  2. Total Search Problems in ZPP
    Noah Fleming, Stefan Grosser, Hanlin Ren, Siddhartha Jain, Jiawei Li, Morgan Shirley, Weiqiang Yuan
    In Submission.

  3. Provably Total Functions in the Polynomial Hierarchy
    Noah Fleming, Deniz Imrek, Christophe Marciot
    ⊳CCC 2025.

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

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

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

  7. TFNP Characterizations of Proof Systems and Monotone Circuits
    Sam Buss, Noah Fleming, Russell Impagliazzo
    ⊳ITCS 2023.
    Video: Presenting at ITCS 2023.

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

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

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

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

  12. 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 2021. [Slides]
    Video: Presenting at University of Copenhagen MIAO Seminar. [Slides]
    Video: Presenting at CCC 2021.

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

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

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

  16. Semialgebraic Proofs and Efficient Algorithm Design
    Noah Fleming, Pravesh Kothari, Toniann Pitassi
    ⊳Foundations and Trends in Theoretical Computer Science 2019. [Slides]

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

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

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

Theses

  1. The Proof Complexity of Integer Programming
    Noah Fleming
    PhD Thesis