2 papers
cs.CC2020
Clique Is Hard on Average for Regular Resolution
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende +3
We prove that for regular resolution requires length to establish that an Erdős-Rényi graph with appropriately chosen edge density does not contain a…
cs.CC2015
Space proof complexity for random 3-CNFs
Patrick Bennett, Ilario Bonacina, Nicola Galesi +3
We investigate the space complexity of refuting -CNFs in Resolution and algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a random -CNF…