Publications - Abstracts

Research Group of Prof.C.P.Schnorr, University of Frankfurt am Main

Cryptographic Limitations on Parallelizing Membership and Equivalence Queries with Applications to Random Self-Reductions

Marc Fischlin
Fachbereich Mathematik (AG 7.2) / Informatik
Johann Wolfgang Goethe-Universität Frankfurt am Main
PSF 111932
60054 Frankfurt/Main, Germany

e-mail: marc@mi.informatik.uni-frankfurt.de
URL: http://www.mi.informatik.uni-frankfurt.de

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.

The .ps, .dvi and .ps.gz versions will be available on October 8th, 1999.