I read the book the Probabilistic Method and the lecture note Pseudorandomness to study techniques of derandomization and completed some of exercises.

I'm trying the technique of "Derandomization" for some algorithms, and I find some samples using the derandomization via small sample spaces and feel very interested.

To deepen the impression on derandomization via small sample space, I want to see more papers using that.


1 Answer 1


Here is an example from low degree testing literature: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/BSVW03/BSVW03.pdf.

High-level summary: Consider BLR linearity testing algorithm that given oracle access to a function $f:\mathbb{F}^m \rightarrow \mathbb{F}$, first, samples $x,y$ uniformly randomly from $\mathbb{F}^m$ and then tests if $f(x)+f(y)=f(x+y)$ by querying the function at required points. This paper reduces the amount of randomness usage by sampling $y$ from an epsilon-biased set instead of sampling from the entire space.


Not the answer you're looking for? Browse other questions tagged or ask your own question.