We will discuss interactive coding in the setting where there are n
parties attempting to compute a joint function of their inputs
using error-prone pairwise communication channels. We will present
a general protocol that allows one to achieve only...
We will outline the proof that gives a positive solution of to
Weaver's conjecture \(KS_2\). That is, we will show that any
isotropic collection of vectors whose outer products sum to twice
the identity can be partitioned into two parts such that...
One of the major open problems in complexity theory is proving
super-polynomial lower bounds for circuits with logarithmic depth
(i.e.,\(P \not\subseteq NC_1\) ). This problem is interesting both
because it is tightly related to understanding the...
In a profoundly influential 1948 paper, Claude Shannon defined the
entropy function H, and showed that the capacity of a symmetric
binary channel with noise rate (bit flip rate) eps is 1−H(eps).
This means that one can reliably communicate n bits by...
Machine learning is often employed as one step in a larger
application, serving to perform information extraction or data
mining for example. The rules obtained by such learning are then
used as inputs to a further analysis. As a consequence of the...
In this talk we will present an overview of the hypermatrix
generalization of matrix algebra proposed by Mesner and
Bhattacharya in 1990. We will discuss a spectral theorem for
hypermatrices deduced from this algebra as well as connections
with...
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...
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...
Classical matrix perturbation bounds, such as Weyl (for
eigenvalues) and David-Kahan (for eigenvectors) have, for a long
time, been playing an important role in various areas: numerical
analysis, combinatorics, theoretical computer science...
