<p>Let $f$ be a Boolean function on $n$-bits. Let $Z = f^{-1}(0) \subseteq 2^n$. Let $C$ be circuit on n bits and of size $m$ and gates $g_1, \ldots, g_m$. $g_i$ also denotes the function on $n$-bits computed by subcircuit with $g_i$ as the last gate. The first $n$ gates are for the input $x_1, \ldots, x_n$. The goal is to show that $C$ of size $m$ cannot compute $f$. Consider all computations of $C$ on inputs from $Z$. A computation assigns values to outputs of gates. Let $B$ be the Boolean algebra of $P(Z)$.</p>

<p>The idea is to consider for any function  $g$ on $n$-bits how well it approximates $f$ on $Z$. Let $||g|| = \{w \in Z \mid g(w) \neq 0 \}$.</p>

<p>For an ultrafilter $F \subseteq B$ we can define a new computation by ultraproduct from it: $c(g_i) = 0$ iff $||g_i|| \not\in F$. Because an ultrafilter is essentially a set of consistent computations for 0 values the resulting $c$ is a valid computation. It would follow that $f(c_1, \ldots, c_n) = 0$. We created a new computation from existing ones. Since all ultrafilters on finite sets are principal $c_1,\ldots,c_n \in Z$. This works for any circuit, we have not exploited the fact that the circuit is of size $m$. </p>

<p>The next idea is now to exploit the finiteness of the circuit to construct a new input that is outside $Z$ and $f(w) \neq 0$ but the circuit does not notice because of its limited size and therefore still outputs 0. So it does not compute $f$.</p>

<p>We need to relax the definition of ultrafilter so that we can get an input outside $Z$. In place of ultrafilters we use upward-closed subsets of $B$ ($a \in F$ and $a \subseteq b$ implies $b \in F$) that preserve meets($a,b \in F$ implies $a \cap b \in F$).</p>

<p>Let $W_F = \{w \in 2^n \mid w_i = 0 \to ||\lnot x_i|| \in F, w_i \neq 0 \to ||x_i|| \in F\}$. $W_F$ is the set of inputs consistent with $F$. If $F$ is prime ($a \cup b \in F$ implies $a \in F$ or $b \in F$) and nonfull ($\emptyset \not\in F$) then for each $i$, $F$ contains either  $||x_i||$ or $||\lnot x_i||$ and $W_F$ contains only a single input.</p>

<p>We are going to relax preservation of meets. In place of all meets in the Boolean algebra we will preserve a small number of them. Let $|f|$ be the smallest number $k$ of meets $M = (a_1 \cap b_1, \ldots, a_k \cap b_k)$ such that for all upward-closed, nonfull, $M$-preserving $F$, $W_F \subseteq Z$. </p>

<p>Let $m$ be the circuit complexity of $f$. Razborov proved that $\frac{1}{2}|f| \leq m \leq O(|f|^3 + n^3)$.</p>

<p>Note that this inequality holds for <em>all</em> functions. To prove a circuit size lower bound $m$ show that for all $m$-meets $M$, there is a $F$ that satisfies the conditions but its $W_F$ is not contained in $Z$. Moreover any strong circuit lower bound can be proven by this method because of the second inequality.</p>

<p>The actual part of a circuit lower bound proof is to show that for given $m$, for any $m$-meets there is such an $F$. In the case of monotone circuits the condition about $W_F$ simplifies to $w_i \neq 0 \to ||x_i|| \in F$ so coming up with $F$ is easier. </p>

<p>Alexander Razborov, On the Method of Approximation, 1989.
<a href="http://people.cs.uchicago.edu/~razborov/files/approx.pdf" rel="nofollow noreferrer">pdf</a></p>

<p>Mauricio Karchmer, On Proving Lower Bounds for Circuit Size, 1995.</p>

<p>Tim Gowers, Razborov's method of approximation, 2009. <a href="https://gowers.files.wordpress.com/2009/05/razborov2.pdf" rel="nofollow noreferrer">pdf</a></p>

CC BY-SA 3.0
2017-08-19T18:14:17.873Z
What is $|f|$? Is it $k$?
Emil Jeřábek
CC BY-SA 3.0
2017-08-19T03:59:50.533Z
2017-08-20T18:53:23.093Z
2017-08-20T18:53:23.093Z
Bob
<p><em>Disclaimer</em>: This is only a high-level overview intended to give some intuition to the methods used in Blum's recent paper.</p>

