Seminar

Title: Flag algebras and subgraph density problems

Abstract: Flag algebras are a tool introduced by Razborov in 2007 that has since been successfully used to approach or solve many problems in asymptotic extremal combinatorics.

Title: Tutorial on Convolutional Neural Networks

Abstract: We have seen stochastic gradient descent and automatic differentiation to help handle the big dimensionality of problems that often occur in machine learning.

Title: The upper density of monochromatic infinite paths

Abstract: Given a complete graph $K_n$, whose edges are coloured in red and blue, what is the longest monochromatic path one can find?

Title: Implementing supersingular isogeny cryptography

Abstract:

Recent years have seen dramatic progress and improvements in the implementation of supersingular isogeny-based cryptosystems.

Title:  A Short Proof of the Containers Theorem for Hypergraphs

Abstract:  A modern trend in extremal combinatorics is extending classical results from the dense setting (e.g. Szemerédi's theorem)

Title: Stability Yields a PTAS for k-Median and k-Means Clustering

Abstract: Previously, we have seen a variety of approximation methods for k-median, and last week we saw

Title: Why Random Reshuffling Beats Stochastic Gradient Descent

Abstract:  Over the first few lectures in the seminar we studied the Stochastic Gradient Descent (SGD) method

Title: Solving DNN Relaxations of the Quadratic Assignment Problem with ADMM and Facial Reduction

Abstract:

The quadratic assignment problem, QAP, has many important applications ranging from the planning of building locations of a university, to the positioning of modules on a computer chip (VLSI design), to the design of keyboards.

Title: Approximation Algorithms for Distributionally Robust Stochastic Optimization

Abstract:

Two-stage stochastic optimization is a widely-used framework for modeling uncertainty, where we have a probability distribution over possible realizations of the data, called scenarios, and decisions are taken in two stages: we make first-stage decisions knowing only the underlying distribution and before a scenario is realized, and may take additional second-stage recourse actions after a scenario is realized.

Title: Approximate Clustering without the Approximation

Abstract: Previously in this CombOpt Reading Group series, we have discussed improving approximation factors for particular distance-based objective functions in clustering problems.