Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Sensitive functions and approximate problems


Chaudhuri,  Shiva
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Any fulltext), 11MB

Supplementary Material (public)
There is no public supplementary material available

Chaudhuri, S.(1993). Sensitive functions and approximate problems (MPI-I-93-145). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-B75D-D
We investigate properties of functions that are good measures of the CRCW PRAM complexity of computing them. While the {\em 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 {\em everywhere sensitivity}, introduced by Vishkin and Wigderson. Specifically we show that the time required to compute a function $f:D^n \rightarrow R$ of everywhere sensitivity $ \es (f)$ with $P \geq n$ processors and unbounded memory is $ \Omega (\log [\log \es(f)/(\log 4P|D| - \log \es(f))])$. This improves previous results of Azar, and Vishkin and Wigderson. We use this lower bound to derive new lower bounds for some {\em 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 {\em approximate selection} requires time $\Omega(\log [\log n/\log k])$ with $kn$ processors and {\em approximate counting} with accuracy $\lambda \geq 2$ requires time $\Omega(\log [\log n/(\log k + \log \lambda)])$ with $kn$ processors. In particular, for constant accuracy, no lower bounds were known for these problems.