Sensitive functions and approximate problems

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ⁿ→R of everywhere sensitivity es(f) with P⩾n processors and unbounded memory is Ω(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 Ω(log[log n/log k]) with kn, processors and approximate counting with accuracy λ⩾2 requires time Ω(log[log n/(log k+log λ)]) with kn processors. In particular, for constant accuracy, no lower bounds were known for these problems