Random Restriction and Circuit Lower Bounds

The class \aczero\ consists of all uniform families of circuits of constant depth and polynomial size, with unlimited-fanin AND and OR gates. NOT gates are allowed only at the inputs. The class \saczero\ is the semi-unbounded version of \aczero\ i.e., AND gates have constant fan-in.

The class AC^0 consists of all uniform families of circuits of constant depth and polynomial size, with unlimited-fanin AND and OR gates. NOT gates are allowed only at the inputs. The class SAC^0 is the semi-unbounded version of AC^0 i.e., AND gates have constant fan-in. In the class NC^0  both AND and OR gates have constant fan-in. The following strict hierarchy is known.

For all prime numbers p, NC^0 \subsetneq SAC^0 \subsetneq AC^0 \subsetneq AC^0[p] \subsetneq TC^0.

Todays post is is about the following theorem.

Theorem : SAC^0 \subsetneq AC^0

Proof : AC^0 is closed under complementation and SAC^0 is not.

Exercise : Prove that SAC^0 is not closed under complementation.

Recently I came up with an alternate proof of the above theorem using the technique of random restriction of Furst, Saxe and Sipser [FSS’81]. I think my proof can be given as a cool homework problem in introductory complexity theory course. Here it goes…..

Let G(V,E) be a directed simple graph (i.e., G does not have self-loops or multi-edges) with |V|=n and |E|=m. Let indegree(v) represent the indegree of a vertex v \in V. Motivated by cycle languages, we define the language Positive Indegree as follows :

Positive Indegree = \{ <G(V,E)>\ |\ indegree(v)\ \geq\ 1\ \forall\ v\ \in\ V\}.

G is represented as (x_1,y_1),\dots,(x_m,y_m) where each x_i and y_i is in \{1,2,\dots,n\} encoded as binary strings. The meaning of (x,y) is that there is a directed edge from x to y. We may assume that circuits computing Positive Indegree will have m = O(n^2) binary inputs in a prespecified order.

Exercise : Positive Indegree \in AC^0.

Lemma : If a CNF or a DNF computes Positive Indegree, then
  • each term includes at least n-1 variables, and
  • there are at least n terms.

Hence there is no SAC^0 circuit of depth two for Positive Indegree.

    Proof : We will prove this lemma for CNFs. The proof for DNFs is similar. Let \mathcal{C} be a CNF circuit computing Positive Indegree.
    • Assume that \mathcal{C} has some term t that depends on less than n-1 variables. Then when all inputs to t are 0, t outputs 0 and hence \mathcal{C} outputs 0. Consider the graph H consisting of a cycle on n-1 vertices (say v_1,\dots,v_{n-1}) and an isolated vertex v_n. Note that H \notin Positive Indegree. Let H_i be the graph obtained by adding the edge (v_i,v_n) to H. Now H_i \in Positive Indegree for 1 \leq i \leq n-1. If t does not depend on all variables of the form (v_i,v_n) then \mathcal{C} outputs 0 for some H_i, which is a contradiction.
    • Consider the graph F^i consisting of a cycle on n-1 vertices (these are the vertices from v_1,\dots,v_{n} except v_i) and an isolated vertex v_i. \mathcal{C} must output zero on F^i for 1 \leq i \leq n. \mathcal{C} outputs 0 only when one of the terms (OR gates) outputs zero. But each OR gate outputs 0 on exactly one assignment of the input variables, Hence, \mathcal{C} must have at least n terms.
    Restriction : Let \mathcal{C} be a circuit computing Positive Indegree. Setting an input of \mathcal{C} to 0 (resp. 1) corresponds to deleting (resp. contracting) the corresponding edge from the input graph G.

    Observation : If some of the inputs of \mathcal{C} are restricted to 0 or 1, the resulting circuit still computes Positive Indegree, albeit on a smaller graph.

    Theorem : Positive Indegree \notin SAC^0.
    Proof : We assume that there is an SAC^0 circuit (say \mathcal{C} of some constant depth d) computing Positive Indegree and derive a contradiction. Using the random restriction technique of [FSS’81] we squash \mathcal{C} down to depth d-1 while still computing Positive Indegree on many variables. This squashing still preserves the constant fanin of AND gates. We repeat this method d-2 times to obtain an SAC^0 circuit of depth 2 with constant AND fanin, which contradicts the previous lemma.

    Corollary : SAC^0 \subsetneq AC^0.

    References :
    • [FSS’81] Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. In FOCS, pages 260–270, 1981.