Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with bootstrapping:
TR18-132 | 17th July 2018
Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse

Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits

Revisions: 3

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 >>>

TR23-082 | 1st June 2023
Ryan Williams

Self-Improvement for Circuit-Analysis Problems

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint