Noah Fleming

Noah Fleming is an Assistant Professor in the Department of Computer Science at Memorial University, where he is a core member of the Theory Group. He holds a PhD from the University of Toronto under Toni Pitassi, with postdoctoral research at UCSD and the Simons Institute at UC Berkeley. His research focuses on computational complexity, proof complexity, circuit complexity, and robust algorithms, with specific interests in TFNP and sublinear algorithms.

Education: PhD in Computer Science (University of Toronto, 2017), supervised by Toni Pitassi. Postdoctoral positions at UCSD (2017–2020) and Simons Institute (2020–2021).

Research interests include foundational questions in computational complexity, such as proof systems, circuit lower bounds, and the interplay between computational models and algorithmic robustness. His work often bridges theoretical computer science with practical algorithm design, particularly in SAT solvers and sublinear algorithms.

Recent publications explore topics like polynomial hierarchy functions, sensitivity bounds in approximation algorithms, and tradeoffs in proof complexity. His work appears in top venues like STOC, CCC, and ITCS.

Advising: Supervises PhD students Christophe Marciot and Deniz Imrek (co-supervised with Anna Gal), MSc student Jordan Kilfoy (co-supervised with Antonina Kolokolova), and undergraduate researchers Parsa Esmkhani, Grey Seaward, and Michael Gregory (both co-supervised with Antonina Kolokolova). Active in organizing the Theory Group's seminars and workshops.

Labs/Teams: Leads the Complexity Theory research stream within the Theory Group at Memorial University, collaborating with faculty like Antonina Kolokolova and visiting researchers from institutions such as UC Berkeley and University of Toronto.