Summary for curious non-experts:
Suppose you have a randomized algorithm that estimates some
numeric quantity, and you want to use it as a subroutine,
i.e. a building block in some other algorithm. Suppose the
estimation algorithm makes
n coin tosses, and you
plan to execute it
k times. This situation seems
to call for
nk coin tosses in total. In this paper,
we show that you can actually get away with only making
about
n + k coin tosses if you use some tricks.
Versions:
The
arXiv version
and the
ECCC version
are identical.
Resources: Adam Klivans presented this paper at the
Simons Institute "Proving and Using Pseudorandomness"
workshop in March 2017; a video is available
here.