2 problems

0 votes0 replies0 views
Barrington–Straubing–Thérien conjecture on CC-circuit lower bounds
Barrington–Straubing–Thérien conjecture. There exists $q>0$ such that $C_n$ has size
Conjectureopencircuit-complexity complexity-lower-bounds modular-circuitsarXiv posted 2 days ago
0 votes0 replies0 views
Smolensky's conjecture on modular circuit lower bounds
Smolensky's conjecture. Such circuits cannot compute $\operatorname{MOD}_q$ in sub-exponential size.
Conjectureopencircuit-complexity complexity-lower-bounds modular-circuitsarXiv posted 2 days ago

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