Superlinear circuit lower bounds for the permanent

The problem asks whether exact computation of the permanent by unrestricted arithmetic circuits necessarily requires more than linear size. The retrieved literature contains substantial lower bounds only after imposing restrictions on the circuit model.

Known results

• Arithmetic formulas require size $\Omega\!\left(n^4/\log n\right)$ over characteristic-zero fields, but formulas are a restricted subclass of circuits.
• Symmetric arithmetic circuits for the permanent have nearly exponential lower bounds over fields of characteristic different from $2$, again under a model restriction.
• Under depth and uniformity restrictions, the permanent has no polynomial-size circuits of sufficiently small depth.
• No unconditional superlinear lower bound for unrestricted arithmetic circuits computing the permanent was found.

Current status (as of September 2026): The unrestricted problem remains open; only restricted-model lower bounds are recorded, with no claimed resolution found.