TR98-036 Authors: Vince Grolmusz, GĂˇbor Tardos

Publication: 30th June 1998 15:48

Downloads: 1683

Keywords:

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.