<p>Here is an example from low degree testing literature: <a href="https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/BSVW03/BSVW03.pdf" rel="nofollow noreferrer">https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/BSVW03/BSVW03.pdf</a>.</p>

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

CC BY-SA 4.0
2020-04-19T12:42:14.717Z
2020-04-19T12:42:14.717Z
A.2
<p>I read the book the Probabilistic Method and the lecture note Pseudorandomness to study techniques of derandomization and completed some of exercises.</p>

<p>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.</p>

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

CC BY-SA 4.0
2020-04-20T17:42:46.613Z
Cross-posted: https://cs.stackexchange.com/q/124429/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
<derandomization>
Examples for derandomization via small sample spaces
Bubble
# Examples for derandomization via small sample spaces

(Asked by: username_0 on 2020-04-18)

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.

**Tags:** derandomization
> **Comments:**
> **username_1**: Cross-posted: https://cs.stackexchange.com/q/124429/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  

---

## 1 answers

### Answer by username_2 on 2020-04-19. Score: 2 | Accepted answer

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.


---

