Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > BOOTSTRAPPING:
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