Seminars

We revisit the question of reducing online learning to approximate optimization of the offline problem. In this setting, we give two algorithms with near-optimal performance in the full information setting: they guarantee optimal regret and require...

We consider the following question: how many points with bounded norm can a "non-degenerate" lattice have. Here, by a "non-degenerate" lattice, we mean an n-dimensional lattice with no surprisingly dense lower-dimensional sublattices.

Dadush and...

Polynomial optimization over hypercubes has important applications in combinatorial optimization. We develop a symmetry-reduction method that finds sums of squares certificates for non-negative symmetric polynomials over k-subset hypercubes that...

Datasets are often used multiple times with each successive analysis depending on the outcomes of previous analyses on the same dataset. Standard techniques for ensuring generalization and statistical validity do not account for this adaptive...

In this talk, we consider the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. We present an explicit binary tree code with constant distance and alphabet size polylog(n), where n is the depth...

What is the probability that the number of triangles in the Erd\H{o}s-R\'enyi random graph with edge density $p$, is at least twice its mean? What is the typical structure of the graph conditioned on this rare event? For instance, when $p=o(1)$...

Three fundamental factors determine the quality of a statistical learning algorithm: expressiveness, optimization and generalization. The classic strategy for handling these factors is relatively well understood. In contrast, the radically different...

Algorithmic graph partitioning tasks are naturally related to geometric issues. Over the past decades, several deeper connections of this type have emerged. In this talk, we will describe one example by showing that, up to lower order factors, the...

We prove that if every problem in NP has n^k-size circuits for a fixed constant k, then for every NP-verifier and every yes-instance x of length n for that verifier, the verifier's search space has a witness for x that can be encoded with a circuit...

We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the...