Computer Science and Discrete Mathematics (CSDM)

A random point process is said to be determinantal if finite subset probabilities correspond to principal minors of some matrix. Determinantal point processes (DPPs) appear in a wide variety of settings, from random matrix theory to combinatorics...

What does the spectrum of a random matrix look like when we make no assumption whatsoever about the covariance pattern of its entries?  It may appear hopeless that anything useful can be said at this level of generality. Nonetheless, a widely used...

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...

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...