18

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.

Gil Kalai
  • 6,033
  • 35
  • 73
  • 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? – András Salamon May 13 '15 at 14:51
  • 2
    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.) – Gil Kalai May 13 '15 at 18:24
  • Thanks Gil, this seems like a good reason to update my prior to "NO". – András Salamon May 13 '15 at 20:42
  • 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. – Stasys May 20 '15 at 20:46
  • 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..) – Gil Kalai May 21 '15 at 06:38
  • Dear Gil, I interpreted your Question 1 as "if a monotone boolean function $f$ cannot be $\epsilon$-approximated by a small monotone circuit, then $f$ has no small non-monotone circuits" (with "small" meaning "of polynomial size"). If the interpretation is correct, the function I mentioned only weakly approximates b-Clique function, and still requires large monotone circuits. – Stasys May 21 '15 at 08:28
  • "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}."This is interesting (reference?) but I am not sure it is relevent - namely I don't see that my notion of $\epsilon$-approximation is relevant to the result you mention. – Gil Kalai May 21 '15 at 16:39
  • Dear Gil, now I see the point: I just wrongly interpreted your question! We indeed have that every monotone circuit, which needs only to coincide with b-Clique on an extremely small, but special set of inputs, must be large. You, however, do not specify this subset of "hard" inputs, only its ratio $1-\epsilon$. This is a very interesting question. B.t.w. that result (on clique approximation) is Thm. 9.26 in my book. – Stasys May 21 '15 at 18:41

0 Answers0