## Computer Science

# Exponential sums and circuits with a single threshold gate and mod-gates

## Document Type

Article

## Abstract

Consider circuits consisting of a threshold gate at the top, Modm gates at the next level (for a fixed m), and polylog fan-in AND gates at the lowest level. It is a difficult and important open problem to obtain exponential lower bounds for such circuits. Here we prove exponential lower bounds for restricted versions of this model, in which each Modm-of-AND subcircuit is a symmetric function of the inputs to that subcircuit. We show that if q is a prime not dividing m, the Modq function requires exponential-size circuits of this type. This generalizes recent results and techniques of Cai et al. [CGT] (which held only for q = 2) and Goldmann (which held only for depth two threshold over Modm circuits). As a further generalization of the [CGT] result, the symmetry condition on the Modm subcircuits can be relaxed somewhat, still resulting in an exponential lower bound. The basis of the proof is to reduce the problem to estimating an exponential sum, which generalizes the notion of "correlation" studied by [CGT]. This identifies the type of exponential sum that will be instrumental in proving the general case. Along the way we substantially simplify previous proofs.

## Publication Title

Theory of Computing Systems

## Publication Date

1999

## Volume

32

## Issue

4

## First Page

453

## Last Page

466

## ISSN

1432-4350

## DOI

10.1007/s002240000126

## Keywords

lower bound, open problem, recent result, symmetric function, symmetry condition

## Repository Citation

Green, F., "Exponential sums and circuits with a single threshold gate and mod-gates" (1999). *Computer Science*. 66.

https://commons.clarku.edu/faculty_computer_sciences/66

## APA Citation

Green, F. (1999). Exponential sums and circuits with a single threshold gate and mod-gates. *Theory of Computing Systems*, *32*, 453-466.