Let $X$ be a set of $n$-bit Boolean functions of the form $f:\{0,1\}^n\rightarrow \{0,1\}$. For instance, $X$ could be the set of $n$-bit monotone Boolean functions, or the set of $n$-bit functions computable by circuits of size $s$, or the set of n-bit Boolean functions computable by branching programs of width $w$, etc.

What are the implications of an efficient algorithm that samples a function from $X$ uniformly at random? Examples of concrete questions are the following.

  1. Does sampling functions from $X$ uniformly at random in time $n^{O(1)}$, implies the existence of pseudorandom generators of small seed-length that fool all functions in $X$?
  2. I remember of having read somewhere that the natural proofs method does not encompass Razborov lower bounds for monotone Boolean circuits because one does not know how to sample n-bit monotone Boolean functions efficiently. Why would such a sampling algorithm imply lower bounds based on cryptographic assumptions?

Obs: Note that sampling uniformly from X is not the same as sampling uniformly from the circuits representing function from X, since many circuits may represent to the same function.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.