research
∙
05/30/2023
Hardness of Approximation in PSPACE and Separation Results for Pebble Games
We consider the pebble game on DAGs with bounded fan-in introduced in [P...
share
research
∙
04/19/2023
Limits of CDCL Learning via Merge Resolution
In their seminal work, Atserias et al. and independently Pipatsrisawat a...
research
∙
02/13/2023
Proving Unsatisfiability with Hitting Formulas
Hitting formulas have been studied in many different contexts at least s...
research
∙
03/27/2021
On the Hierarchical Community Structure of Practical Boolean Formulas
Modern CDCL SAT solvers easily solve industrial instances containing ten...
research
∙
10/14/2020
Complexity Measures on the Symmetric Group and Beyond
We extend the definitions of complexity measures of functions to domains...
research
∙
05/23/2020
MaxSAT Resolution and Subcube Sums
We study the MaxRes rule in the context of certifying unsatisfiability. ...
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
∙
01/07/2020