Paper Info
Title
On Learning, Lower Bounds and (un)Keeping Promises.
Abstract
We extend the line of research initiated by Fortnow and Klivans [6] that studies the relationship between efficient learning algorithms and circuit lower bounds. In [6], it was shown that if a Boolean circuit class C has an efficient deterministic exact learning algorithm, (i.e. an algorithm that uses membership and equivalence queries) then EXPNP not subset of P/poly[C](1). Recently, in [14] EXPNP was replaced by DTIME(n(omega(1))). Yet for the models of randomized exact learning or Valiant's PAC learning, the best result so far is a lower bound against BPEXP (the exponential-time analogue of BPP). In this paper, we derive stronger lower bounds as well as some other consequences from randomized exact learning and PAC learning algorithms, answering an open question posed in [6] and [14]. In particular, we show that 1. If a Boolean circuit class C has an efficient randomized exact learning algorithm or an efficient PAC learning algorithm(2) then BPTIME(n(omega(1)))/1 not subset of P/poly[C]. 2. If a Boolean circuit class C has an efficient randomized exact learning algorithm then no strong pseudo-random generators exist in P/poly[C]. We note that in both cases the learning algorithms need not be proper(3). The extra bit of advice comes to accommodate the need to keep the promise of bounded away probabilities of acceptance and rejection. The exact same problem arises when trying to prove lower bounds for BPTIME or MA [3,7,16,20]. It has been an open problem to remove this bit. We suggest an approach to settle this problem in our case. Finally, we slightly improve the result of [5] by showing a subclass of MAEXP that requires super-polynomial circuits. Our results combine and extend some of the techniques previously used in [6,14] and [20].
Year
DOI
Venue
2014
10.1007/978-3-662-43948-7_85
Lecture Notes in Computer Science
DocType
Volume
ISSN
Journal
8572
0302-9743
Citations 
PageRank 
References 
0
0.34
11
Authors
1
Name
Order
Citations
PageRank
Ilya Volkovich11458.64