# What does it mean to fool a function?

In computer science papers, I see about the term 'fooling' a function.

What does it mean to fool a function against a particular complexity class? Why is it important?

• Never came across that expression, can you link one of those papers? Nov 20 '15 at 23:50
• This cstheory thread might be helpful. Nov 21 '15 at 5:29
• When asking a question like this, please include in the question some information about the context in which you saw the phrase.
– D.W.
Nov 21 '15 at 7:05
• @G.Bach This is actually quite a central concept in computational complexity. Nov 21 '15 at 14:10

Let's consider a randomized algorithm for some decision problem. The algorithm makes use of some random bits $r_1,\ldots,r_n$. In practice, we run this algorithm by using an "informal" pseudorandom number generator, perhaps injecting some physical randomness. Perhaps we can do the same formally?
The best case scenario is that there exists some really complex sequence of random bits that "looks random" for every efficient algorithm; the complexity of the sequence should grow with the complexity of the algorithm, but we want the algorithm generating the sequence to be efficient (though perhaps less efficient than the algorithm itself). While one sequence is perhaps too much to ask for (how exactly would it work, anyway?), but we can hope that a simpler distribution causes the randomized algorithm to act in roughly the same way: $$\Pr[A(x,\mathbf{r})] \approx \Pr[A(x,\mathbf{g})],$$ where $A$ is the randomized algorithm, $x$ is the input, $\mathbf{r}$ is a vector of random bits generated uniformly at random, and $\mathbf{g}$ is the same generated pseudorandomly. What we aim for is for $\mathbf{g}$ not only to be generated efficiently, but moreover we want the support of the distribution to have polynomial size. By enumerating all possible values of $\mathbf{g}$, we can derandomize $A$.
Now back to your question. A pseudorandom sequence $\mathbf{g}$ (or a collection of such sequences) is said to fool an algorithm $A$ if $\Pr[A(x,\mathbf{r})] \approx \Pr[A(x,\mathbf{g})]$. It fools a complexity class if it fools all algorithms in this class.