Complexity of Modular Circuits
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski · 2022
We study how the complexity of modular circuits computing AND depends on the depth of the circuits and the prime factorization of the modulus they use. In particular our construction of subexponential circuits of depth 2 for AND helps us to classify (modulo Exponential Time Hypothesis) modular circuits with respect to the complexity of their satisfiability. We also study a precise correlation between this complexity and the sizes of modular circuits realizing AND. In particular we use the superlinear lower bound from [10] to check satisfiability of CC0 circuits in probabilistic 2O(n/ε(n)) time, where ε is some extremely slowly increasing function. Moreover we show that AND can be computed by a polynomial size modular circuit of depth 2 (with O(log n) random bits) providing a probabilistic computational model that can not be derandomized.