Size-Depth Tradeoffs and the Block-Respecting Model

The switching lemma gives a size lower bound as a function of depth for parity: a depth-$d$ circuit needs $2^{\Omega(n^{1/(d-1)})}$ gates. That bound is proved by restriction and it weakens as depth grows. A different line of work reaches a stronger conclusion by a different route — not by simplifying the circuit, but by observing that a shallow circuit cannot move much information between distant parts of its input, and then pricing the information movement with communication complexity.

The block-respecting restriction

Fix a partition of the $n$ input variables into $b$ blocks of size $n/b$ each. A circuit is block-respecting with respect to this partition if every gate’s fan-in either lies entirely inside one block or takes at most one wire from each block. In other words, a gate may look at many variables, but if it looks across blocks it may take only one wire per block, so the number of distinct blocks it reads equals its cross-block fan-in.

The model is artificial on its face. Its purpose is to make a specific quantity measurable: the number of wires that cross between blocks at each level. In an unrestricted circuit, a gate can read a thousand wires from one block and one from another, and the accounting of cross-block communication has no structure. Under the restriction, every gate that mixes blocks is a small communication step, and a level of the circuit becomes a round of a communication protocol.

The tradeoff theorem for the model states that a block-respecting circuit of depth $d$ and size $s$ computing a function whose block-communication complexity is high must satisfy a relation between $s$, $d$ and the number of blocks. The relation is not a single inequality but a family, one per function, obtained by instantiating the communication lower bound for that function.

Block-respecting circuit, depth 3, b blocks:

  level 1   gates read within blocks only          -> b independent computations
  level 2   gates take at most one wire per block  -> a small "summary" per block
  level 3   gates combine summaries                -> cross-block communication

  The wires at level 2 are the messages; their count is the communication cost.

Communication complexity as the accounting unit

The bridge between circuits and communication is a simulation. Given a block-respecting circuit of depth $d$, split the input into two halves $X$ and $Y$ at a block boundary. Each gate at the top of the circuit depends on both halves, and the set of wires crossing the split is a set of bits that the $X$-side must send to the $Y$-side. A protocol that simulates the circuit level by level, sending the cross-boundary wires at each level, decides the function with $d$ rounds and a number of bits equal to the total cross-boundary wire count.

The contrapositive is the lower bound. If the function requires $\Omega(c)$ bits of communication in $d$ rounds, then the circuit must have $\Omega(c)$ cross-boundary wires, and since each gate contributes at most one wire per block, the size is at least $\Omega(c)$.

Parity is the function where this bites hardest. Two-party parity — Alice holds $x$, Bob holds $y$, decide the parity of $x \oplus y$ — has deterministic communication complexity $n/2$ bits, because any protocol that is correct on all inputs must distinguish the $2^n$ possible parities, and the players’ messages are the only channel. So a depth-$d$ block-respecting circuit for parity needs $\Omega(n)$ wires crossing each block boundary, at every level, giving size $\Omega(n)$ per level and $\Omega(n d)$ overall — linear, not exponential.

That is weaker in exponent than the switching lemma’s $2^{\Omega(n^{1/(d-1)})}$ for constant depth, and it is not a defect of the communication method. The two results are about different circuit models: the switching lemma allows unrestricted fan-in at every gate, and the communication argument requires block-respecting structure. The value of the second is that it generalises to gates that the first cannot handle.

Why the model reaches threshold gates

A threshold gate on $k$ inputs is not a low-degree polynomial and has no bounded-width normal form, so both the switching lemma and the polynomial method fail on it. Communication complexity has no such difficulty, because the lower bound for a threshold function is a statement about how many bits must cross a cut, and that statement holds for any gate that computes the threshold.

The communication complexity of the “greater than” function — decide whether $x > y$ for $n$-bit numbers — is $n$ bits in the deterministic two-party model, since the comparison outcome depends on the most significant bit where the two differ and any protocol must locate it. A threshold gate on $2n$ inputs computes exactly that comparison when the inputs are arranged as two binary numbers, so a block-respecting circuit with a threshold gate at the top must send $\Omega(n)$ bits across the corresponding cut.

