Publications - Abstracts
# 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.