Random restrictions are a powerful tool used to study the
complexity of boolean functions. Various classes of boolean
circuits are known to simplify under random restrictions. A prime
example of this, discovered by Subbotovskaya more than 60
years...
In this talk, I will present the following two connections
between private optimization and statistical physics, both via the
problem of approximating a given covariance matrix with a low-rank
matrix:
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...
