Noah Fleming

According to our database, Noah Fleming authored at least 23 papers between 2015 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Provably Total Functions in the Polynomial Hierarchy.

Noah Fleming, Christophe Marciot, Deniz Imrek

Electron. Colloquium Comput. Complex., 2025

2024

Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman.

Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, Shuo Pang

Electron. Colloquium Comput. Complex., 2024

Sensitivity Lower Bounds for Approximaiton Algorithms.

Noah Fleming, Yuichi Yoshida

Electron. Colloquium Comput. Complex., 2024

Black-Box PPP is not Turing-Closed.

Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2024

2023

Limits of CDCL Learning via Merge Resolution.

Noah Fleming, Vijay Ganesh, Antonina Kolokolova, Chunxiao Li, Marc Vinyals

Electron. Colloquium Comput. Complex., 2023

2022

Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes.

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

J. ACM, 2022

On Semi-Algebraic Proofs and Algorithms.

Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere

Electron. Colloquium Comput. Complex., 2022

TFNP Characterizations of Proof Systems and Monotone Circuits.

Sam Buss, Noah Fleming, Russell Impagliazzo

Electron. Colloquium Comput. Complex., 2022

Low Degree Testing over the Reals.

Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida

Electron. Colloquium Comput. Complex., 2022

2021

The Proof Complexity of Integer Programming.

Noah Fleming

PhD thesis, 2021

Extremely Deep Proofs.

Noah Fleming, Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2021

Reflections on Proof Complexity and Counting Principles.

Noah Fleming, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2021

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

Electron. Colloquium Comput. Complex., 2021

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

CoRR, 2021

On the Hierarchical Community Structure of Practical Boolean Formulas.

Chunxiao Li, Jonathan Chung, Soham Mukherjee, Marc Vinyals, Noah Fleming, Antonina Kolokolova, Alice Mu, Vijay Ganesh

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2021, 2021

2020

Towards a Complexity-Theoretic Understanding of Restarts in SAT Solvers.

Chunxiao Li, Noah Fleming, Marc Vinyals, Toniann Pitassi, Vijay Ganesh

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2020, 2020

Distribution-Free Testing of Linear Functions on ℝⁿ.

Noah Fleming, Yuichi Yoshida

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Semialgebraic Proofs and Efficient Algorithm Design.

Noah Fleming, Pravesh Kothari, Toniann Pitassi

Electron. Colloquium Comput. Complex., 2019

Distribution-Free Testing of Linear Functions on R^n.

Noah Fleming, Yuichi Yoshida

CoRR, 2019

2017

Random CNFs are Hard for Cutting Planes.

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2017

Stabbing Planes.

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

Electron. Colloquium Comput. Complex., 2017

Random Θ(log n)-CNFs Are Hard for Cutting Planes.

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2015

Complexity of alignment and decoding problems: restrictions and approximations.

Noah Fleming, Antonina Kolokolova, Renesa Nizamee

Mach. Transl., 2015