Noah Fleming
Assistant Professor
Department of Computer Science, Memorial University of Newfoundland and Labrador
e-mail: nfleming@mun.ca
www: cs.mun.ca/˜noahfleming
Google Scholar : dblp

Research Interests
Complexity Theory. Including proof complexity, circuit complexity, TFNP, interactions between them, and similar topics.
Algorithm Design and Analysis. Applications of proof complexity to the design and analysis of practical algorithms,
sublinear algorithms, property testing, and sensitive algorithms.

Education and Employment− Assistant Professor
Memorial University of Newfoundland and Labrador, St. John’s, Canada.
− Postdoctoral Research Fellow
University of California, San Diego, USA.
Hosted by Russell Impagliazzo and Samuel Buss
− M.V. Raghunathan Research Fellow
Simons Institute, University of California, Berkeley, California, USA.
Satisfiability: Theory, Practice, and Beyond Program.
− Ph.D. in Computer Science
University of Toronto, Toronto, Canada.
Advisor: Toniann Pitassi
Title: The Proof Complexity of Integer Programming.
− M.Sc. in Computer Science
University of Toronto, Toronto, Canada.
Advisor: Toniann Pitassi
Project Title: Linear Threshold Proof Systems.
− B.Sc. Double Major in Computer Science and Pure Mathematics
Memorial University of Newfoundland, St. John’s, Canada.

2022 – Present
2021 – 20222021
2017 – 2021

2015 – 20172010 - 2015

Visiting Positions− Simons Institute, Berkely, U.S.A.
Visiting Researcher.
Satisfiability: Extended Reunion Program.
− National Institute of Informatics, Tokyo, Japan
Research intern in Theoretical Computer Science.
Supervisor: Yuichi Yoshida.
− Simons Institute, Berkely, U.S.A.
Visiting Graduate Student.
Lower Bounds in Computational Complexity Program.
− Institute for Advanced Study, Princeton, U.S.A.
Visiting Graduate Student.

Fall 2023
Summer 2019
Fall 2018
Fall 2017

Research Funding− NSERC Discovery Grant ($205, 000)
2023 - 2028
Principal Canadian research grant. 58% success rate with an average award of $173, 000 for early career researchers(ECR) in my application year of 2023.
− NSERC Discovery Launch Supplement ($12, 500)
2023
− Memorial University Startup grant ($40, 000)
2022 - 2025

1

Awards and Honours− UCSD CSE Postdoctoral Fellowship ($124, 000 USD)
− Invited special issue journal article “On the Power and Limitations of Branch and Cut” at CCC 2021.
Honour reserved for the top 5-10 papers in the conference.
− NSERC Postdoctoral Fellowship (PDF) ($90, 000 CAD)
− Graduate Completion Award ($1, 600 CAD)
− Acres Productive Technologies Inc./Joseph Yonan Memorial Fellowship ($2, 000 CAD)
− Ontario Graduate Scholarship ($15, 000 CAD)
− Walter C. Sumner Memorial Fellowship ($8, 000 CAD)
− Walter C. Sumner Memorial Fellowship ($8, 000 CAD)
− Mitacs Globalink Research Award - Japan Society for the Promotion of Science(¥534, 000 YEN)
− NSERC Alexander Graham Bell Canada Graduate Scholarship - Doctoral (CGSD)($105, 000 CAD)− NSERC Alexander Graham Bell Canada Graduate Scholarship - Master’s (CGSM)($17, 500 CAD)

2021 - 2023
2021
2021 - 2023
2021
2020
2020
2020
20192019
2017 - 20202015 - 2016

