Modular coloring formulas are hard for cutting planes proofs
Xudong Fu · 1996
The modulo r coloring principle states that for any r-coloring of a set of size n and any partition of that set into groups of size r, each group cent aining exactly one element of each color, each color occurs at most ~times.For n a multiple of r, we show ~nn (lOg") lower bound on the length of cutting planes proof systems for modulo r coloring principles by extending Razborov's well-known lower bound on the size of monotone boolean circuits that compute Perfect Mat thing.The lower bound is extended to monotone circuits over the reals that compute the same function.1