# MPI-I-93-145

## Sensitive functions and approximate problems

### Chaudhuri, Shiva

**MPI-I-93-145**. October** **1993, 8 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-93-145.pdf | 10464 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-145

**BibTeX**
`@TECHREPORT{``Chaudhuri93a``,`

` AUTHOR = {Chaudhuri, Shiva},`

` TITLE = {Sensitive functions and approximate problems},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-93-145},`

` MONTH = {October},`

` YEAR = {1993},`

` ISSN = {0946-011X},`

`}`