The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial f(x_1,\ldots, x_n) of degree at most s will evaluate to a nonzero value at some point on a grid S^n \subseteq \mathbb{F}^n with |S| > s. Thus, there is a deterministic polynomial identity test (PIT) for all degree-s size-s ... more >>>

Many results in fine-grained complexity reveal intriguing consequences from solving various SAT problems even slightly faster than exhaustive search. We prove a ``self-improving'' (or ``bootstrapping'') theorem for Circuit-SAT, \#Circuit-SAT, and its fully-quantified version: solving one of these problems faster for ``large'' circuit sizes implies a significant speed-up for ``smaller'' circuit ... more >>>