# 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^{0}

For a fixed positive integer [math]d[/math], let AC^{0}_{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^{0} is the union of AC^{0}_{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!