Lower bounds for constant depth circuits in the presence of help bits
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 532-537
- https://doi.org/10.1109/sfcs.1989.63530
Abstract
The problem of how many extra bits of 'help' a constant depth circuit needs in order to compute m functions is considered. Each help bit can be an arbitrary Boolean function. An exponential lower bound on the size of the circuit computing m parity functions in the presence of m-1 help bits is proved. The proof is carried out using the algebraic machinery of A. Razborov (1987) and R. Smolensky (1987). A by-product of the proof is that the same bound holds for circuits with mod/sub p/ gates for a fixed prime p>2. The lower bound implies a random oracle separation for PH and PSPACE, which is optimal in a technical sense.Keywords
This publication has 13 references indexed in Scilit:
- The Boolean Hierarchy I: Structural PropertiesSIAM Journal on Computing, 1988
- The polynomial time hierarchy collapses if the Boolean hierarchy collapsesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Random oracles separate PSPACE from the polynomial-time hierarchyInformation Processing Letters, 1987
- Lower bounds on the size of bounded depth circuits over a complete basis with logical additionMathematical Notes, 1987
- Algebraic methods in the theory of lower bounds for Boolean circuit complexityPublished by Association for Computing Machinery (ACM) ,1987
- Almost optimal lower bounds for small depth circuitsPublished by Association for Computing Machinery (ACM) ,1986
- Separating the polynomial-time hierarchy by oraclesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981
- The polynomial-time hierarchyTheoretical Computer Science, 1976