À¶Ý®ÊÓƵ

Title:Strongly connected orientations and integer lattices

Abstract: Let D = (V, A) be a digraph whose underlying graph is 2-edge-connected, and let P be the polytope whose vertices are the incidence vectors of arc sets whose reversal makes D strongly connected. We study the lattice theoretic properties of the integer points contained in a proper 'slanted' face F of P. We prove under a mild necessary condition that the 0,1 points in FÌýcontain anÌýintegralÌýbasisÌýB, i.e., B is linearly independent, and every integral vector in the linear of span of F is an integral linear combination of B. This result is surprising as the integer points in F do not necessarily form aÌýHilbert basis.

Our result has consequences for head-disjoint strong orientations in hypergraphs, and also to a famous conjecture by Woodall that the minimum size of a dicut of D, say k, is equal to the maximum number of disjoint dijoins. We prove a relaxation of this conjecture, by finding for any odd prime number p, a p-adic packing of dijoins of value k and of support size at most 2|A|. We also prove that the all-ones vector belongs to the lattice generated by the 0,1 points in F, where F is the face of P satisfying x(C) = 1 for every minimum dicut C.

This is based on joint work with Gerard Cornuejols, Siyue Liu, and Olha Silina.

Ìý

Ìý

Title:ÌýExplicit Lossless Vertex Expanders

Abstract: We give the first construction of explicit constant-degree lossless vertex expanders. Specifically, for any ε>0 and sufficiently large d, we give an explicit construction of an infinite family of d-regular graphs where every small set S of vertices has (1−ε)d|S| neighbors (which implies (1−2ε)d|S| unique-neighbors). Our results also extend naturally to construct biregular bipartite graphs of any constant imbalance, where small sets on each side have strong expansion guarantees. The graphs we construct admit a free group action, and hence realize new families of quantum LDPC codes of Lin and M. Hsieh with a linear time decoding algorithm.

Our construction is based on taking an appropriate product of a constant-sized lossless expander with a base graph constructed from Ramanujan Cayley cubical complexes.

Based on joint work with Jun-Ting Hsieh, Alexander Lubotzky, Assaf Reiner, and Rachel Yun Zhang ()

Title:ÌýRandom analogues of Erd\H{o}s-Ko-Rado type results.

Abstract:ÌýThe classical Erd\H{o}s-Ko-Rado (EKR) theorem and its variants can be translated into characterizing maximum co-cliques of graphs in Association schemes. For instance, the classical Erd\H{o}s-Ko-Rado characterizes maximum co-cliques in the Kneser graph. Given a graph $G$, by $G_{p}$, we denote the random subgraph of $G$ in which edges appear independently, each with a probability $p$. In this talk, we consider the following question: for which probabilities is the independence number of $G_{p}$ equal to that of $G$? Bollabas-Narayanan-Raigorodskii investigated the independence numbers of random subgraphs of the Kneser graph. In this talk, we will investigate the independence numbers of random subgraphs of (i) the derangement graph on permutations; and (ii) the perfect matching graphs. The derangement graph is associated with the EKR type result on permutations and the perfect matching graph is associated with EKR type result on perfect matchings. This is joint work with the members of the PIMS Collaborative Research Group on Movement and Symmetry in graphs. ÌýÌý

Title:Arrangements and Likelihood

Abstract: In this talk, we establish connections between hypersurface arrangements and likelihood geometry. The central object is the likelihood correspondence which captures the dependence between data and critical points of the likelihood function of a statistical model parametrized by the polynomials defining the arrangement. In particle physics, this same object is known as the scattering correspondence. The connection to hypersurface arrangements leads to a new description of the prime ideal of the likelihood correspondence, which is often computationally advantageous. This description is based on the Rees algebra of the likelihood module of the arrangement, a module closely related to the module of logarithmic derivations. We present results for generic and graphic arrangements.

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

Title:Faster linear algebra using treewidth

Abstract:

: We look at the complexity of solving sparse linear systems as a function of the treewidth of the instance. That is, the sparse matrix is associated with a sparse graph, and solutions can be found faster when that graph has low treewidth. We give a parameterized algorithm in system size and treewidth achieving the conjectured optimal performance.

This is joint work with Daniel Grier.

Ìý

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 ()

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 1:30pm,

Title:Constraining moduli space cohomology by counting graphs

Abstract: In 1992, Kontsevich defined complexes spanned by graphs. TheseÌý
complexes are increasingly prominent in algebraic topology, geometricÌý
group theory and mathematical physics. For instance, a 2021 theorem byÌý
Chan-Galatius and Payne implies that the top-weight cohomology of theÌý
moduli space of curves of genus g is equal to the homology of a specificÌý
graph complex. I will present a new theorem on the asymptotic growthÌý
rate of the Euler characteristic of this graph complex and explain itsÌý
implication on the cohomology of the moduli space of curves. The proofÌý
involves solving a specific graph counting problem.

Ìý

Title:Splitting algorithms for monotone inclusions with minimalÌýdimension

Abstract: Many situations in convex optimization can be modeled as the problem ofÌýfinding a zero of a monotone operator, which can be regarded as aÌýgeneralization of the gradient of a differentiable convex function. InÌýorder to numerically address this monotone inclusion problem, it isÌývital to be able to exploit the inherent structure of the operatorÌýdefining it. The algorithms in the family of the splitting methodsÌýachieve this by iteratively solving simpler subtasks that are defined byÌýseparately using some parts of the original problem.

In the first part of this talk, we will introduce some of the mostÌýrelevant monotone inclusion problems and present their applications toÌýoptimization. Subsequently, we will draw our attention to a commonÌýanomaly that has persisted in the design of methods in this family: theÌýdimension of the underlying space —which we denote as lifting— of theÌýalgorithms abnormally increases as the problem size grows. This hasÌýdirect implications on the computational performance of the method as aÌýresult of the increase of memory requirements. In this framework, weÌýcharacterize the minimal lifting that can be obtained by splittingÌýalgorithms adept at solving certain general monotone inclusions.ÌýMoreover, we present splitting methods matching these lifting bounds, and thusÌýhaving minimal lifting.

Ìý