Barrington–Straubing–Thérien conjecture on CC-circuit lower bounds

Let mNm \in \mathbb{N}, and let (Cn)nN(C_n)_{n \in \mathbb{N}} be a family of bounded-depth CC[m]\operatorname{CC}[m]-circuits computing AND\operatorname{AND}.

Barrington–Straubing–Thérien conjecture. There exists q>0q>0 such that CnC_n has size

2Ω(nq).2^{\Omega(n^q)}.

The conjecture asserts a strong lower bound for computing conjunction using only modular gates. The surrounding discussion identifies this as an open question; for non-prime mm, the source gives substantially smaller upper bounds, so the precise optimal exponent remains an additional issue.

Sources & referencesView supporting material

Primary source

Michael Kompatscher, “CC-circuits and the expressive power of nilpotent algebras”, arXiv:1911.01479 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.