Publications
Peer Reviewed Conference Publications
1. Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere. Black-Box PPP is not Turing Closed.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024).
doi: 10.1145/3618260.3649769
2. Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida. Low Degree Testing over the Reals.
Proceedings of the 2023 Symposium on Discrete Algorithms (SODA 2023).
doi: 10.1137/1.9781611977554.ch31
3. Marc Vinyals, Chunxiao Li, Noah Fleming, Antonina Kolokolova, Vijay Ganesh. Limits of CDCL Learning via Merge
Resolution.
Proceedings of the 26th International Conference on the Theory and Applications of Satisfiability Testing (SAT 2023).
doi: 10.4230/LIPIcs.SAT.2023.27
4. Sam Buss, Noah Fleming, Russell Impagliazzo. TFNP Characterizations of Proof Systems and Monotone Circuits.
Proceedings of the 14th Innovations in Theoretical Computer Science (ITCS 2023).
doi: 10.4230/LIPIcs.ITCS.2023.30
5. Noah Fleming, Toniann Pitassi, Robert Robere. Extremely Deep Proofs.
Proceedings of the 13th Innovations in Theoretical Computer Science (ITCS 2022).
doi: 10.4230/LIPIcs.ITCS.2022.70
6. Noah Fleming, Mika Göös, Stefan Grosser, Robert Robere. On Semi-Algebraic Proofs and Algorithms.
Proceedings of the 13th Innovations in Theoretical Computer Science (ITCS 2022).
doi: 10.4230/LIPIcs.ITCS.2022.69
7. Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Li-Yang Tan, Robert Robere, Avi Wigderson. On thePower and Limitations of Branch and Cut.
Proceedings of the 36th Computational Complexity Conference (CCC 2021).
doi: 10.4230/LIPIcs.CCC.2021.6
Invited to the special journal issue for CCC 2021.
8. Chunxiao Li, Jonathan Chung, Soham Mukherjee, Marc Vinyals, Noah Fleming, Antonina Kolokolova, Alice Mu, Vijay
Ganesh. On the Hierarchical Community Structure of Practical SAT Formulas.
Proceedings of the 24th International Conference on the Theory and Applications of Satisfiability Testing (SAT 2021).
doi: 10.1007/978-3-030-80223-3 25
9. Chunxiao Li, Noah Fleming, Marc Vinyals, Toniann Pitassi, Vijay Ganesh. Towards a Complexity-Theoretic Understanding of Restarts in SAT Solvers. Proceedings of the 23rd International Conference on the Theory and Applicationsof Satisfiability Testing (SAT 2020).
doi: 10.1007/978-3-030-51825-7 172

10. Noah Fleming, Yuichi Yoshida. Distribution-Free Testing of Linear Functions on Rn .
Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS 2020).
doi: 10.4230/LIPIcs.ITCS.2020.22
11. Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, RobertRobere. Stabbing Planes.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018).
doi: 10.4230/LIPIcs.ITCS.2018.10
12. Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere. Random Θ(log n)-CNFs are Hard for Cutting Planes.
Proceedings of the 58th annual IEEE Symposium on Foundations of Computer Science (FOCS 2017).
doi: 10.1109/FOCS.2017.19
Peer Reviewed Journal Publications
1. Noah Fleming, Mika Göös, Russell Impgaliazzo, Toniann Pitassi, Li-Yang Tan, Robert Robere, Avi Wigderson. On thePower and Limitations of Branch and Cut.
Theory of Computing (ToC 2024).
2. Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere. Random Θ(log n)-CNFs are Hard for Cutting Planes.
Journal of the ACM (JACM 2022).
doi: 10.1145/3486680
3. Noah Fleming, Pravesh Kothari, Toniann Pitassi. Semialgebraic Proofs and Efficient Algorithm Design.
RFoundations and Trends©
in Theoretical Computer Science, 14 (1-2): 1-229 (2019).
doi: 10.1561/0400000086
4. Noah Fleming, Antonina Kolokolova, Renesa Nizamee. Complexity of Alignment and Decoding Problems: Restrictions
and Approximations.
Machine Translation, 29 (3-4): 163-187 (2015).
doi: 10.1007/s10590-015-9172-5
In Submission− Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida. Low Degree Testing over the Reals.
In submission to Algorithmica.
− Sam Buss, Noah Fleming, Russell Impagliazzo. TFNP Characterizations of Proof Systems and Monotone Circuits.
In submission to SIAM Journal on Computing.
Book Chapters
1. Noah Fleming, Toniann Pitassi. Reflections on Proof Complexity and Counting Principles.
In Ivo Düntsch and Edwin Mares, editors, Alasdair Urquhart on Nonclassical and Algebraic Logic and Complexity ofProofs, Outstanding Contributions to Logic. Springer International Publishing (2022).
doi: 10.1007/978-3-030-71430-7Supervision
Graduate Students− Christophe Marciot (Memorial University, Ph.D.)− Deniz Imrek (University of Austin, Ph.D., co-supervised with Anna Gal)
− Jordan Kilfoy (Memorial University, MSc., co-supervised with Antonina Kolokolova)

