Explicit linear circuit lower bounds

Take two bits. Return 1 in the first output when exactly one input is 1, and otherwise return 0; copy the second input to the second output. On inputs 1 and 1 this gives outputs 0 and 1. One exclusive-or operation computes the first output.

Can we describe a growing family of bit transformations efficiently and prove that every circuit computing them needs more than any fixed multiple of the number of inputs? The circuit may reuse intermediate results and cancel a bit that appears twice.[1]

Can we efficiently specify bit transformations that provably require more than any constant number of two-input operations per input, even when a circuit reuses and cancels intermediate sums? The two-bit example returns $y_1=x_1\oplus x_2$ and $y_2=x_2$; a single XOR gate computes the first output and a wire copies the second.

An XOR gate adds its two inputs modulo two. Cancellation is legal: $(x_1\oplus x_2)\oplus x_2=x_1$. Each transformation is multiplication by an $n\times n$ matrix over the two-element field. An explicit family supplies such a matrix by a polynomial-time construction for each size.

The sought superlinear lower bound means that the minimum gate count divided by $n$ tends to infinity as $n$ grows. The circuit is an unrestricted acyclic network of two-input XOR gates with all outputs required. A lower bound that forbids cancellation does not suffice.[1] [2]

Existence arguments do not identify such a matrix family with a proved unrestricted lower bound.[2]

Counting arguments show that hard binary transformations exist, but they do not give the efficiently constructible family with a proved unrestricted superlinear lower bound sought here. Results for cancellation-free circuits constrain what intermediate computations can do, leaving the unrestricted target open.

Raz’s July 2026 revision describes conditional barriers for specified forms of natural proofs under cryptographic assumptions. Those statements are restrictions on particular proof approaches under assumptions, not an unconditional claim that all lower-bound methods must fail.[1] [2]

A transformation can list which inputs contribute to each output, but that list does not tell us the cost of computing all outputs together. Shared intermediate sums can save operations. The question asks whether one can exhibit a specific family whose cost remains large despite every such reuse and cancellation.[1] [2]

Because an intermediate XOR sum can feed several later gates, a circuit is a shared computation rather than a separate computation for each matrix row. Cancellation can also remove an input from a later sum. These mechanisms explain why counting nonzero matrix entries does not determine the minimum gate count.

The explicitness requirement adds a second connection: showing that most transformations are costly is an existence argument, while proving a named, efficiently generated family costly requires a property one can analyze. The target probes how structural knowledge of a linear map can control all circuits that realize it.[1] [2]