= Avi Wigderson
{c}
<Avi Wigderson> studies <computational complexity theory>, including the role of <randomized algorithms> in efficient computation. His research connects <pseudorandom generators>, computational hardness and <derandomization>. His book <Mathematics and Computation by Avi Wigderson> explains how sufficiently strong circuit-hardness assumptions can supply generators that fool efficient computational tests.<Mathematics and Computation by Avi Wigderson>[Chapter 7, especially §7.3.2, pseudorandom generators from hard problems]{ref}
The mechanism turns a lower-bound assumption into an algorithmic resource. If a generator with a short seed preserves a randomized computation's acceptance probability closely enough, enumerating all seeds can replace sampling random bits. The seed must be short enough for that enumeration to meet the claimed time bound; simply fixing one arbitrary seed does not supply the guarantee. This makes the power of randomness a precise question about computation rather than a visual impression that an output “looks random”.
\Image[https://www.ias.edu/sites/default/files/styles/portrait/public/images/scholars/757-1722863124.jpg.webp?itok=TMqaQze6]
{title=Portrait of <Avi Wigderson>}
{source=https://www.ias.edu/scholars/wigderson}
{width=240}
Back to article page
