I am a Ph.D. student in the Theory Group at the University of Toronto, where I am fortunate to be supervised by Toni Pitassi.

Previously, I was a M.V. Raghunathan Research Fellow at the Simons Institute, Berkeley for the Satisfiability: Theory and Practice Program.

My research interests include proof complexity and its applications to algorithm design and analysis, circuit complexity, and property testing.

Vita

Email: noahfleming@cs.toronto.edu



Education

Ph.D. in Computer Science (2017 - Present)
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. 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
    ⊳To Appear at CCC 2021.
    ⊳Invited to CCC 2021 special issue.
    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.

  2. 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
    ⊳To Appear at SAT 2021.

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

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

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

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

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

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

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


University of Toronto ICPC Team
I am coaching the University of Toronto ICPC teams. More information can be found at the University of Toronto ICPC webpage