论文标题
从电路下限学习算法
Learning algorithms from circuit lower bounds
论文作者
论文摘要
我们重新审视了从建设性电路下限的各种概念中的有效学习算法的已知结构，例如破坏伪和伪造者的区分者或有效的见证算法，这些算法发现试图计算硬功能的小电路的错误。作为我们的主要结果，我们证明，如果有可能以特定的交互式方式有效地找到试图解决硬性问题的许多P大型电路的错误，那么可以通过均匀分布来通过构件的查询来学习P型电路。相反的含义也存在。这提供了学习算法的新特征，并扩展了Razborov和Rudich的自然证明障碍。该证明是基于利用Krajíček（2010）引入的Nisan-Wigderson发电机的方法，用于分析有界算术中电路下限的复杂性。 来自电路下限的学习算法的已知结构的一个有趣结果是Oliveira和Santhanam的学习速度（2016年）。我们提供了这种现象的替代证明，并讨论了其推进硬度放大计划的潜力。
We revisit known constructions of efficient learning algorithms from various notions of constructive circuit lower bounds such as distinguishers breaking pseudorandom generators or efficient witnessing algorithms which find errors of small circuits attempting to compute hard functions. As our main result we prove that if it is possible to find efficiently, in a particular interactive way, errors of many p-size circuits attempting to solve hard problems, then p-size circuits can be PAC learned over the uniform distribution with membership queries by circuits of subexponential size. The opposite implication holds as well. This provides a new characterisation of learning algorithms and extends the natural proofs barrier of Razborov and Rudich. The proof is based on a method of exploiting Nisan-Wigderson generators introduced by Krajíček (2010) and used to analyze complexity of circuit lower bounds in bounded arithmetic. An interesting consequence of known constructions of learning algorithms from circuit lower bounds is a learning speedup of Oliveira and Santhanam (2016). We present an alternative proof of this phenomenon and discuss its potential to advance the program of hardness magnification.
