Events

Title: Recognizing slack matrices

Abstract:

This week, we will be discussing the topic of slack matrices. Slack matrices arise in the context of lifts of polytopes, where, given a polytope P, we can characterize the existence of a lift of P of a given size in terms of properties of an associated slack matrix.

Title: Binary Submatroids

Abstract:

A binary matroid can be thought of as a set of nonzero binary vectors.

Title: Rectangular Catalan Algebraic Combinatorics

Abstract:

The enumeration of Dyck-like lattice paths in a m x n rectangle has a long and fruitful history culminating in Bizley-Grossman’s formula (1954). We will discuss how it is natural to extend this formula to weighted enumeration, with parameters accounting for such statistics as area; and to consider parking-function analogs.

Title: Proof of the monotone column permanent conjecture

Abstract: 

In 1993, Jim Haglund conjectured the following.  If  A  is a  square matrix of real numbers which are weakly decreasing down each column, and J is the all-ones matrix of the same size, then the permanent of the matrix xJ+A is a polynomial with only real roots.

Title: Improving the general upper bound for Hadwiger's conjecture

Abstract:

In 1943, Hadwiger conjectured that every K_t-minor-free graph has chromatic number at most t-1.

Title:

Abstract:

Differential privacy is about preserving an individuals privacy while maintaining utility in the context of data analysis.

Title: Widths in even-hole-free graphs

Abstract:

Historically, the study of even-hole-free graphs is motivated by the analogy with perfect graphs. The decomposition theorems that are known for even-hole-free graphs are seemingly more powerful than the ones for perfect graphs: the basic classes and the decompositions are more restricted.

Zoom (for information email emma.watson@uwaterloo.ca) 

Title: Hardness of set-partitioning formulation for the vehicle routing problem with stochastic demands

Abstract:

The vehicle routing problem considers the cheapest way to serve a set of customers using a fixed set of vehicles. When a vehicle serves a customer, it picks up its demand which is given as an input, and the total demand picked up cannot exceed the vehicle’s capacity. This classical combinatorial optimization problem combines aspects of routing (like a traveling salesman problem) and packing (like a knapsack problem).

Title: Combinatorial masters in QED

Abstract:

Calculations in perturbative QED (and also in QCD) use a reduction from Feynman integrals to `master integrals'. In general, the reduction to master integrals is performed by excessive use of computer power.

Zoom (for information email emma.watson@uwaterloo.ca) 

Title: Permanent Hardness from Linear Optics

Abstract:

One of the great accomplishments in complexity theory was Valiant's 1979 proof that the permanent of a matrix is #P-hard to compute.  Subsequent work simplified Valiant's ideas and even began to recast them as problems in quantum computing.  In 2011, this culminated in a striking proof by Aaronson, based solely on quantum linear optics, of the #P-hardness of the permanent.