18
$\begingroup$

Question 1: Is it true that for every polynomial $p(n)$ and $\epsilon >0$ there is a polynomial $q(n)$ such that every monotone Boolean function on $n$ variables that can be expressed by a Boolean circuit of size $p(n)$ can be $\epsilon$-approximated by a monotone Boolean circuit of size at most $q(n)$.

A function $f$ is $\epsilon$-approximated by a function $g$ if they agree on at least $(1-\epsilon)$ fraction of inputs.

We can ask a slightly more general question. Let $\mu_p$ denote the Bernoulli measure on $\{0,1\}^n$ where every variable is '1' with probability $p$. For a (non-constant) monotone function $f$ let $p_c(f)$ be the value such that $\mu_{p_c}(\{x: f(x)=1\})=1/2$.

Question 2: Is it true that for every polynomial $p(n)$ and $\epsilon >0$ there is a polynomial $q(n)$ such that every monotone Boolean function $f$ on $n$ variables, there is a Boolean function $g$ that can be expressed by a monotone Boolean circuit of size $q(n)$ such that for $p=p_c(f)$, $\mu_p(\{x: f(x) \ne g(x) \}) \le \epsilon$.

Of course, the instinctive thought is that the answers for both these question is NO. Is it known? Razborov famously proved that matching cannot be expressed by a monotone Boolean circuit of polynomial size. But matching can be approximated in its critical probability by the property that there are no isolated vertices and this property admits a monotone (low depth) circuit.

I asked the analog questions (Problems 1,2,3) for $AC^0$ and $TC^0$ in this blog post.

$\endgroup$
  • $\begingroup$ Why is NO the instinctive response? Monotone functions have all sorts of nice properties, so a priori this doesn't seem all that unlikely to me. Are you perhaps thinking of a counting argument? $\endgroup$ – András Salamon May 13 '15 at 14:51
  • 2
    $\begingroup$ Dear Andras, Alas, counting arguments are too weak for things of this kind. A YES answer will tell you that an argument that (1) some monotone NP-complete problem cannot be approximated by a polynomial size monotone circuit in the critical probability, automatically implies that (2) it cannot be approximated by a polynomial size circuit in the critical probability. (2) is a stronger statement than $NP \ne P$ but I dont regard (1) as hopeless. (You may think that the answer is YES but proving it is hopeless, but I find it easier to think that the answer is NO and its not beyond reach.) $\endgroup$ – Gil Kalai May 13 '15 at 18:24
  • $\begingroup$ Thanks Gil, this seems like a good reason to update my prior to "NO". $\endgroup$ – András Salamon May 13 '15 at 20:42
  • $\begingroup$ Gill, what about the fact that every monotone circuit separating graphs consisting of complete a-partite graphs with a > 32 from graphs consisting of b-cliques for a < b < n/32 must have size exponential in min{a,n/b}^{1/4}. The approximation density seems to be here enough (is it?) to say that your conjecture would definitely imply P!=NP. $\endgroup$ – Stasys May 20 '15 at 20:46
  • $\begingroup$ Dear Stasy, I don't see how the results you mention refer to Questions 1 and 2. (As I said, I also expect a 'no' answer..) $\endgroup$ – Gil Kalai May 21 '15 at 6:38

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.