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 of frequent sets. An explicit family
of subsets is given that requires exponentially many rows to be
represented as the family of frequent sets of a matrix, with any
threshold. Examples are given of families that can be represented by
a small matrix with threshold t, but that require a significantly
larger matrix if the threshold is less than t. We also discuss the
connections of these problems to circuit complexity and the existence
of efficient listing algorithms.