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?

  • 5
    $\begingroup$ Never came across that expression, can you link one of those papers? $\endgroup$
    – G. Bach
    Nov 20 '15 at 23:50
  • 1
    $\begingroup$ This cstheory thread might be helpful. $\endgroup$ Nov 21 '15 at 5:29
  • 2
    $\begingroup$ When asking a question like this, please include in the question some information about the context in which you saw the phrase. $\endgroup$
    – D.W.
    Nov 21 '15 at 7:05
  • $\begingroup$ @G.Bach This is actually quite a central concept in computational complexity. $\endgroup$ Nov 21 '15 at 14:10
  • $\begingroup$ @YuvalFilmus Thanks for the reply, I might've forgotten about this otherwise! $\endgroup$
    – G. Bach
    Nov 21 '15 at 19:27

Let's start with some background. The context is derandomization:

Given a randomized algorithm, is there an equivalent deterministic algorithm?

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.

Another context in which similar concepts appear is cryptography. For example, in cryptography a pseudorandom number generator is defined (roughly) as an efficient algorithm producing a long random sequence which fools every polynomial time distinguisher (a distinguisher a machine trying to distinguish the YES case (truly random) from the NO case (pseudorandom)).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy