9
$\begingroup$

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

$\endgroup$
1

2 Answers 2

6
$\begingroup$

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.

Alexander Razborov, On the Method of Approximation, 1989. pdf

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

Tim Gowers, Razborov's method of approximation, 2009. pdf

$\endgroup$
1
  • 3
    $\begingroup$ What is $|f|$? Is it $k$? $\endgroup$ Aug 19, 2017 at 18:14
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I don't think this answers the question, the question doesn't ask anything about that draft. $\endgroup$
    – Kaveh
    Aug 24, 2017 at 2:08
  • $\begingroup$ @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. $\endgroup$
    – alw
    Aug 24, 2017 at 5:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.