Events

Title: The Probabilistic Set-Covering Problem

Abstract: In the classical set-covering problem, we have a set of items and a set S of subsets of the items. The objective is to find a min-cost subset C of S which covers every item, i.e., where every item is contained in at least one of the subsets in C. The probabilistic set-covering problem (PSC) generalizes this to a stochastic setting where the objective is to find a min-cost covering which covers a random subset of the items with probability at least p. We will discuss some structural properties of this problem which lead to a branch-and-bound algorithm for solving it.

Title: Hadamard’s Maximal Determinant Problem and Generalisations

Abstract:  Any matrix $M$ of order $n$ with entries taken from the complex unit disk satisfies Hadamard’s determinantal inequality $|\det M|\leq n^{n/2}$. Matrices meeting this bound with equality have pairwise orthogonal rows and columns. Such matrices are known as Hadamard matrices, and character tables of finite abelian groups give examples at every order.

Title: A raising operator formula for Macdonald polynomials

Abstract: In this talk, I will give a brief introduction on Catalanimal, a tool that helps us to prove the shuffle theorem under any line, the extended delta conjecture and the Loehr- Warrington conjecture. I will then focus on its variant "Macanimal" which gives us an explicit raising operator formula for the modified Macdonald polynomials. Our method just as easily yields a formula for an infinite series of $GL_l$ characters which truncates to the modified Macdonald polynomials.

Title: Stochastic Minimum Norm Combinatorial Optimization

Abstract: In this work, we introduce and study stochastic minimum-norm optimization. We have an underlying combinatorial optimization problem where the costs involved are random variables with given distributions; each feasible solution induces a random multidimensional cost vector. The goal is to find a solution that minimizes the expected norm of the induced cost vector, for a given monotone, symmetric norm.

Title: The ADMM:  Past, Present, and Future

Abstract: Over the past 15 years, the alternating direction method of multipliers (ADMM) has become a standard optimization method.  This talk will cover the origins of the ADMM, its subsequent development, and what to expect in the future.

Title: Cliques in dense matroids

Abstract: We will give a singly exponential bound on the number of points a $U_{2,q+2}$-minor-free matroid can have without containing $M(K_{q+2})$ as a minor.

Title: Equiangular lines and algebraic number theory

Abstract: It is believed that SICs, that is maximal equiangular tight frames, exist in all complex vector spaces. To construct them we use the Weyl-Heisenberg groups, and hence the cyclotomic numbers (roots of unity).

Title: The Hat Guessing Number of Graphs

Abstract:  The hat guessing number HG(G) of a graph G on n vertices is defined in terms of the following game: n players are placed on the n vertices of G, each wearing a hat whose color is arbitrarily chosen from a set of q possible colors. Each player can see the hat colors of his neighbors, but not his own hat color. All of the players are asked to guess their own hat colors simultaneously, according to a predetermined guessing strategy and the hat colors they see, where no communication between them is allowed.

Title: Approximation Algorithms for Stochastic Knapsack 

Abstract: The classical Knapsack problem takes as input a set of items with some fixed nonnegative values and weights. The goal is to compute a subset of items of maximum total value, subject to the constraint that the total weight of these elements is at most a given limit. In this talk we review a paper by Gupta, Krishnaswamy, Molinaro and Ravi, in which the following stochastic variation of this problem is considered: the value and weight of each item are correlated random variables with known, arbitrary distributions.

Title: Sylvester, Gallai, and their complex relatives

Abstract: Given any finite set of points in the real plane, not all collinear, there is a line in the plane that contains exactly two of them. This pretty result was conjectured by Sylvester in 1893 and proved by Gallai in 1944. We will present an extension of the result to higher dimensional complex spaces and discuss some related conjectures. This is joint work with Matthew Kroeker.