Targeted SamplersResearch Paper
A randomized algorithm that runs in time and uses random bits usually errs on some fraction of its random strings. Derandomization asks for a deterministic algorithm with the same answers, and fine-grained derandomization asks that the deterministic algorithm be almost as fast, in time rather than . Without a generic…