Noah Fleming
YOU?
Author Swipe
View article: Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman Open
We exhibit supercritical trade-off for monotone circuits, showing that there are functions computable by small circuits for which any circuit must have depth super-linear or even super-polynomial in the number of variables, far exceeding t…
View article: Sensitivity Lower Bounds for Approximaiton Algorithms
Sensitivity Lower Bounds for Approximaiton Algorithms Open
Sensitivity measures how much the output of an algorithm changes, in terms of Hamming distance, when part of the input is modified. While approximation algorithms with low sensitivity have been developed for many problems, no sensitivity l…
View article: Black-Box PPP Is Not Turing-Closed
Black-Box PPP Is Not Turing-Closed Open
The complexity class PPP contains all total search problems many-one reducible to the Pigeon problem, where we are given a succinct encoding of a function mapping n+1 pigeons to n holes, and must output two pigeons that collide in a hole. …
View article: Limits of CDCL Learning via Merge Resolution
Limits of CDCL Learning via Merge Resolution Open
In their seminal work, Atserias et al. and independently Pipatsrisawat and Darwiche in 2009 showed that CDCL solvers can simulate resolution proofs with polynomial overhead. However, previous work does not address the tightness of the simu…
View article: Low Degree Testing over the Reals
Low Degree Testing over the Reals Open
We study the problem of testing whether a function $f: \mathbb{R}^n \to \mathbb{R}$ is a polynomial of degree at most $d$ in the \emph{distribution-free} testing model. Here, the distance between functions is measured with respect to an un…
View article: On the Hierarchical Community Structure of Practical SAT Formulas
On the Hierarchical Community Structure of Practical SAT Formulas Open
Modern CDCL SAT solvers easily solve industrial instances containing tens of millions of variables and clauses, despite the theoretical intractability of the SAT problem. This gap between practice and theory is a central problem in solver …
View article: On the Hierarchical Community Structure of Practical Boolean Formulas
On the Hierarchical Community Structure of Practical Boolean Formulas Open
Modern CDCL SAT solvers easily solve industrial instances containing tens of millions of variables and clauses, despite the theoretical intractability of the SAT problem. This gap between practice and theory is a central problem in solver …
View article: On the Power and Limitations of Branch and Cut
On the Power and Limitations of Branch and Cut Open
The Stabbing Planes proof system [Paul Beame et al., 2018] was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute …
View article: Towards a Complexity-theoretic Understanding of Restarts in SAT solvers
Towards a Complexity-theoretic Understanding of Restarts in SAT solvers Open
Restarts are a widely-used class of techniques integral to the efficiency of Conflict-Driven Clause Learning (CDCL) Boolean SAT solvers. While the utility of such policies has been well-established empirically, a theoretical explanation of…
View article: Distribution-Free Testing of Linear Functions on ℝⁿ
Distribution-Free Testing of Linear Functions on ℝⁿ Open
We study the problem of testing whether a function f:ℝⁿ → ℝ is linear (i.e., both additive and homogeneous) in the distribution-free property testing model, where the distance between functions is measured with respect to an unknown probab…
View article: Distribution-Free Testing of Linear Functions on R^n
Distribution-Free Testing of Linear Functions on R^n Open
We study the problem of testing whether a function f:R^n->R is linear (i.e., both additive and homogeneous) in the distribution-free property testing model, where the distance between functions is measured with respect to an unknown probab…
View article: Semialgebraic Proofs and Efficient Algorithm Design
Semialgebraic Proofs and Efficient Algorithm Design Open
Over the past several decades, an exciting interplay between proof systems and algorithms has emerged. Several prominent algorithms can be viewed as direct translations of proofs that a solution exists into an algorithm for finding that so…
View article: Stabbing Planes
Stabbing Planes Open
We develop a new semi-algebraic proof system called Stabbing Planes which formalizes modern branch-and-cut algorithms for integer programming and is in the style of DPLL-based modern SAT solvers. As with DPLL there is only a single rule: t…
View article: Stabbing Planes
Stabbing Planes Open
We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by branching on an inequ…
View article: Random CNFs are Hard for Cutting Planes
Random CNFs are Hard for Cutting Planes Open
The random k-SAT model is the most important and well-studied distribution over k-SAT instances. It is closely connected to statistical physics; it is used as a testbench for satisfiability algorithms, and average-case hardness over this d…
View article: Random CNFs are Hard for Cutting Planes.
Random CNFs are Hard for Cutting Planes. Open
The random k-SAT model is the most important and well-studied distribution over k-SAT instances. It is closely connected to statistical physics; it is used as a testbench for satisfiability algorithms, and average-case hardness over this d…
View article: Predicting Protein Thermostability Upon Mutation Using Molecular Dynamics Timeseries Data
Predicting Protein Thermostability Upon Mutation Using Molecular Dynamics Timeseries Data Open
A large number of human diseases result from disruptions to protein structure and function caused by missense mutations. Computational methods are frequently employed to assist in the prediction of protein stability upon mutation. These me…