The sample complexity and computational complexity of Boolean function learning
Anthony, M.
(2002).
The sample complexity and computational complexity of Boolean function learning.
(CDAM research report series LSE-CDAM-2002-13).
Centre for Discrete and Applicable Mathematics, London School of Economics and Political Science.
(2002).
The sample complexity and computational complexity of Boolean function learning.
(CDAM research report series LSE-CDAM-2002-13).
Centre for Discrete and Applicable Mathematics, London School of Economics and Political Science.
This report surveys some key results on the learning of Boolean functions in a probabilistic model that is a generalization of the well-known ‘PAC’ model. A version of this is to appear as a chapter in a book on Boolean functions, but the report itself is relatively self-contained.