Showing cs.CCShow all
3 papers · 1 filter
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ényi…
cs.CC2024
Supercritical Tradeoffs for Monotone Circuits
Mika Göös, Gilbert Maystre, Kilian Risse +1
We exhibit a monotone function computable by a monotone circuit of quasipolynomial size such that any monotone circuit of polynomial depth requires exponential size. This is the fi…
cs.CC2024
Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
Susanna F. de Rezende, Aaron Potechin, Kilian Risse
We prove that Sherali-Adams with polynomially bounded coefficients requires proofs of size to rule out the existence of an -clique in Erdős-Rényi random graphs…