期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Modular gates are known to be immune for the random
restriction techniques of Ajtai; Furst, Saxe, Sipser; and Yao and
Hastad. We demonstrate here a random clustering technique which
overcomes this difficulty and is capable to prove generalizations of
several known modular circuit lower bounds of Barrington, Straubing,
Therien; Krause and Pudlak; and others, characterizing symmetric
functions computable by small (MOD_p, AND_t, MOD_m) circuits.
Applying a degree-decreasing technique together with random restriction
methods for the AND gates at the bottom level, we also prove a hard
special case of the Constant Degree Hypothesis of Barrington, Straubing,
Therien, and some other related lower bounds for certain (MOD_p, MOD_m,
AND) circuits.
Most of the previous lower bounds on circuits with modular gates used
special definitions of the modular gates (i.e., the gate outputs one if
the sum of its inputs is divisible by m, or is not divisible by m), and
were not valid for more general MOD_m gates. Our methods are applicable
-- and our lower bounds are valid -- for the most general modular gates
as well.
