Previous Conferences & Workshops

We introduce and study a new type of learning problem for probability distributions over the Boolean hypercube \(\{-1,1\}^n\). As in the standard PAC learning model, a learning problem in our framework is defined by a class \(C\) of Boolean...

Given data stream \(D = \{p_1,p_2,...,p_m\}\) of size \(m\) of numbers from \(\{1,..., n\}\), the frequency of \(i\) is defined as \(f_i = |\{j: p_j = i\}|\). The \(k\)-th frequency moment of \(D\) is defined as \(F_k = \sum_{i=1}^n f_i^k\). We...