{"docId":9624,"paperId":7303,"url":"https:\/\/lmcs.episciences.org\/7303","doi":"10.46298\/lmcs-18(2:12)2022","journalName":"Logical Methods in Computer Science","issn":"","eissn":"1860-5974","volume":[{"vid":630,"name":"Volume 18, Issue 2"}],"section":[],"repositoryName":"arXiv","repositoryIdentifier":"1911.01479","repositoryVersion":9,"repositoryLink":"https:\/\/arxiv.org\/abs\/1911.01479v9","dateSubmitted":"2021-03-29 10:15:07","dateAccepted":"2022-03-29 12:27:14","datePublished":"2022-05-26 00:00:00","titles":["CC-circuits and the expressive power of nilpotent algebras"],"authors":["Kompatscher, Michael"],"abstracts":["We show that CC-circuits of bounded depth have the same expressive power as circuits over finite nilpotent algebras from congruence modular varieties. We use this result to phrase and discuss a new algebraic version of Barrington, Straubing and Th\\'erien's conjecture, which states that CC-circuits of bounded depth need exponential size to compute AND. Furthermore, we investigate the complexity of deciding identities and solving equations in a fixed nilpotent algebra. Under the assumption that the conjecture is true, we obtain quasipolynomial algorithms for both problems. On the other hand, if AND is computable by uniform CC-circuits of bounded depth and polynomial size, we can construct a nilpotent algebra in which checking identities is coNP-complete, and solving equations is NP-complete."],"keywords":["Mathematics - Rings and Algebras","Computer Science - Computational Complexity","08A70, 08A40"]}