Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JOSEPH CULBERSON:
All reports by Author Joseph Culberson:

TR04-012 | 19th December 2003
Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore

The Resolution Complexity of Random Graph $k$-Colorability

We consider the resolution proof complexity of propositional formulas which encode random instances of graph $k$-colorability. We obtain a tradeoff between the graph density and the resolution proof complexity.
For random graphs with linearly many edges we obtain linear-exponential lower bounds on the length of resolution refutations. For any $\epsilon>0$, ... more >>>




ISSN 1433-8092 | Imprint