3 papers
math.OC2025
Cut-based Conflict Analysis in Mixed Integer Programming
Gioni Mexi, Felipe Serrano, Timo Berthold +2
For almost two decades, mixed integer programming (MIP) solvers have used graph-based conflict analysis to learn from local infeasibilities during branch-and-bound search. In this…
cs.CC2025
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström +2
We prove that polynomial calculus (and hence also Nullstellensatz) over any field requires linear degree to refute that sparse random regular graphs, as well as sparse ErdÅs-Rény…
cs.CC2024
Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett +2
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 s…