Linear dynamical systems are the canonical model for time series
data. They have wide-ranging applications and there is a vast
literature on learning their parameters from input-output
sequences. Moreover they have received renewed interest
because...
It is widely believed that the physics of diffraction imposes
certain fundamental limits on the resolution of an optical system.
In this work we study the diffraction limit as a statistical
inverse problem in increasingly more realistic mathematical...
This talk will summarize a project I was involved in during the
past 8 years. It started with attempts to understand the PIT
(Polynomial Identity Testing) problem - a central problem involving
randomness and hardness. It has led us to pursue many...
In the last few years, expanders have been used in fast graph
algorithms in different models, including static, dynamic, and
distributed algorithms. I will survey these applications of
expanders, explain the expander-related tools behind this...
In a vertex expanding graph, every small subset of vertices
neighbors many different vertices. Random graphs are near-optimal
vertex expanders; however, it has proven difficult to create
families of deterministic near-optimal vertex expanders, as...
Let C be a class of metric spaces. We consider the following
computational metric embedding problem: given a vector x in R^{n
choose 2} representing pairwise distances between n points, change
the minimum number of entries of x to ensure that the...
A finite set system is union-closed if for every pair of sets in
the system their union is also in the system. Frankl in 1979
conjectured that for any such system there exists an element which
is contained in ½ of the sets in that system (the only...
Discrepancy theory provides a powerful approach to improve upon
the bounds obtained by a basic application of the probabilistic
method. In recent years, several algorithmic approaches have been
developed for various classical results in the area. In...
Matrix powering, and more generally iterated matrix
multiplication, is a fundamental linear algebraic primitive with
myriad applications in computer science. Of particular interest is
the problem’s space complexity as it constitutes the main
route...
We prove the existence of subspace designs with any given
parameters, provided that the dimension of the underlying space is
sufficiently large in terms of the other parameters of the design
and satisfies the obvious necessary divisibility...
