Events

Title: On the hardness of computing the diameter of a polytope

Abstract:

The diameter of a polytope P is given by the maximum length of a shortest path between a pair of vertices on P. Giving bounds on the diameter of a polytope is a fundamental research topic in theoretical computer science and discrete mathematics, motivated by the (still unknown) existence of a polynomial pivot rule for the Simplex Algorithm for solving Linear Programs.

Title: Dyadic matroids with spanning cliques

^{*Please note time and date change}

Abstract:

The Matroid Minors Project of Geelen, Gerards, and Whittle describes the structure of minor-closed classes of matroids representable over a fixed finite field.

Title: Mutually unbiased bases

Abstract:

A pair of d x d unitary matrices is unbiased if M*N is at, i.e., all its entries have the same absolute value. A relatively simple argument shows that a set of pairwise unbiased unitary matrices has size at most d + 1.

Title: Fun with Pfaffians: Identities for Schur Q-Functions

Abstract:

Schur functions determinantal identities (e.g. Jacobi-Trudi, Giambelli) are cornerstones of symmetric function theory. Less well-known are the Pfaffian identities for Schur Q-functions.

Title: Quasi-popular Matchings, Optimality, and Extended Formulations

Abstract:

The goal of this talk is to obtain efficient algorithms for computing desirable matchings (wrt cost) by paying the price of mildly relaxing popularity.

Title: Feynman graphs to chord diagrams

Abstract:

I will explain how classic techniques of algebraic combinatorics can, via chord diagrams, tell us about the leading log, next-to-leading log, etc, expansions in quantum field theory, and what we think chord diagrams can tell us about individual Feynman graphs as well. 

Title: Indicence groups of graphs, forbidden minors, and planar covers

Abstract:

The solution group of binary linear system is a quantum-probabilistic generalization of the solution space of the system.

Title: A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists

Abstract:

We will continue the discussion of stable matching when there are unacceptable pairs and one-sided ties. Two weeks ago, we looked at a 3/2-approximation that was purely combinatorial. 

Title: On the approximability of the stable matching problem with ties of size two and one-sided ties

Abstract:

The stable matching problem is central for game theory. If participants are allowed to have ties, the problem of finding a stable matching of maximum cardinality is an NP-hard problem, even when the ties are of size two.

Title: From Combinatorics to Computer Algebra and Morse Theory - Making Sense of Multivariate Asymptotics

Abstract:

The  asymptotic study  of  multivariate  generating  functions comprises  the  domain  of  Analytic Combinatorics  in Several Variables (ACSV).