Barrington–Straubing–Thérien conjecture on CC-circuit lower bounds
Barrington–Straubing–Thérien conjecture on CC-circuit lower bounds
Let , and let be a family of bounded-depth -circuits computing .
Barrington–Straubing–Thérien conjecture. There exists such that has size
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 , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.