  This paper proves the first super-logarithmic lower bounds on the cell probe
complexity of dynamic boolean (a.k.a. decision) data structure problems, a
long-standing milestone in data structure lower bounds.
  We introduce a new method for proving dynamic cell probe lower bounds and use
it to prove a $\tilde{\Omega}(\log^{1.5} n)$ lower bound on the operational
time of a wide range of boolean data structure problems, most notably, on the
query time of dynamic range counting over $\mathbb{F}_2$ ([Pat07]). Proving an
$\omega(\lg n)$ lower bound for this problem was explicitly posed as one of
five important open problems in the late Mihai P\v{a}tra\c{s}cu's obituary
[Tho13]. This result also implies the first $\omega(\lg n)$ lower bound for the
classical 2D range counting problem, one of the most fundamental data structure
problems in computational geometry and spatial databases. We derive similar
lower bounds for boolean versions of dynamic polynomial evaluation and 2D
rectangle stabbing, and for the (non-boolean) problems of range selection and
range median.
  Our technical centerpiece is a new way of "weakly" simulating dynamic data
structures using efficient one-way communication protocols with small advantage
over random guessing. This simulation involves a surprising excursion to
low-degree (Chebychev) polynomials which may be of independent interest, and
offers an entirely new algorithmic angle on the "cell sampling" method of
Panigrahy et al. [PTW10].
