Events

Title: Stable marraige with general preferences

Abstract:

This week, we discuss a generalization of the standard stable marriage problem, in which one side has a complete, totally ordered, strict preference list while the other has preferences given in terms of arbitrary binary relations.

Title: Optimization and Cryptography in Generalized Physical Theories 

Abstract:

In this talk, I will discuss three important cryptographic tasks in the quantum and post-quantum world. I will discuss the impossibility of bit-commitment and coin-flipping, and also the possibility of physically unforgeable money in the framework of Generalized Physical Theories (GPTs).

Title: Feynman graphs, ribbon graphs and tensor graphs

Abstract:

In this talk I will define the so-called Feynman graphs, which are a particular class of graphs appearing in quantum field theory.

Title: Continuous Quantum Walks

Abstract:

Continuous quantum walks are of considerable interest in quantum physics and quantum computing.

Title: Upsetting Matrices

Abstract: 

Title: Independence Polynomials and Their Roots

Abstract:

Independence polynomials are generating functions for the number of independent sets of each cardinality in a graph G.

Title: Signings and induced subgraphs of the Hypercube

Abstract:

Just over a month ago, Hao Haung resolved the sensitivity conjecture, a 30 year-old question about the complexity of boolean functions.

Title: Approximation Algorithms for Minimum-Norm Optimization Problems

Abstract:

In many optimization problems, a feasible solution induces a multidimensional cost vector. For example, in k-clustering, opening k facilities induces an assignment-cost vector indexed by the clients; in load-balancing, a schedule induces a load vector across the machines.

Title: Polynomial Spaces

Abstract:

We describe some simple machinery that enables us to derive upper bounds on the size of codes, and lower bounds on the size of designs in a quite general setting.

Title: Combinatorial questions motivated by Invariant Theory

Abstract:

We begin the talk by discussing a question in Invariant Theory: given a representation $V$ of a Lie group $G$, when if the invariant ring $k[V]^G$ a polynomial ring? We give a conjectural answer which we have verified for $SL_n$ and discuss some combinatorial questions motivated by the proof. This is joint work with Dan Edidin.