On the Exact Learning of Formulas in Parallel (Extended Abstract)
Nader H. Bshouty, Richard Cleve · Foundations of Computer Science · 1992
We investigate the parallel complexity of learning formulas from membership and equivalence queries. We consider a number of learning problems that can be solved sequentially an polynomial time. We prove some upper and lower bounds on the number of parallel steps required to solve these problems with a polynomial number of processors.