A Note on a Theorem of Razborov
David A. Mix Barrington · 1987
RAZBOROV [RA86] HAS RECENTLY PROVED THAT A CONSTANT DEPTH UNBOUNDED FAN- IN CIRCUIT WITH `AND'' AND `PARITY'' GATES REQUIRES EXPONENTIAL SIZE TO COMPUTE THE MAJORITY FUNCTION, AFFIRMING A FIVE YEAR OLD CONJECTURE [FSS81]. HERE WE EXTEND HIS TECHNIQUE TO SHOW THE SAME RESULT FOR CIRCUITS WITH `AND'' GATES AND `MOD-P'' GATES FOR PRIME P, WHERE A MOD-P GATE OUTPUTS ONE IF THE SUM MOD P OF ITS (BOOLEAN) INPUTS IS NONZERO AND ZERO OTHERWISE.