4
$\begingroup$

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.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.