research
∙
04/19/2023
Limits of CDCL Learning via Merge Resolution
In their seminal work, Atserias et al. and independently Pipatsrisawat a...
share
research
∙
04/18/2022
Low Degree Testing over the Reals
We study the problem of testing whether a function f: ℝ^n →ℝ is a polyno...
research
∙
03/27/2021
On the Hierarchical Community Structure of Practical Boolean Formulas
Modern CDCL SAT solvers easily solve industrial instances containing ten...
research
∙
02/09/2021
On the Power and Limitations of Branch and Cut
The Stabbing Planes proof system was introduced to model the reasoning c...
research
∙
03/04/2020
Towards a Complexity-theoretic Understanding of Restarts in SAT solvers
Restarts are a widely-used class of techniques integral to the efficienc...
research
∙
09/08/2019
Distribution-Free Testing of Linear Functions on R^n
We study the problem of testing whether a function f:R^n->R is linear (i...
research
∙
10/09/2017