Noah Fleming

48 papers A* 5A 11Journal 31
YearRankTypeTitle / Venue / Authors
2026 A* conf
Sensitivity Lower Bounds for Approximation Algorithms.
SODA
Noah Fleming, Yuichi Yoshida
2026 J jnl
Separations above TFNP from Sherali-Adams Lower Bounds.
CoRR
Anna Gál, Noah Fleming, Deniz Imrek, Christophe Marciot
2026 J jnl
Separations above TFNP from Sherali-Adams Lower Bounds.
Electron. Colloquium Comput. Complex.
Noah Fleming, Anna Gál, Christophe Marciot, Deniz Imrek
2026 A conf
Total Search Problems in ZPP.
ITCS
Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Hanlin Ren, Morgan Shirley, Weiqiang Yuan
2025 A conf
Provably Total Functions in the Polynomial Hierarchy.
CCC
Noah Fleming, Deniz Imrek, Christophe Marciot
2025 J jnl
Provably Total Functions in the Polynomial Hierarchy.
Electron. Colloquium Comput. Complex.
Noah Fleming, Christophe Marciot, Deniz Imrek
2025 J jnl
Total Search Problems in ZPP.
CoRR
Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Hanlin Ren, Morgan Shirley, Weiqiang Yuan
2025 J jnl
Total Search Problems in ZPP.
Electron. Colloquium Comput. Complex.
Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Hanlin Ren, Morgan Shirley, Weiqiang Yuan
2025 A* conf
Truly Supercritical Trade-Offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman.
STOC
Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, Shuo Pang
2024 A* conf
Black-Box PPP Is Not Turing-Closed.
STOC
Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere
2024 J jnl
Black-Box PPP is not Turing-Closed.
Electron. Colloquium Comput. Complex.
Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere
2024 J jnl
Sensitivity Lower Bounds for Approximaiton Algorithms.
CoRR
Noah Fleming, Yuichi Yoshida
2024 J jnl
Sensitivity Lower Bounds for Approximaiton Algorithms.
Electron. Colloquium Comput. Complex.
Noah Fleming, Yuichi Yoshida
2024 J jnl
Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman.
CoRR
Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, Shuo Pang
2024 J jnl
Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman.
Electron. Colloquium Comput. Complex.
Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, Shuo Pang
2023 A conf
Limits of CDCL Learning via Merge Resolution.
SAT
Marc Vinyals, Chunxiao Li, Noah Fleming, Antonina Kolokolova, Vijay Ganesh
2023 J jnl
Limits of CDCL Learning via Merge Resolution.
CoRR
Marc Vinyals, Chunxiao (Ian) Li, Noah Fleming, Antonina Kolokolova, Vijay Ganesh
2023 J jnl
Limits of CDCL Learning via Merge Resolution.
Electron. Colloquium Comput. Complex.
Noah Fleming, Vijay Ganesh, Antonina Kolokolova, Chunxiao Li, Marc Vinyals
2023 A* conf
Low Degree Testing over the Reals.
SODA
Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida
2023 A conf
TFNP Characterizations of Proof Systems and Monotone Circuits.
ITCS
Sam Buss, Noah Fleming, Russell Impagliazzo
2022 A conf
Extremely Deep Proofs.
ITCS
Noah Fleming, Toniann Pitassi, Robert Robere
2022 J jnl
Low Degree Testing over the Reals.
CoRR
Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida
2022 J jnl
Low Degree Testing over the Reals.
Electron. Colloquium Comput. Complex.
Vipul Arora, Arnab Bhattacharyya, Noah Fleming, Esty Kelman, Yuichi Yoshida
2022 A conf
On Semi-Algebraic Proofs and Algorithms.
ITCS
Noah Fleming, Mika Göös, Stefan Grosser, Robert Robere
2022 J jnl
On Semi-Algebraic Proofs and Algorithms.
Electron. Colloquium Comput. Complex.
Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere
2022 J jnl
Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes.
J. ACM
Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere
2022 J jnl
TFNP Characterizations of Proof Systems and Monotone Circuits.
Electron. Colloquium Comput. Complex.
Sam Buss, Noah Fleming, Russell Impagliazzo
2021 J jnl
Extremely Deep Proofs.
Electron. Colloquium Comput. Complex.
Noah Fleming, Toniann Pitassi, Robert Robere
2021 A conf
On the Hierarchical Community Structure of Practical Boolean Formulas.
SAT
Chunxiao Li, Jonathan Chung, Soham Mukherjee, Marc Vinyals, Noah Fleming, Antonina Kolokolova, Alice Mu, Vijay Ganesh
2021 J jnl
On the Hierarchical Community Structure of Practical SAT Formulas.
CoRR
Chunxiao Li, Jonathan Chung, Soham Mukherjee, Marc Vinyals, Noah Fleming, Antonina Kolokolova, Alice Mu, Vijay Ganesh
2021 A conf
On the Power and Limitations of Branch and Cut.
CCC
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
2021 J jnl
On the Power and Limitations of Branch and Cut.
CoRR
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
2021 J jnl
On the Power and Limitations of Branch and Cut.
Electron. Colloquium Comput. Complex.
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson
2021 J jnl
Reflections on Proof Complexity and Counting Principles.
Electron. Colloquium Comput. Complex.
Noah Fleming, Toniann Pitassi
2021 — —
The Proof Complexity of Integer Programming.
Noah Fleming
2020 A conf
Distribution-Free Testing of Linear Functions on ℝⁿ.
ITCS
Noah Fleming, Yuichi Yoshida
2020 A conf
Towards a Complexity-Theoretic Understanding of Restarts in SAT Solvers.
SAT
Chunxiao Li, Noah Fleming, Marc Vinyals, Toniann Pitassi, Vijay Ganesh
2020 J jnl
Towards a Complexity-theoretic Understanding of Restarts in SAT solvers.
CoRR
Chunxiao Li, Noah Fleming, Marc Vinyals, Toniann Pitassi, Vijay Ganesh
2019 J jnl
Distribution-Free Testing of Linear Functions on R^n.
CoRR
Noah Fleming, Yuichi Yoshida
2019 J jnl
Semialgebraic Proofs and Efficient Algorithm Design.
Electron. Colloquium Comput. Complex.
Noah Fleming, Pravesh Kothari, Toniann Pitassi
2019 J jnl
Semialgebraic Proofs and Efficient Algorithm Design.
Found. Trends Theor. Comput. Sci.
Noah Fleming, Pravesh Kothari, Toniann Pitassi
2018 A conf
Stabbing Planes.
ITCS
Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere
2017 J jnl
Random CNFs are Hard for Cutting Planes.
CoRR
Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere
2017 J jnl
Random CNFs are Hard for Cutting Planes.
Electron. Colloquium Comput. Complex.
Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere
2017 A* conf
Random Θ(log n)-CNFs Are Hard for Cutting Planes.
FOCS
Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere
2017 J jnl
Stabbing Planes.
CoRR
Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere
2017 J jnl
Stabbing Planes.
Electron. Colloquium Comput. Complex.
Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere
2015 J jnl
Complexity of alignment and decoding problems: restrictions and approximations.
Mach. Transl.
Noah Fleming, Antonina Kolokolova, Renesa Nizamee