Robert H. Sloan, Ken Takata, György Turán

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

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio

The \emph{Chow parameters} of a Boolean function $f: \{-1,1\}^n \to \{-1,1\}$ are its $n+1$ degree-0 and degree-1 Fourier coefficients. It has been known since 1961 \cite{Chow:61, Tannenbaum:61} that the (exact values of the) Chow parameters of any linear threshold function $f$ uniquely specify $f$ within the space of all Boolean ... more >>>

Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii

In this paper, we address sorting networks that are constructed from comparators of arity $k > 2$. That is, in our setting the arity of the comparators -- or, in other words, the number of inputs that can be sorted at the unit cost -- is a parameter. We study ... more >>>