Abstract.  For an input of length N, we usually assume that the time complexity of any algorithm is at least N, since the algorithm needs N steps only to read the input. However, especially recently, there have been increasing demands for studying algorithms that run in significantly less than N steps by sacrificing the exactness of the computation. In this case, we need some mechanism for algorithms to obtain the input, since it is no longer possible to read all the input bits sequentially. "Oracles" are a popular model for this purpose. The most standard oracle is so-called an index oracle, that returns the i-th bit of the input for the query i (an integer between 1 and N). Thus, we obviously need N oracle calls in order to get all the input bits in this case.

A little surprisingly, this is not always the case. For instance, some Boolean functions can be computed, with high success probability, using oracle calls much less than N times. Furthermore, if we are allowed to use different kind of oracles or "quantum" oracles, then we can even reconstruct the whole input string with less than N oracle calls. This talk includes several interesting such cases and introduction to the basic ideas and mechanisms making that possible.