# Lower bounds of calculating a function of a set

Having a set $A$ of $n$ elements, let's say I want to calculate a function $f(A)$ that is sensitive to all parts of the input, i.e. depends on very member of $A$ (i.e. it is possible to change any member of $A$ to something else to obtain a new input $A'$ s.t. value of $f$ on $A$ and $A'$ are different).

For example, $f$ could be the sum or the average.

Is there a result that proves that, under some conditions, the time necessary to a deterministic Turing machine to compute $f$ will be $\Omega(n)$?

• Note that if $A$ is a sequence with random access, and the sensitivity assumption is weakened, this does not always hold. For example, $(i,x_1,\dots,x_n) \to x_i$ can be computed with two queries, even though it is not a junta. Apr 10 '12 at 22:44
• @sdcvvc your example reminds me the C language instruction V[i]. What is the definition of junta? Apr 10 '12 at 22:52
• A $k$-junta is a boolean function that depends only on $k$ arguments, i.e. there is a set $A\subset\{1,2,\dots,n\}$ of size $k$ such that for any $x$,$y$, if $x$ and $y$ differ only on positions outside $A$, then $f(x)=f(y)$. I abused this term to mean a function that does not depend on all arguments. Apr 10 '12 at 23:18
• If you are trying to find support for your answer to the average distance problem on math.se, unfortunately, this won't do. Apr 11 '12 at 5:38
• @Aryabhata the first intention was to find support for my answer to this question: math.stackexchange.com/questions/129969/…, but the only thing that this result will say is that if there are $n$ vertices in the graph, the algorithm calculating the average distance them will be $\Omega(n)$, which is quite obvius. I have deleted my answer there, because as you wrote I did not prove anything. Apr 11 '12 at 7:18

You have to be specify the model of computation and properties of $f$. In the following argument I will state the assumptions that I need. It can be generalized a little bit further but I think it should be sufficient to give you the idea.

Assume that the machine $M$ never reads the value of one of the members of $A$ (a fixed set, and $A$ is given as a list). Assume further that $A$ is an input such that changing the value of its $i$th member does not change $M$'s answer. Assume further that $f$ is sensitive to all parts of the input, i.e. depends on very member of $A$ (i.e. it is possible to change any member of $A$ to something else to obtain a new input $A'$ s.t. value of $f$ on $A$ and $A'$ are different).

We can use an adversary argument to show that the machine cannot compute the right answer by changing the value of that member of $A$ to obtain $A'$ else s.t. the value of $f$ is different. The value of $M$ on these two sets is the same, so one of them must be false and therefore $M$ cannot compute $f$ correctly.

Therefore any machine $M$ that computes $f$ will need to read all of the input which takes $\Omega(n)$ steps.

(On the other hand, assume that we have a nondeterministic random access machine, and we want to compute OR of the bits in the input. We can nondeterministicly guess a bit and check if that is 1, if it is 1, we output 1. This machine reads only a single bit of the input in $O(\lg n)$ steps and correctly answers the problem. So without assumptions on $M$ and $f$ the result does not hold.)

• Sorry I forgot to write that my model of computation was the deterministic Turing machine. Apr 10 '12 at 22:07
• +1 for adversary argument, which is a great way to begin understanding lower bounds.
– Joe
Apr 12 '12 at 4:57