The result is a lower bound for block-respecting threshold circuits that is linear in $n$ per level, and it holds for depth growing with $n$ as long as the block structure is maintained. No comparable bound is known for unrestricted threshold circuits, and the gap between the two models is the measure of how much the block restriction costs.

Depth reduction, and what it preserves

The block-respecting model would be uninteresting if it were unrelated to ordinary circuits. Two reductions connect them.

Every ordinary circuit of depth $d$ and size $s$ can be converted to a block-respecting circuit of depth $O(d)$ and size $O(s \cdot b)$ for any partition into $b$ blocks, by routing each gate’s inputs through a small fan-in tree that collects at most one wire per block. The size increase is the price of the routing, and it is what makes the model a restriction rather than a different problem.

In the other direction, a block-respecting circuit is an ordinary circuit with a syntactic constraint, so its lower bounds apply to the restricted class and not to all circuits. This is the same shape as the monotone model: a restriction strong enough to prove something, with a conversion that shows the restriction is not free.

The depth-reduction side is where the model has been most productive. Valiant’s depth-reduction lemma shows that any circuit of fan-in two and size $s$ can be rearranged into a circuit of depth $O(\log s)$ with size $O(s)$ at the cost of allowing unbounded fan-in gates, which is why the class of functions with polynomial-size formulas equals $\mathrm{NC}^1$. The lemma does not preserve the block structure, so the communication lower bounds do not transfer to $\mathrm{NC}^1$; they transfer to the block-respecting subclass, and the question of whether that subclass is strictly smaller is open.

The three tradeoff regimes

Collecting the known results gives three regimes, and they are worth distinguishing because they are often conflated.

The unrestricted regime is the switching lemma’s: depth $d$, size $2^{\Omega(n^{1/(d-1)})}$ for parity. The bound is exponential for constant $d$ and trivial for $d = \log n$.

The block-respecting regime is the communication argument’s: depth $d$, size $\Omega(n d)$ for parity, linear in $n$ for every fixed $d$. The bound does not degrade with depth, which is its advantage, and it does not apply to unrestricted circuits, which is its cost.

The monotone regime is Razborov’s: no depth restriction, size $n^{\Omega(k)}$ for clique. The bound is exponential in a parameter of the function rather than in $n$, and it does not apply to circuits with negations.

No regime subsumes another. A function that is easy for one model may be hard for another, and the depth hierarchy is the framework in which the regimes are compared: each lower bound places a function outside some level of the hierarchy, and the level it places it outside depends on which restriction the proof needed.

The cost of a wire, measured

One number makes the communication view concrete. In a block-respecting circuit with $b$ blocks, a gate at level $\ell$ that reads across blocks contributes at most $b$ wires, one per block, and the total cross-block wire count at that level is at most $s_\ell \cdot b$ for $s_\ell$ gates at the level. The communication lower bound for the function forces that count to be at least $c$, so $s_\ell \ge c/b$. Summing over $d$ levels gives $s \ge d c / b$.

For parity with $b = 2$ blocks, $c = n/2$, the bound is $s \ge n d / 4$. For a partition into $\sqrt{n}$ blocks, $c$ stays $\Omega(n)$ across the central cut and $s \ge \Omega(n d / \sqrt{n}) = \Omega(d \sqrt{n})$, which is weaker; the choice of partition matters, and the strongest bound comes from the cut that maximises $c/b$. That maximisation is the only optimisation in the argument, and it is why the model’s results are stated per partition rather than globally.

The corresponding upper bound is not tight. A block-respecting circuit can compute parity in size $O(n)$ at any depth by routing the parity chain through the block structure, so the linear lower bound and the linear upper bound meet up to constants for the natural partition. The interesting questions in the model are therefore about functions whose communication complexity exceeds their circuit complexity, and those are exactly the functions for which the unrestricted circuit size is unknown.