2019-2020 Seminars

While there are convergence guarantees for temporal difference (TD) learning when using linear function approximators, the situation for nonlinear models is far less understood, and divergent examples are known. We take a first step towards...

Many of the central problems in computational complexity revolve around proving lower bounds on the amount of resources used in various computational models. In this talk we will continue our survey of the connections between three central models...

Expanders have grown to be one of the most central and studied notions in modern graph theory. It is thus only natural to research extremal properties of expanding graphs. In this talk we will adapt the following (rather relaxed) definition of...

Please Note: The seminars are not open to the general public, but only to active researchers.

Register here for this event: https://docs.google.com/forms/d/e/1FAIpQLScJ-BUVgJod6NGrreI26pedg8wGEyPhh3WMDskE1hIac_Yp3Q/viewform

What interplay of dynamics...

A nxn matrix M over GF(2) is said to be (r,\delta)-rigid if every matrix M' within \delta n^2 Hamming distance from M has rank at least r. A long standing open problem is to construct explicit rigid matrices. In a recent remarkable result, Alman and...

Please Note: The seminars are not open to the general public, but only to active researchers.

Register here for this event: https://docs.google.com/forms/d/e/1FAIpQLScJ-BUVgJod6NGrreI26pedg8wGEyPhh3WMDskE1hIac_Yp3Q/viewform

The affinity between...

For a function K : R^d x R^d -> R, and a set P = {x_1, ..., x_n} in d-dimension, the K graph G_P of P is the complete graph on n nodes where the weight between nodes i and j is given by K(x_i, x_j). In this paper, we initiate the study of when...

Many of the central problems in computational complexity revolve around proving lower bounds on the amount of resources used in various computational models. In this series of talks, we will discuss three standard objects in computational complexity...

MIP* (pronounced “M-I-P star”) denotes the class of problems that admit interactive proofs with quantum entangled provers. It has been an outstanding question to characterize the complexity of MIP*. Most notably, there was no known computable upper...

I’ll discuss the Noisy Quadratic Model, the toy problem of minimizing a convex quadratic function with noisy gradient observations. While the NQM is simple enough to have closed-form dynamics for a variety of optimizers, it gives a surprising amount...