Circuit complexity

A circuit is a model for computing Boolean functions, in which functions are computed using a sequence of elementary operations, called gates. Different circuit models exist, depending on how they restrict the width, depth, size, and pool of usable gates. The circuit size, or circuit complexity of a family of Boolean functions [math]\{f_n\}_n[/math], deals with how the size of the smallest circuit computing [math]f_n[/math] grows as [math]n \to \infty[/math].

General definition

A circuit which computes a Boolean function is a tuple [math](L, G)[/math], where

• [math]L[/math] is a set of gate labels, each of which is a function from [math]\{-1,1\}^{i}[/math] to [math]\{-1,1\}[/math] for some non-negative integer [math]i[/math] (where [math]i[/math] represents the number of inputs to the gate), and
• [math]G[/math] is a labelled directed acyclic graph with labels from [math]L[/math].

The vertices of the graph are called gates. For each gate [math]g[/math] of in-degree [math]i[/math], the gate [math]g[/math] can be labeled by an element [math]\ell[/math] of [math]L[/math] if and only if [math]\ell[/math] is defined on [math]\{-1,1\}^{i}[/math].

Terminology

The gates of in-degree 0 are called inputs or leaves. The gates of out-degree 0 are called outputs. If there is an edge from gate [math]g[/math] to gate [math]h[/math] in the graph [math]G[/math] then [math]h[/math] is called a child of [math]g[/math]. We suppose there is an order on the vertices of the graph, so we can speak of the [math]k[/math]th child of a gate when [math]k[/math] is less than the out-degree of the gate.

The size of a circuit is the number of nodes of a circuit. The depth of a gate [math]g[/math] is the length of the longest path in [math]G[/math] beginning at [math]g[/math] up to an output gate. In particular, the gates of out-degree 0 are the only gates of depth 1. The depth of a circuit is the maximum depth of any gate.

Level [math]i[/math] is the set of all gates of depth [math]i[/math]. A levelled circuit is a circuit in which the edges to gates of depth [math]i[/math] comes only from gates of depth [math]i + 1[/math] or from the inputs. In other words, edges only exist between adjacent levels of the circuit. The width of a levelled circuit is the maximum size of any level.

Evaluation

The exact value [math]V(g)[/math] of a gate [math]g[/math] with in-degree [math]i[/math] and label [math]l[/math] is defined recursively for all gates [math]g[/math].

[math] V(g) = \begin{cases} l & \text{if } g \text{ is an input} \\ l(V(g_1), \dotsc, V(g_i)) & \text{otherwise,} \end{cases} [/math]

where each [math]g_j[/math] is a parent of [math]g[/math].

The value of the circuit is the value of each of the output gates.

AC⁰

For a fixed positive integer [math]d[/math], let AC⁰_d be all families of circuits with depth exactly [math]d[/math], size polynomial in [math]n[/math], unlimited fan-in AND and OR gates, and NOT gates at the inputs. The class AC⁰ is the union of AC⁰_d over all [math]d[/math], i.e it is the class of all constant depth, polynomial-sized circuits which use AND and OR gates.

Properties

• TODO: There is vast literature on the relation between different complexity measures: Bounded depth circuit size, Fourier tail, noise sensitivity, etc. Start citing, please!