Johannes Köbler and Wolfgang Lindner and Rainer Schuler
Abstract:
We show that every language in $\RP$ has subexponential-time
approximations for infinitely many input lengths if boolean circuits
are not polynomial-time pac-learnable with membership queries under
the uniform distribution.