<p>I will attempt to use notation that is closer to what is used in the aforementioned paper.</p>

<p>Let $f$ be a Boolean function on $n$ variables $x_1,\dots,x_n$. Suppose we want to prove that any Boolean network computing $f$ has large size.</p>

<p>Given some Boolean network $\beta$ computing $f$ at its output node, consider the following process.</p>

<ol>
<li>Order the gates in $\beta$ according to some topological order $g_1,g_2,\dots,g_m$ where the last node is the output node.</li>
<li>For each time step $t=1,\dots,m$ we will <em>approximate</em> the function computed at gate $g_t$ by a “simple” function $f_{g_t}$. This approximation may change the functions computed at nodes downstream of $g_t$ (in particular, the function at the output node $g_m$ may have changed).</li>
</ol>

<p>At the end of this process, we will have approximated the function computed at $g_m$ by a simple function $f_{g_m}$.</p>

<p>Next construct a group of test inputs $T\subseteq \{0,1\}^n$.</p>

<p>Suppose we can prove the following statements:</p>

<ul>
<li>The approximation of each individual node is good (i.e., at most $e$-many mistakes are introduced on inputs from $T$ at each approximation step).</li>
<li>No simple function approximates $f$ well (i.e., for any simple function $f_{g_m}$, we have $f_{g_m}\neq f$ on more than a $d$-fraction of $T$).</li>
</ul>

<p>Then by simply counting the number of errors we get that $\beta$ must have at least $\tfrac{d\lvert T\rvert}{e}$-many gates.</p>

<p>If this approximation scheme can be shown to work for any network $\beta$ computing the function $f$, then we arrive at a lower bound for the circuit complexity of $f$.</p>

CC BY-SA 3.0
2017-08-24T02:08:57.923Z
I don't think this answers the question, the question doesn't ask anything about that draft.
Kaveh
CC BY-SA 3.0
2017-08-24T05:50:57.700Z
@Kaveh that is fair. I may have incorrectly assumed, due to the timing of the question, that it was asking about this technique in relation to the paper.
alw
CC BY-SA 3.0
2017-08-22T12:10:10.640Z
2017-08-22T12:10:10.640Z
alw
<p>What is Razborov's method of approximations? Can someone give a high-level overview and the intuition behind it?</p>

CC BY-SA 3.0
2017-08-19T14:01:52.040Z
If you want to watch a lecture on the topic, Tim Gowers covers this in his complexity theory lectures: https://sms.cam.ac.uk/collection/545358
Robin Kothari
<cc.complexity-theory><circuit-complexity>
High-level overview of Razborov's method of approximations
Alex
# High-level overview of Razborov's method of approximations

(Asked by: username_0 on 2017-08-19)

What is Razborov's method of approximations? Can someone give a high-level overview and the intuition behind it?

**Tags:** cc.complexity-theory, circuit-complexity

> **Comments:**
> **username_1**: If you want to watch a lecture on the topic, Tim Gowers covers this in his complexity theory lectures: https://sms.cam.ac.uk/collection/545358  

---

## 2 answers

### Answer by username_2 on 2017-08-19. Score: 7

Let $f$ be a Boolean function on $n$-bits. Let $Z = f^{-1}(0) \subseteq 2^n$. Let $C$ be circuit on n bits and of size $m$ and gates $g\_1, \ldots, g\_m$. $g\_i$ also denotes the function on $n$-bits computed by subcircuit with $g\_i$ as the last gate. The first $n$ gates are for the input $x\_1, \ldots, x\_n$. The goal is to show that $C$ of size $m$ cannot compute $f$. Consider all computations of $C$ on inputs from $Z$. A computation assigns values to outputs of gates. Let $B$ be the Boolean algebra of $P(Z)$.

The idea is to consider for any function $g$ on $n$-bits how well it approximates $f$ on $Z$. Let $||g|| = \{w \in Z \mid g(w) \neq 0 \}$.

For an ultrafilter $F \subseteq B$ we can define a new computation by ultraproduct from it: $c(g\_i) = 0$ iff $||g\_i|| \not\in F$. Because an ultrafilter is essentially a set of consistent computations for 0 values the resulting $c$ is a valid computation. It would follow that $f(c\_1, \ldots, c\_n) = 0$. We created a new computation from existing ones. Since all ultrafilters on finite sets are principal $c\_1,\ldots,c\_n \in Z$. This works for any circuit, we have not exploited the fact that the circuit is of size $m$.

