<p><strong>Question 1:</strong>  Is it true that for every polynomial $p(n)$ and $\epsilon &gt;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 <em>monotone</em> Boolean circuit of size at most $q(n)$. </p>

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

<p>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$.</p>

<p><strong>Question 2:</strong>  Is it true that for every polynomial $p(n)$ and $\epsilon &gt;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$. </p>

<p>Of course, the instinctive thought is that the answers for both these question is <strong>NO</strong>. 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.</p>

<p>I asked the analog questions (Problems 1,2,3) for $AC^0$ and $TC^0$ in <a href="https://gilkalai.wordpress.com/2010/02/10/noise-stability-and-threshold-circuits/">this blog post</a>.</p>

CC BY-SA 3.0
2015-05-13T14:51:58.367Z
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
CC BY-SA 3.0
2015-05-13T18:24:23.400Z
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
CC BY-SA 3.0
2015-05-13T20:42:33.823Z
Thanks Gil, this seems like a good reason to update my prior to "NO".
András Salamon
CC BY-SA 3.0
2015-05-20T20:46:28.233Z
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
CC BY-SA 3.0
2015-05-21T06:38:03.707Z
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
CC BY-SA 3.0
2015-05-21T08:28:49.703Z
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
CC BY-SA 3.0
2015-05-21T16:39:57.767Z
"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
CC BY-SA 3.0
2015-05-21T18:41:54.803Z
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](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html).
Stasys
<cc.complexity-theory><circuit-complexity><pr.probability>
Are monotone Boolean functions in P well-approximated by monotone polynomial-size circuits?
Gil Kalai
# Are monotone Boolean functions in P well-approximated by monotone polynomial-size circuits?

(Asked by: username_0 on 2015-05-13)

**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](https://gilkalai.wordpress.com/2010/02/10/noise-stability-and-threshold-circuits/).

**Tags:** cc.complexity-theory, circuit-complexity, pr.probability
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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.)  
> **username_1**: Thanks Gil, this seems like a good reason to update my prior to "NO".  
> **username_2**: 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.  
> **username_0**: 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..)  
> **username_2**: 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.  
> **username_0**: "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.  
> **username_2**: 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](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html).  

---

## 0 answers

