Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions Author: Marc Fischlin Email: marc@mi.informatik.uni-frankfurt.de Source: Theoretical Computer Science Vol. 268, Issue 2, 17 October 2001, pp. 199 - 219. Abstract. We assume wlog that every learning algorithm with membership and equivalence queries proceeds in rounds. In each round it puts in parallel a polynomial number of queries and after receiving the answers, it performs internal computations before starting the next round. The query depth is defined by the number of rounds. In this paper we show that, assuming the existence of cryptographic one-way functions, for any fixed polynomial d(n) there exists a concept class that is efficiently and exactly learnable with membership queries in query depth d(n)+1, but cannot be weakly predicted with membership and equivalence queries in depth d(n). Hence, concerning the query depth, efficient learning algorithms for this concept class cannot be parallelized. We also discuss applications to random-self-reductions and coherent sets.

©Copyright 2001 Elsevier Science B.V.