New answers tagged

2

This paper by Régis Barbanchon might be of interest. From the abstract: We prove that the Satisfiability (resp. planar Satisfiability) problem is parsimoniously P-time reducible to the 3-Colorability (resp. Planar 3-Colorability) problem, that means that the exact number of solutions is preserved by the reduction, provided that 3-colorings are counted ...


4

There are a few points to consider here: If we wish to show that $CC(f) = \omega(\log n)$, we should show that it is not possible to cover the domain of $f$ using $\mathrm{poly}(n)$ monochromatic rectangles (rather than $n$ rectangles). Showing it for $n$ rectangles would only establish that $CC(f) > \log n$. If we wish to prove a lower bound on $D(EQ)$,...


Top 50 recent answers are included