2023 – Present
2023 – Present
2024 – Present

Undergraduate Students− Michael Gregory (Memorial University)
Honours Thesis on generalized Polynomial Calculus lower bounds.
− Grey Seaward (Memorial University)
Honours Thesis on Meta-complexity and TFNP.
− Parsa Esmkhani (Memorial University, co-supervised with Antonina Kolokolova)
Honours Thesis on Algorithmic Game Theory and TFNP.
32024 – Present
2023 – Present
2023 – Present

− Gavin Hull (Memorial University).
Research project on communication complexity.
− Felipe Heap (University of Toronto, co-supervised with Toniann Pitassi).
Research project on monotone circuit lower bounds and the sensitivity conjecture.

Winter 2023
2019

Postdocs and Visiting Researchers− Marc Vinyals (Memorial University, co-hosted with Antonina Kolokolova)

2022

Professional Service− External Reviewer− Conferences: FOCS, STOC, CCC, ITCS, SODA, SAT, ISAAC, ICALP, LICS, ESA, STACS, Random.
− Journals: Journal of the ACM, Theory of Computing, Information Processing Letters, TheoretiCS, Computational
Complexity, Logical Methods in Computer Science, Journal of Artificial Intelligence.

− Faculty Search Committee. Department of Computer Science, Memorial University.
− 2022 – 2023, 2023 – 2024, 2024 – 2025.

− Graduate Student Admissions Committee. Department of Computer Science, Memorial University.
− 2022 – 2023.

− Faculty of Science representative to the Faculty of Business Faculty Council. Memorial University.
− 2022 – 2023.

− Head Coach, University of Toronto International Collegiate Programming Contest (ICPC) Team. University of Toronto.
2018 – 2021
Organized and ran programming competitions, problem sessions, and practices for the three University of Toronto
ICPC teams. Organized logistics and transportation to regional championships. Secured funding to run the teams
from the University of Toronto.
− Teaching Assistant. University of Toronto.

2015 – 2021

− CSC438/2404 (1 appt.), CSC165 (9 appt.), CSC373 (1 appt.), CSC363 (1 appt.), CSC263 (1 appt.)− Lead Mentor, Undergraduate Summer Research Program. University of Toronto

2016

Held weekly mentoring sessions for undergraduate students participating in the Department of Computer Science
Undergraduate Summer Research Program to guide them on their research project.

Teaching− Comp 3602: Introduction to the Theory of Computing. Memorial University.
− Fall 2023, Fall 2024− Comp 6901: Applied Algorithms. Memorial University.
− Fall 2022, Fall 2023, Fall 2024

− Comp 6902/COMP 4742: Theory of Computation. Memorial University.
− Winter 2023, Winter 2024

− CSC165: Mathematical Expression and Reasoning. University of Toronto.
− Winter 2017. Co-taught with Toniann Pitassi.

