This is intended to be a survey talk, accessible to a general
mathematical audience. The cdh topology was created by Voevodsky to
extend motivic cohomology from smooth varieties to singular
varieties, assuming resolution of singularities (for...
We use critical block sensitivity, a new complexity measure
introduced by Huynh and Nordstrom (STOC 2012) to study the
communication complexity of search problems. Our main result is a
simple proof that if S is a search problem with high
critical...
This workshop is part of the topical program "Non-equilibrium
Dynamics and Random Matrices" which will take place during the
2013-2014 academic year at the Institute for Advanced Study.
The workshop aims to provide a broad survey of the
current...
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 functions over
{−1...
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...
