ICS 2011

Welcome to ICS2011
Innovations in Computer Science  ICS 2011, Tsinghua University, Beijing, China, January 79, 2011. Proceedings, 284297, 9787302245179
Tsinghua University Press
Let S be a finite set. Given a function f : S → S and an element a ∈ S, define f0(a) = a and fi(a) = f(fi−1(a)) for all i ≥ 1. Let s ≥ 0 and r > 0 be the smallest integers such that fs(a) = fs+r(a). Determining s and r, given a ∈ S and a blackbox oracle to f, is the cycledetection problem. When f is bijective (i.e., f is a permutation of S), the orderfinding problem is to find the smallest r > 0 such that fr(a) = a, and the discretelog problem is, given an additional element b ∈ S, to find the smallest k ≥ 0 such that fk(a) = b. We study the query complexity of these problems with oracles that allow "jumps" to distant positions in the sequence ā f0(a)f1(a)f2(a)... ∈ S* at unit cost. Specifically, for every m ∈ N the oracle Omf is defined, which for every a ∈ S allows to look ahead at any position i < m in the sequence ā; that is, Omf (a, i) = fi(a) for every (a, i) ∈ S × [m]. We show that with an unrestricted oracle O∞f , the cycledetection and orderfinding problems can be solved using O(log s+log r/ log log log r) and O(log r/ log log log r) queries, respectively, regardless of S. This is nearly optimal, as we also prove lower bounds of Ω(log s + log r/ log log r) and Ω(log r/ log log r) queries. Interestingly, for the discretelog problem, our results combined with the algorithm of Sutherland [8] imply a lower bound of Ω( / log r) queries (where r is the size of the cycle to which both a and b belong), which is tight up to the log r factor. This contrasts with the fact that, with generic groupoperation oracles, the problems of order finding and discrete log are known to have polynomially related query complexities. We also provide algorithms and lower bounds for general oracles Omf , m ∈ N, improving results from earlier work. In particular, with m = poly(r), our lower bound for orderfinding improves the previous bound of Ω(r1/3) queries, proved by Cleve [2], to Ω(r1/2), which is nearly optimal. Preview:

Copyright 20102011, Institute for Computer Science, Tsinghua University, All Rights Reserved.