Seminars and Reading Series− Theory Reading Group. Memorial University
Winter 2023 – Present
Weekly seminar series on topics in theoretical computer science.
− CSC199: Special topics in Computer Science. University of California, San-Diego.
Fall 2021
Seminar on the Theory of SAT. Covering topics in propositional and algebraic proof systems, and SAT Solvers. Coorganized with Sam Buss, Sicun Gao, and Russell Impagliazzo.
4

Invited Talks
These do not include presentations for accepted papers at conferences.
− MIAO Seminar
University of Copenhagen, Copenhagen, Denmark.
Seminar Title: PPP is not Turing Closed in the Black-Box Setting.
− Proof Complexity and Beyond Workshop
MFO Oberwolfach, Germany.
Seminar Title: PPP is not Closed for Turing Reductions.
− Theory Seminar
National Institute of Informatics, Tokyo, Japan.
Seminar Title: Black-Box PPP is not Turing Closed.
− Math Colloquium
Memorial University, Newfoundland, Canada.
Seminar Title: A Logical Approach to P vs. NP.
− Theory Seminar
University of Toronto, Toronto, Canada.
Invited Speaker.
Seminar Title: Proofs, Circuits, and Total Functions.
− Extended Reunion: Satisfiability Program
Simons Institute, Berkeley, California, USA.
Seminar Title: The Proof Complexity of Integer Programming.
− Meta-Complexity Program
Simons Institute, Berkeley, California, USA.
Seminar Title: TFNP, Proof Complexity and Monotone Circuit Complexity.
− North American Annual Meeting of the Association for Symbolic Logic
University of California, Irvine, California, USA.
Seminar Title: The Proof Complexity of Integer Programming.
− Satisfiability: Theory, Practice, and Beyond Reunion Program
Simons Institute, Berkeley, California, USA.
Seminar Title: Extremely Deep Proofs.
− Online SAT Seminar
Online.
Seminar Title: Extremely Deep Proofs.
− UCSD Theory Seminary, University of California, San Diego
San Diego, California, USA.
Seminar Title: Semi-Algebraic Proofs and Algorithms.
− Oxford-Warwick Complexity Meeting
Online.
Seminar Title: Extremely Deep Proofs.
− MIAO Video Seminar, University of Copenhagen
Copenhagen, Denmark.
Seminar Title: On the Complexity of Branch-and-Cut.
− Simons InstituteBerkeley, California, USA.
Seminar Title: The Proof Complexity of Integer Programming Solvers.
− Simons InstituteBerkeley, California, USA.
Seminar Title: The Proof Complexity of Practical Integer Programming.
− Institute for Advanced Study
Princeton, New Jersey, USA.
Invited Speaker.
Seminar Title: Recent Progress on Cutting Planes Proofs.
− BIRS Proof Complexity Workshop 20w5144
BIRS Centre, Banff, Canada.
Seminar Title: Semialgebraic Proofs and Efficient Algorithm Design.

52024
2024
2024
2023
2023

2023
2023
2023
2022
2022
2022
2021
2021
2021
2021
2020

2020

− Simon Fraser University Theory Seminar
Simon Fraser University, Vancouver, Canada.
Seminar Title: Stabbing Planes.
− Memorial University of Newfoundland Computer Science Seminar.
Memorial University of Newfoundland, St. John’s, Canada.
Seminar Title: Random CNF formulas are hard to refute in Cutting Planes.
− Proof Complexity Workshop
Dagstuhl, Germany.
Seminar Title: Stabbing Planes.
− Proof Complexity and Beyond Workshop
MFO Oberwolfach, Germany.
Seminar Title: Random Θ(log n)-CNF formulas Are Hard for Cutting Planes.

201920182018
2017

Short-Term Visiting Researchers− Morgan Shirley.
− Jiawei Li.
− Ian Mertz.
− Chunxiao Li. (Co-hosted with Antonina Kolokolova).
− Vijay Ganesh. (Co-hosted with Antonina Kolokolova).

Fall 2024
Summer 2024
Winter 2024
Fall 2022
Fall 2022

6