Cryptographic Limitations on Parallelizing Membership and Equivalence Queries with Applications to Random Self-Reductions Queries Author: Marc Fischlin Source: Lecture Notes in Artificial Intelligence Vol. 1501, 1998, 72 - 86. 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 at all. We also discuss some applications to random self-reductions and coherent sets. ©Copyright 1998 Springer