We study the complexity of computing Boolean functions using AND, OR and NOT gates. We show that a circuit of depth d with S gates can be made to output a constant by setting O(S 1−ɛ(d) ) (where ɛ(d) = 4 −d) of its input values. This implies a superlinear size lower bound for a large class of functions. Using this, we obtain a function computable by a uniform family of constant depth polynomial size circuits that cannot be computed by constant depth circuits of linear size. We give circuit constructions that show that the bound O(S 1−ɛ(d) ) is near optimal. We also study the complexity of computing threshold functions. The function T n r has the value 1 iff at least r of its inputs have the value 1. We show that a circuit computing T n r has at least Ω(r 2 (log n) / log r) gates, for r ≤ n 1/3, improving previous bounds. We also show a trade-off between the number of gates and the number of wires in a threshold circuit, namely, a circuit with G (< n/2) gates and W wires computing T n r satisfies W ≥ Ω(nr(log n)/(log(G / log n))), showing that it is not possible to simultaneously optimize the number of gates and wires in a threshold circuit. Our bounds for threshold functions are based on a combinatorial lemma of independent interest. 1

The chaining problem is defined as follows. Given values at $a_1 , \ldots ,a_n ,a_i = 0$ or 1, $1 \leqslant i \leqslant n$, compute $b_1 , \ldots ,b_n $ such that $b_i = \max \{ j|a_j = 1,j < i\} $. (Define $\max \{ \} = 0$.) The chaining problem appears as a subproblem in many contexts. There are known algorithms that solve the chaining problem on CROW PRAMs in $O(\alpha (n))$ time, where $\alpha (n)$ is the inverse of Ackerman’s function, and is a very slowly growing function. The author studies a class of algorithms (called oblivious algorithms) for this problem. A simple oblivious chaining algorithm running in $O(\alpha (n))$ time is presented. More importantly, the optimality of the algorithm is demonstrated by showing a matching lower bound for oblivious algorithms using n processors. The first steps toward a lower bound for all chaining algorithms are also provided by showing that any chaining algorithm that runs in two steps must use a superlinear number of processors. The proofs use prefix graphs and weak superconcentrators An interesting connection between the two is demonstrated and this idea is used to obtain improved bounds on the size of prefix graphs.

We investigate properties of functions that are good measures of the CRCW PRAM complexity of computing them. While the block sensitivity is known to be a good measure of the CREW PRAM complexity, no such measure is known for CRCW PRAMs. We show that the complexity of computing a function is related to its everywhere sensitivity, introduced by Vishkin and Wigderson (1985). Specifically we show that the time required to compute a function f:D/sup n//spl rarr/R of everywhere sensitivity es(f) with P/spl ges/n processors and unbounded memory is /spl Omega/(log[log es(f)/(log 4P|D|- log es(f))]). This improves previous results of Azar (1992), and Vishkin and Wigderson. We use this lower bound to derive new lower bounds for some approximate problems. These problems can often be solved faster than their exact counterparts and for many applications, it is sufficient to solve the approximate problem. We show that approximate selection requires time /spl Omega/(log[log n/log k]) with kn, processors and approximate counting with accuracy /spl lambda//spl ges/2 requires time /spl Omega/(log[log n/(log k+log /spl lambda/)]) with kn processors. In particular, for constant accuracy, no lower bounds were known for these problems.>

The authors study the complexity of some prefix problems in the CRCW PRAM model. The main result is an Omega ( alpha (n)) lower bound for chaining, matching a previous upper bound and solving an open problem. They give reductions to show an Omega ( alpha (n)) lower bound on the complexity of the prefix maxima and range maxima problems even when the domain is (1,...,n). An interesting consequence is that prefix maximum is strictly harder than simple maximum. They also give a reduction to show an Omega ( alpha (n)) lower bound on a parenthesis matching problem, matching the upper bound. No lower bounds were previously known for any of these problems. The lower bounds contribute to the study of very fast parallel algorithms by introducing techniques for proving lower bounds for small domain problems.>

The chaining problem is defined as follows.Given