Hi! I am an assistant professor in the Department of Computer Science at Memorial University.

My research interests are in the area of computational complexity with a particular focus on proof complexity, circuit complexity and the connections between them. I am also interested in the applications of proof complexity to algorithmic design and analysis, as well as property testing.

Previously, I was a postdoctoral researcher at UCSD and a research fellow at the Simons Institute, Berkeley. I received my PhD from the University of Toronto where I had the great fortune of being supervised by Toni Pitassi.

Vita

Email: nfleming@mun.ca



Recent Publications

  1. Low Degree Testing over the Reals
    Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshia
    ⊳In Submission.

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

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

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

  5. 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: Noah presenting at the Simons Institute 2021. [Slides]
    Video: Noah presenting at University of Copenhagen MIAO Seminar. [Slides]
    Video: Noah presenting at CCC 2021.

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

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

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

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

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

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

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

Other Manuscripts, Projects & Expository Writings

  1. Cuckoo Hashing and Cuckoo Filters
    Noah Fleming
    An exposition on Cuckoo Hashing and Cuckoo Filters.

  2. Predicting Protein Thermostability Upon Mutation Using Molecular Dynamics Timeseries Data
    Noah Fleming, Benjamin Kinsella, Christopher Ing
    Manuscript 2016.

SAT Seminar
Sam Buss, Russell Impagliazzo, Sicun Gao, and I are running a seminar on proof complexity and SAT. The webpage for the seminar can be found here and my slides for the first two lectures are below.
  1. Lecture 1. [slides]
  2. Lecture 2. [slides]
  3. Lecture 3. [slides]
  4. Lecture 4. [slides]
  5. Lecture 5. [slides]
  6. Lecture 6. [slides]
  7. Lecture 7. [slides]
Theses
Fun Stuff