Events

Title: Online Competitive Algorithms for Resource Allocation

Abstract:

In online optimization with budgets, the data in the optimization problem is revealed over time. At each step a decision variable needs to be set without knowing the future inputs, while there is a budget constraint that couples the decisions across time.

Title: Erdös-Rényi Graphs

Abstract:

These might not be the Erdös-Rényi graphs you first thought of. Let V be a 3-dimensional vector space over a field of odd order q.

Title: Optimal detection of sparse principal components in high dimension

Abstract:

I will present the paper with this title by Berthet and Rigollet (Ann. Stat., 41 (2013) 1780-1815, https://projecteuclid.org/download/pdfview_1/euclid.aos/1378386239). 

Title: Graph Sparsification by Effective Resistances

Abstract:

We will discuss an application of the matrix concentration inequalities of Tropp to spectral sparsification of graphs.

Title: Recovery of a mixture of Gaussians by sum-of-norms clustering

Abstract:

Sum-of-norms clustering is a method for assigning n points in R^d to K clusters, 1 ≤ K ≤ n, using convex optimization.

Title: From Warragul to Waterloo

Abstract:

As Tom Lehrer once said “Some of you may have run into mathematicians, and therefore had occasion to wonder how they got that way”; this talk will be a partial explanation of how I got this way.

Title: The Erdős-Pósa property for A-paths

Abstract:

Let A be a set of vertices in a graph G. An A-path is a path whose ends are in A. Gallai proved, for any integer k, that there are either k disjoint A-paths or there is a set of at most 2k vertices that hit all A-paths.

Title: The 600-cell

Abstract:

If d ≥ 5, then in R^d there are exactly three regular polytopes (simple, hypercube, dual hypercube). If d = 3 we have the icosahedron and the dodecahedron in addition. If d = 4, there are again two exceptional regular polytopes, the so-called 120-cell and 600-cell.

Title: Stable Matching Overview

Abstract:

This semester, the CombOpt Reading Group studies Stable Matching. In this talk we will introduce the basic concepts in stable matching, provide an overview of the planned papers to be discussed this semester, and mention interesting open questions along the way.

Title: Stochastic optimization methods beyond stochastic gradient descent

Abstract:

We will present a very general framework for unconstrained stochastic optimization which encompasses standard frameworks such as line search and trust region using random models.