Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds
Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds
复制标题
精确学习算法、投注游戏和电路下界
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
J. M. Hitchcock
中科院分区：
文献类型：
--
作者：
Ryan C. Harkins;J. M. Hitchcock
本文扩展和改进了Fortnow和Klivans[2009]的工作，他们证明了如果C类电路在Anluin的通过等价和成员查询进行精确学习的模型中有有效的学习算法[Anluin 1988]，那么我们有EXPNP的下界而不是C。2001]去掉了NP预言，并改进了Exp Not C的下界，这表明设计C的学习算法比Fortnow和Klivans[2009]的结果更难。我们还研究了博彩对策和自然证明之间的联系，并作为推论，证明了强伪随机生成元的存在。
我们的结果也进一步证明了这类布尔电路没有有效的精确学习算法。这是因为我们的分离是强烈的，因为它产生了反对阶级的自然证据(Razborov和Rudich 1997)。由此我们得出结论，布尔电路的精确学习算法意味着不存在强伪随机生成器，这与人们普遍认为的密码学猜想相矛盾。作为推论，我们得出结论：如果存在强伪随机生成元，则布尔电路不存在精确的学习算法。
This article extends and improves the work of Fortnow and Klivans [2009], who showed that if a circuit class C has an efficient learning algorithm in Angluin’s model of exact learning via equivalence and membership queries [Angluin 1988], then we have the lower bound EXPNP not C. We use entirely different techniques involving betting games [Buhrman et al. 2001] to remove the NP oracle and improve the lower bound to EXP not C. This shows that it is even more difficult to design a learning algorithm for C than the results of Fortnow and Klivans [2009] indicated. We also investigate the connection between betting games and natural proofs, and as a corollary the existence of strong pseudorandom generators.
Our results also yield further evidence that the class of Boolean circuits has no efficient exact learning algorithm. This is because our separation is strong in that it yields a natural proof [Razborov and Rudich 1997] against the class. From this we conclude that an exact learning algorithm for Boolean circuits would imply that strong pseudorandom generators do not exist, which contradicts widely believed conjectures from cryptography. As a corollary we obtain that if strong pseudorandom generators exist, then there is no exact learning algorithm for Boolean circuits.