New answers tagged


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