b'@techreport{MPI-I-93-145,'b'\nTITLE = {Sensitive functions and approximate problems},\nAUTHOR = {Chaudhuri, Shiva},\nLANGUAGE = {eng},\nNUMBER = {MPI-I-93-145},\nINSTITUTION = {Max-Planck-Institut f{\\"u}r Informatik},\nADDRESS = {Saarbr{\\"u}cken},\nYEAR = {1993},\nDATE = {1993},\nABSTRACT = {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.},\nTYPE = {Research Report / Max-Planck-Institut f\xc3\xbcr Informatik},\n}\n'