Decompositions in theorems in classical Fourier analysis which
decompose a function into large Fourier coefficients and a part
that is pseudorandom
with respect to (has small correlation with) linear functions. The
Goldreich-Levin theorem [GL89]...
A k-modal probability distribution over the domain {1,...,N} is
one whose histogram has at most k "peaks" and "valleys". Such
distributions are a natural generalization of the well-studied
class of monotone increasing (or monotone decreasing)...
In a joint work with Tsuyoshi Ito we have constructed a
fingerprinting scheme (i.e., hashing) that leaks significantly less
than log(1/epsilon) bits about the preimage, where epsilon is the
error ("collision") probability. It is easy to see...
A "sparsifier" of a graph is a weighted subgraph for which every
cut has approximately the same value as the original graph, up to a
factor of (1 +/- eps). Sparsifiers were first studied by Benczur
and Karger (1996). They have wide-ranging...
Recursive Majority-of-three (3-Maj) is a deceptively simple
problem in the study of randomized decision tree complexity. The
precise complexity of this problem is unknown, while that of the
similarly defined Recursive NAND tree is completely...
Boolean Threshold Functions (BTF) arise in many contexts,
ranging from computer science and learning theory to theoretical
neurobiology. In this talk, I will present non-rigorous approaches
developed in the statistical physics of disordered...
Given data drawn from a mixture of multivariate Gaussians, a
basic problem is to accurately estimate the mixture parameters. We
provide a polynomial-time algorithm for this problem for any fixed
number ($k$) of Gaussians in $n$ dimensions (even...
We give an elementary proof of a generalization of Bourgain and
Tzafriri's Restricted Invertibility Theorem, which says roughly
that any matrix with columns of unit length and bounded operator
norm has a large coordinate subspace on which it is well...
