Welcome to Combinatorics and Optimization

Title: Alice, Bob, and colours: An algebraic approach to quantum advantage

Abstract: Two-player one-round games exhibit quantum advantage if the availability of quantum resources results in non-classical correlations between the players' answers, which allow outperforming any classical strategy. The first part of the talk illustrates a link between (i) the occurrence of quantum advantage in a game, and (ii) the complexity of the corresponding classical computational problem. In particular, I will show that both (i) and (ii) are determined by the same algebraic invariants of the game, known as polymorphisms. This allows transferring methods from the universal-algebraic theory of constraint satisfaction to the setting of quantum advantage. In particular, this approach yields a complete characterisation of the occurrence of quantum advantage for games played on graphs.   

The second part of the talk outlines recent work on the quantum chromatic number introduced in [Cameron--Montanaro--Newman--Severini--Winter'07]. The gap between this parameter and its classical counterpart is a measure of quantum advantage for the graph colouring game. Using the polymorphic approach, I will show that the maximum gap is linear when the quantum chromatic number makes use of entangled strategies on a constant number of qubits. In contrast, in the case of unlimited entanglement resources, I will prove the existence of graphs whose quantum chromatic number is 3 and whose classical chromatic number is arbitrarily large, conditional to the quantum variants of Khot's d-to-1 Conjecture [Khot'02] and Håstad's inapproximability of linear equations [Håstad'01].

Title: Learning from Coarse Samples

Abstract:Coarsening occurs when the exact value of a sample is not observed.
Instead, only a subset of the sample space containing the exact value is known.
Coarse data naturally arises in diverse fields, including Economics, Engineering, Medical and Biological Sciences, and all areas of the Physical Sciences.
One of the simplest forms of coarsening is rounding, where data values are mapped to the nearest point on a specified lattice.

We survey applications of coarse learning to regression with self-selection bias, regression with second-price auction data, and present details of an SGD-based algorithm for coarse Gaussian mean estimation.

Based on joint work with Alkis Kalavasis and Anay Mehrotra (https://arxiv.org/abs/2504.07133)

Title:Source characterization of the hypegraphic posets

Abstract: For a hypergraph $\mathbb{H}$ on $[n]$, the hypergraphic poset $P_\mathbb{H}$ is the transitive closure of the oriented $1$-skeleton of the hypergraphic polytope $\Delta_\mathbb{H}$, which is the Minkowski sum of the standard simplices $\Delta_H$ for each hyperedge $H \in \mathbb{H}$. In 2019, C. Benedetti, N. Bergeron, and J. Machacek established a remarkable correspondence between the transitive closure of the oriented $1$-skeleton of $\Delta_\mathbb{H}$ and the flip graph on acyclic orientations of $\mathbb{H}$. Viewing an orientation of $\mathbb{H}$ as a map $A$ from $\mathbb{H}$ to $[n]$, we define the sources of the acyclic orientations as the values $A(H)$ for each hyperedge $H \in \mathbb{H}$. In a recent paper, N. Bergeron and V.

Pilaud provided a characterization of $P_\mathbb{H}$ based on the sources of acyclic orientations for interval hypergraphs. Specifically, two distinct acyclic orientations $A$ and $B$ of $\mathbb{H}$ are comparable in $P_\mathbb{H}$ if and only if their sources satisfy $A(H) \leq B(H)$ for all hyperedges $H\in \HH$. The goal of this work is to extend this source characterization of $P_\mathbb{H}$ to arbitrary hypergraphs on $[n]$.

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