Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Perceptron:
TR98-061 | 29th September 1998
Robert H. Sloan, Ken Takata, György Turán

On frequent sets of Boolean matrices

Given a Boolean matrix and a threshold t, a subset of the
columns is frequent if there are at least t rows having a 1 entry in
each corresponding position. This concept is used in the algorithmic,
combinatorial approach to knowledge discovery and data mining. We
consider the complexity aspects ... more >>>

TR06-061 | 5th May 2006
Venkatesan Guruswami, Prasad Raghavendra

Hardness of Learning Halfspaces with Noise

Learning an unknown halfspace (also called a perceptron) from
labeled examples is one of the classic problems in machine learning.
In the noise-free case, when a halfspace consistent with all the
training examples exists, the problem can be solved in polynomial
time using linear programming. ... more >>>

ISSN 1433-8092 | Imprint