Events

Approximately Counting Flows via Generating Function Optimization

Abstract: In this talk, we will present recent new lower bounds on the number of non-negative integer flows on a directed acyclic graph with specified total vertex flows (or equivalently, the number of lattice points of a given flow polytope, or the coefficients of the A-type Kostant partition function). We will also give a sketch of the proof, which involves three main parts: (1) prove a certain log-concavity property of the associated multivariate generating function, (2) prove bounds on the coefficients in terms of an associated optimization problem, and (3) dualize the optimization problem to obtain the desired lower bounds. If time permits, we will also briefly discuss other applications of this technique, including to approximating Kostka numbers and to the traveling salesperson problem. Joint work with Alejandro Morales, and with Petter Brändén and Igor Pak.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,

Graph Property Testing using the Container Method

Abstract: The Graph and Hypergraph Container Methods have recently been used to obtain multiple striking results across different areas of mathematics. In this talk, we will see how the graph container method is particularly well-suited for the study of some fundamental problems in graph property testing.

The main problem we will discuss in the talk is the Independent Set Testing problem introduced by Goldreich, Goldwasser, and Ron (1998). In this problem, we are given oracle access to a graph on $n$ vertices that either (i) contains an independent set on $\rho n$ vertices, or (ii) is $\epsilon$-far from the property in the sense that at least $\epsilon n^2$ edges must be removed from the graph to make it have an independent set of this size. We will introduce a new container lemma for the latter class of graphs and we will show how this lemma can be used to obtain a near-optimal solution to the Independent Set Testing problem. We will also discuss how variants and extensions of the new container lemma can be used to prove a variety of other results in property testing.

This is joint work with Cameron Seth.

Title: Combinatorial Nullstellensatz and the Erdős box problem

Abstract: In the talk, I will show how Lasoń’s generalization of Alon’s Combinatorial Nullstellensatz can be used to obtain lower bounds on Turán numbers of complete r-partite r-uniform hypergraphs. As an example, I will give a short and simple explicit construction of a hypergraph free of copies of the complete r-partite r-uniform  hypergraph with parts of size 2, thereby providing a lower bound for the so-called Erdős box problem. This asymptotically matches best known bounds when r ≤ 4. 

Title:Coefficient Positivity and Analytic Combinatorics

 Abstract: Given a rational function analytic at the origin, are its power series coefficients positive? We first motivate this question with historical background, examples and connections to decidability questions in combinatorics. We then present a method for proving positivity for a certain class of multivariate rational functions, by constructing explicit error bounds for an asymptotic expansion using analytic combinatorics in several variables. After applying our method to a couple of examples in the literature, including re-proving a (recently proved) conjecture of Gillis, Reznick and Zeilberger from 1983, we discuss the feasibility of completing certain steps in our analysis using methods from computer algebra.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm

Title: Purifying arbitrarily noisy quantum states

Abstract: Quantum state purification is the task of recovering a nearly pure copy of an unknown pure quantum state using multiple noisy copies of the state. We derive an efficient purification procedure based on the swap test for qudits of any dimension, starting with any initial error parameter. For constant initial error parameter and dimension, our procedure has sample complexity asymptotically optimal in the final error parameter, and almost matches the known optimal protocol for qubits. Our protocol has a simple recursive structure that can be applied when the states are provided one at a time in a streaming fashion, requiring only a small quantum memory to implement.  Joint work with Andrew Childs, Honghao Fu, Zhi Li, Maris Ozols, Vedang Vyas. 

Title: Hypercube decompositions and combinatorial invariance for Kazhdan-Lusztig polynomials

Abstract: Kazhdan-Lusztig polynomials are of foundational importance in geometric representation theory. Yet the Combinatorial Invariance Conjecture, due to Lusztig and to Dyer, suggests that they only depend on the combinatorics of Bruhat order. I'll describe joint work with Grant Barkley in which we adapt the hypercube decompositions introduced by Blundell-Buesing-Davies-Veličković-Williamson to prove this conjecture for Kazhdan-Lusztig R-polynomials in the case of elementary intervals in the symmetric group. This significantly generalizes the main previously known case of the conjecture, that of lower intervals.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm.