Learning circuits with few negations
Learning circuits with few negations
复制标题
具有很少否定的学习电路
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Li
中科院分区：
文献类型：
--
作者：
Eric Blais;C. Canonne;I. Oliveira;R. Servedio;Li
单调布尔函数和计算它们的单调布尔电路在复杂性理论中得到了深入的研究。在本文中，我们研究了布尔函数的结构方面的最小数量的否定在任何电路计算它们，一个复杂的措施，插值之间的单调函数和类的所有功能。我们从学习理论Vantage研究了这种单调性的推广，给出了电路的均匀分布可学习性的近似匹配上界和下界，它们包含的否定数。我们的上界是基于负限电路的一个新的结构特征，它推广了A. A.马尔科夫我们的下界，采用傅立叶分析工具从硬度放大，甚至没有否定电路（即单调函数），给出了新的结果。
Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean functions in terms of the minimum number of negations in any circuit computing them, a complexity measure that interpolates between monotone functions and the class of all functions. We study this generalization of monotonicity from the vantage point of learning theory, giving near-matching upper and lower bounds on the uniform-distribution learnability of circuits in terms of the number of negations they contain. Our upper bounds are based on a new structural characterization of negation-limited circuits that extends a classical result of A. A. Markov. Our lower bounds, which employ Fourier-analytic tools from hardness amplification, give new results even for circuits with no negations (i.e. monotone functions).