Singleton Functions

An $N$-bit Boolean function that evaluates to 1 for exactly one input is a singleton function. We will show that for any $N$-bit singleton function Ambainis' Theorem can always attain a lower query bound of $\Omega(\sqrt{N})$, but no better.

The proof of the $\Omega(\sqrt{N})$ lower query bound for determining the oracle string in Theorem can equally well be applied to any singleton function.

Corollary 2.4.1   $\Omega(\sqrt{N})$ oracle queries are required to compute any $N$-bit singleton function in the bounded error setting.

Theorem 2.4.1   $\Omega(\sqrt{N})$ is the best lower bound on the number of oracle queries required to compute an $N$-bit singleton function that can be attained from Theorem .

This result coupled with the $N/2$ lower bound for the singleton function of determining the oracle string leads immediately the the following corollary.

Corollary 2.4.2   There exist functions for which Ambainis' Theorem can not attain asymptotically tight lower bounds.

Despite this limitation, the theorem can still prove lower bounds for many Boolean functions. From this point forward all our lower bounds are directly or indirectly attained through Ambainis' Theorem.