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 >>>

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 >>>