Reducing randomization with random walks
Kent Quanrud · 74:21
This lecture shows how expander random walks amplify RP and BPP algorithms down to error \(\delta\) using only \(m + O(\log 1/\delta)\) random bits instead of the naïve \(m \cdot \log(1/\delta)\) from independent repe...