Noah Fleming

According to our database, Noah Fleming authored at least 27 papers between 2015 and 2026.

Collaborative distances:

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

2026

Non-Signaling Locality Lower Bounds for Dominating Set.

Noah Fleming, Max Hopkins, Yuichi Yoshida

CoRR, April, 2026

Separations above TFNP from Sherali-Adams Lower Bounds.

Noah Fleming, Anna Gál, Christophe Marciot, Deniz Imrek

Electron. Colloquium Comput. Complex., 2026

Sensitivity Lower Bounds for Approximation Algorithms.

Noah Fleming, Yuichi Yoshida

Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, 2026

Total Search Problems in ZPP.

Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Hanlin Ren, Morgan Shirley, Weiqiang Yuan

Proceedings of the 17th Innovations in Theoretical Computer Science Conference, 2026

2025

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

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Provably Total Functions in the Polynomial Hierarchy.

Noah Fleming, Deniz Imrek, Christophe Marciot

Proceedings of the 40th Computational Complexity Conference, 2025

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

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023

Low Degree Testing over the Reals.

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

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Limits of CDCL Learning via Merge Resolution.

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

Proceedings of the 26th International Conference on Theory and Applications of Satisfiability Testing, 2023

TFNP Characterizations of Proof Systems and Monotone Circuits.

Sam Buss, Noah Fleming, Russell Impagliazzo

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

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

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

J. ACM, 2022

Extremely Deep Proofs.

Noah Fleming, Toniann Pitassi, Robert Robere

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

On Semi-Algebraic Proofs and Algorithms.

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

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

2021

The Proof Complexity of Integer Programming.

Noah Fleming

PhD thesis, 2021

Reflections on Proof Complexity and Counting Principles.

Noah Fleming, Toniann Pitassi

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

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

Proceedings of the 36th Computational Complexity Conference, 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

Found. Trends Theor. Comput. Sci., 2019

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

Noah Fleming, Yuichi Yoshida

CoRR, 2019

2018

Stabbing Planes.

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

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Random CNFs are Hard for Cutting Planes.

Noah Fleming, 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