Sensitive Functions and Approximate Problems

Properties of functions that are good measures of the CRCW PRAM complexity of computing them are investigated. While theblock sensitivityis known to be a good measure of the CREW PRAM complexity, no such measure is known for CRCW PRAMs. It is shown that the complexity of computing a function is related to itseverywhere sensitivity, introduced by Vishkin and Wigderson. Specifically, the time required to compute a functionf: Dn →Rof everywhere sensitivityes(f) withPprocessors and unbounded memory isΩ(log[log es(f)/(log(|D|+4P/es(f)))]). This improves results of Azar and of Vishkin and Wigderson. This lower bound is used to derive new lower bounds for someapproximate problems. These problems can often be solved faster than their exact counterparts and for many applications, it is sufficient to solve the approximate problem. It is shown thatapproximate selection, approximate counting, approximate compaction, andpadded sortingall require timeΩ(loglog n) with a linear number of processors, if the level of accuracy desired is moderately high. For these levels of accuracy, no lower bounds were known for these problems on the PRAM model. The lower bounds for some of the problems are tight.

Authors

• Shiva Chaudhuri

Keywords

No keywords are indexed for this paper.