research
∙
07/26/2023
Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning
Conflict analysis has been successfully generalized from Boolean satisfi...
share
research
∙
05/31/2023
Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases
We consider the graph k-colouring problem encoded as a set of polynomial...
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...
research
∙
09/25/2022
Certifying Parity Reasoning Efficiently Using Pseudo-Boolean Proofs
The dramatic improvements in combinatorial optimization algorithms over ...
research
∙
03/23/2022
Certified Symmetry and Dominance Breaking for Combinatorial Optimisation
Symmetry and dominance breaking can be crucial for solving hard combinat...
research
∙
08/02/2021
Planning with Learned Binarized Neural Networks Benchmarks for MaxSAT Evaluation 2021
This document provides a brief introduction to learned automated plannin...
research
∙
12/17/2020
Clique Is Hard on Average for Regular Resolution
We prove that for k ≪√(n) regular resolution requires length n^Ω(k) to e...
research
∙
07/06/2020
KRW Composition Theorems via Lifting
One of the major open problems in complexity theory is proving super-log...
research
∙
01/08/2020
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
We establish an exactly tight relation between reversible pebblings of g...
research
∙
01/07/2020
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
We significantly strengthen and generalize the theorem lifting Nullstell...
research
∙
12/02/2019