Events

Title: Quantum Log-Approximate-Rank Conjecture is also False

Abstract:

In a recent breakthrough result, Chattopadhyay, Mande and Sherif [ECCC TR18-17] showed an exponential separation between the log approximate rank and randomized communication complexity of a total function `f', hence refuting the log approximate rank conjecture of Lee and Shraibman [2009].

Title: Approximately counting independent sets in graphs with bounded bipartite pathwidth

Abstract:

In 1989, Jerrum and Sinclair showed that a natural Markov chain for counting
matchings in a given graph G is rapidly mixing.

Title: Hedetnemi's conjecture is false

Abstract:

On may 6th 2019, Yaroslav Shitov found a graph G x H such that the chromatic number of G x H is strictly smaller than the minimum of the chromatic number of G and the chromatic number of H. I will present the example.

Title: Toric varieties from distributive lattices

Abstract:

Given a nite lattice L, consider the ring of complex polynomials in indeterminates indexed by L, modulo the ideal generated by (XaXb-Xa^bXa_b for all a; b 2 L).

Title: Popular Matchings

Abstract:

We introduce a variant of the stable matching problem on a bipartite graph G = (A [ P;E)

Title: Deducing Kurdyka-Łojasiewicz exponent of optimization models

Abstract:

Kurdyka-Łojasiewicz (KL) exponent is an important quantity for determining the qualitative convergence behavior of many first-order methods.

Title: Spanning trees and electrical networks... and what about matroids?

Abstract:

The relevance of spanning trees to the theory of electrifcal networks goes all the way back to Kirchhoff in 1847.

Title: Popularity, Mixed Matchings, and Self-duality

Abstract:

This week we continue our discussion of popular matchings.

Title: Matching Games: From Bargaining to the Nucleolus

Abstract:

Cooperative matching games were first introduced in seminal work by Shapley and Shubik in their classic 1971 paper. In this talk, I will first review some of the key concepts and results in this area. I will then use these tools to (re-)derive several facts and algorithms for network generalizations of the famous Nash bargaining concept.

Title: Arborified zeta values and shuffles of rooted trees

_{*Please note room change}

Abstract:

Arborified zeta values are a generalisation to rooted trees of the usual multizeta values.