2021-2022 Seminars

We consider the problem of computing a Gradient Descent solution of a continuously differentiable function f on a bounded convex domain, i.e., finding a "point where Gradient Descent terminates". Equivalently, this corresponds to computing a so...

The query model is one of the most basic computational models.  In contrast to the Turing machine model, fundamental questions regarding the power of randomness and quantum computing are relatively well-understood.  For example, it is well-known...

Given i.i.d. samples drawn from an unknown distribution over a large domain [N], approximating several basic quantities, such as the distribution's support size and its Shannon Entropy, requires at least roughly (N / \log N) samples [Valiant and...

Every multivariate polynomial P(x_1,...,x_n) can be written as a sum of monomials, i.e. a sum of products of variables and field constants.  In general, the size of such an expression is the number of monomials that have a non-zero coefficient in P...

Every multivariate polynomial P(x_1,...,x_n) can be written as a sum of monomials, i.e. a sum of products of variables and field constants.  In general, the size of such an expression is the number of monomials that have a non-zero coefficient in P...

The study of linear spaces of matrices arises naturally (and independently) in many different areas of mathematics and computer science.  In this survey talk, I will describe some of these motivations, and state and prove some (old and new)...

A random walk on expanders, despite its strong underlying correlations, poses extremely useful pseudorandom properties. The expander hitting property and the expander Chernoff are two such classic examples. That is, the AND function and certain...