Events - July 2022

Title: Stochastic Load Balancing on Unrelated Machines

Abstract: We will take a look at the stochastic load balancing problem. The goal is to assign tasks to machines, so that the maximum amount of time taken by any machine to complete all its assigned tasks is minimized. The stochastic twist to this problem is that now the time required to complete each task is a random variable sampled from some known distribution. For the stochastic version, we need to minimize the maximum time taken by any machine in expectation. We will look at a constant factor approximation algorithm for this problem that appeared in a recent paper by Gupta, Kumar, Nagarajan and Shen.

Title: Strongly regular graphs with a regular point 

Abstract:  Arising from Hoffman and Singleton's study of Moore graphs, strongly regular graphs play an important role in algebraic graph theory. Strongly regular graphs can be construct from geometric objects, such as generalized quadrangles and certain geometric properties, such as having a regular point, can be studied in the context of graphs.

Title: High-Rank Matroids and Unavoidable Flats

Abstract: We discuss a variety of questions and results pertaining to conjectures of Geelen from 2021 on the unavoidable flats in matroids of sufficiently high rank. We will also explore the differences in how such questions are posed for various classes of matroids, why such differences are necessary, and how they could potentially be reconciled. A result for the class of binary matroids and an outline of its proof will be discussed in detail. Joint work with Jim Geelen.

Title: Positivity and sums of squares in products of free algebras

Abstract: A noncommutative polynomial is said to be positive relative to some constraints if plugging matrices (or more generally, operators on a Hilbert space) satisfying the constraints into the polynomial always yields a positive operator. It is a natural problem to determine whether or not a given polynomial is positive, and if it is, to find some certificate of positivity. This problem is closely connected with noncommutative polynomial optimization, where we want to find matrices or operators that maximize the operator norm of some polynomial, subject to the constraint that some other polynomials in the operators are positive or vanish. When the algebra cut out by the constraints is a free algebra, free group algebra, or similar algebra, it's well-known that a polynomial is positive on operators satisfying the constraints if and only if it's a sum of Hermitian squares in the algebra.

Title: An identity in the group algebra of the symmetric group

Abstract: Come with me on a magical journey into the mysterious world of inverse Wronskians.

Title: Strong Cospectrality in Trees

Title: Stochastic Optimization

Abstract: While deterministic optimization problems are very useful in practice, often times the assumption that all data is known in advance does not hold true. One possible way to relax this assumption is to assume that the data depends on random variables. This assumption leads to stochastic optimization problems.

Title: Bounded treewidth in hereditary graph classes

Abstract: A highlight of the superb graph minors project of Robertson and Seymour is their so-called Grid Theorem: a minor-closed class of graphs has bounded treewidth if and only it does not contain all planar graphs. Which induced-subgraph-closed graph classes have bounded treewidth?