Paper Info
Title
Lower Bounds for Constant Depth Circuits for Prefix Problems
Abstract
A prefix-or circuit has n inputs and n outputs; the ith output is the OR of the first i inputs. A prefix-carry circuit has 2n inputs, interpreted as two n-bit numbers, and n outputs; the ith output is the carry in the ith position of the sum of the two numbers. We show a nonlinear lower bound for constant-depth, unboundedfanin implementations of prefix-or. However, with negation, linear size circuits are possible. For prefix-carry, we show nonlinear lower bounds for arbitrary circuits. In both cases the lower bounds exhibit a size/depth tradeoff: the circuit size must be at least (nf d –1 d(n)) for depth a constant times d. Here the functions f d form an increasing hierarchy coextensive with the primitive recursive functions. The lower bounds match the known upper bounds for these problems, to within a constant factor for depth.
Year
DOI
Venue
1983
10.1007/BFb0036901
ICALP
Keywords
Field
DocType
prefix problems,lower bounds,constant depth circuits,lower bound,upper bound
Boolean function,Discrete mathematics,Combinatorics,Boolean circuit,Nonlinear system,Primitive recursive function,Parallel random-access machine,Computer science,Upper and lower bounds,Prefix,Electronic circuit
Conference
Volume
ISSN
ISBN
154
0302-9743
3-540-12317-2
Citations 
PageRank 
References 
29
1.79
8
Authors
3
Name
Order
Citations
PageRank
Ashok K. Chandra131161215.02
Steven Fortune2291.79
Richard J. Lipton364121796.57