I am a postdoctoral researcher at the University of California, San Diego, hosted by Russell Impagliazzo and Sam Buss.

Prior to this I was:

My research interests lie in the area of computational complexity with a particular focus on proof complexity and its applications to algorithm design and analysis, circuit complexity, and property testing.

Vita

Email: nfleming@eng.ucsd.edu



Education

Ph.D. in Computer Science (2017 - 2021)
University of Toronto
Advisor: Toniann Pitassi

M.Sc. in Computer Science (2015 - 2017)
University of Toronto
Advisor: Toniann Pitassi

B.Sc. Double Major in Computer Science and Pure Mathematics (2010 - 2015)
Memorial University of Newfoundland

Publications

  1. Extremely Deep Proofs
    Noah Fleming, Toniann Pitassi, Robert Robere
    ⊳ITCS 2022.[Slides]

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

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

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

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

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

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

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

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

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

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