2 papers
cs.CC2025
Lower Bounds for CSP Hierarchies Through Ideal Reduction
Jonas Conneryd, Yassine Ghannane, Shuo Pang
We present a generic way to obtain level lower bounds for (promise) CSP hierarchies from degree lower bounds for algebraic proof systems. More specifically, we show that pseudo-red…
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…