The next idea is now to exploit the finiteness of the circuit to construct a new input that is outside $Z$ and $f(w) \neq 0$ but the circuit does not notice because of its limited size and therefore still outputs 0. So it does not compute $f$.

We need to relax the definition of ultrafilter so that we can get an input outside $Z$. In place of ultrafilters we use upward-closed subsets of $B$ ($a \in F$ and $a \subseteq b$ implies $b \in F$) that preserve meets($a,b \in F$ implies $a \cap b \in F$).

Let $W\_F = \{w \in 2^n \mid w\_i = 0 \to ||\lnot x\_i|| \in F, w\_i \neq 0 \to ||x\_i|| \in F\}$. $W\_F$ is the set of inputs consistent with $F$. If $F$ is prime ($a \cup b \in F$ implies $a \in F$ or $b \in F$) and nonfull ($\emptyset \not\in F$) then for each $i$, $F$ contains either $||x\_i||$ or $||\lnot x\_i||$ and $W\_F$ contains only a single input.

We are going to relax preservation of meets. In place of all meets in the Boolean algebra we will preserve a small number of them. Let $|f|$ be the smallest number $k$ of meets $M = (a\_1 \cap b\_1, \ldots, a\_k \cap b\_k)$ such that for all upward-closed, nonfull, $M$-preserving $F$, $W\_F \subseteq Z$.

Let $m$ be the circuit complexity of $f$. Razborov proved that $\frac{1}{2}|f| \leq m \leq O(|f|^3 + n^3)$.

Note that this inequality holds for *all* functions. To prove a circuit size lower bound $m$ show that for all $m$-meets $M$, there is a $F$ that satisfies the conditions but its $W\_F$ is not contained in $Z$. Moreover any strong circuit lower bound can be proven by this method because of the second inequality.

The actual part of a circuit lower bound proof is to show that for given $m$, for any $m$-meets there is such an $F$. In the case of monotone circuits the condition about $W\_F$ simplifies to $w\_i \neq 0 \to ||x\_i|| \in F$ so coming up with $F$ is easier.

username_0ander Razborov, On the Method of Approximation, 1989.
[pdf](http://people.cs.uchicago.edu/~razborov/files/approx.pdf)

Mauricio Karchmer, On Proving Lower Bounds for Circuit Size, 1995.

Tim Gowers, Razborov's method of approximation, 2009. [pdf](https://gowers.files.wordpress.com/2009/05/razborov2.pdf)

> **Comments:**
> **username_3**: What is $|f|$? Is it $k$?  

---

### Answer by username_4 on 2017-08-22. Score: 0

*Disclaimer*: This is only a high-level overview intended to give some intuition to the methods used in Blum's recent paper.

I will attempt to use notation that is closer to what is used in the aforementioned paper.

Let $f$ be a Boolean function on $n$ variables $x\_1,\dots,x\_n$. Suppose we want to prove that any Boolean network computing $f$ has large size.

Given some Boolean network $\beta$ computing $f$ at its output node, consider the following process.

1. Order the gates in $\beta$ according to some topological order $g\_1,g\_2,\dots,g\_m$ where the last node is the output node.
2. For each time step $t=1,\dots,m$ we will *approximate* the function computed at gate $g\_t$ by a “simple” function $f\_{g\_t}$. This approximation may change the functions computed at nodes downstream of $g\_t$ (in particular, the function at the output node $g\_m$ may have changed).

At the end of this process, we will have approximated the function computed at $g\_m$ by a simple function $f\_{g\_m}$.

Next construct a group of test inputs $T\subseteq \{0,1\}^n$.

Suppose we can prove the following statements:

* The approximation of each individual node is good (i.e., at most $e$-many mistakes are introduced on inputs from $T$ at each approximation step).
* No simple function approximates $f$ well (i.e., for any simple function $f\_{g\_m}$, we have $f\_{g\_m}\neq f$ on more than a $d$-fraction of $T$).

Then by simply counting the number of errors we get that $\beta$ must have at least $\tfrac{d\lvert T\rvert}{e}$-many gates.

If this approximation scheme can be shown to work for any network $\beta$ computing the function $f$, then we arrive at a lower bound for the circuit complexity of $f$.

> **Comments:**
> **username_5**: I don't think this answers the question, the question doesn't ask anything about that draft.  
> **username_4**: @username_5 that is fair. I may have incorrectly assumed, due to the timing of the question, that it was asking about this technique in relation to the paper.  

---

