Abstract: In this lecture we will present several eigenvalue bounds on the independence number and the distance chromatic number of graph powers. We will see how to use polynomials and mixed-integer linear programming in order to optimize such bounds. Some infinite families of graphs for which the new bounds are tight will also presented.

Abstract: SDPs are the go-to method for approximating NP-complete Boolean constraint satisfaction problems (CSPs). Quantumly, the generalization of CSPs is the fundamental k-local Hamiltonian problem, which asks: Given a many-body quantum system, what energy level does the system relax into when cooled to near absolute zero? In this work, we formally introduce the k-local Hamiltonian problem, and discuss various SDP approaches for giving non-trivial approximations. For example, how well can general quantum CSPs be approximated? How about CSPs where the constraints take a very specific, physically motivated, form? No quantum background is required, though naturally some background is always helpful!

Abstract: We explore the interplay between algebraic combinatorics and some algorithmic problems in graph theory. We define a polynomial with connections to correspondence colouring, a recent generalization of list-colouring, and the Unique Games Conjecture. Like the chromatic polynomial of a graph, we are able to evaluate this polynomial at -r+1 modulo r^n, despite the complexity of computing this polynomial. This is based on joint work with Chris Godsil and Gordon Royle.

Abstract: Semidefinite programming performance estimation is a technique for the worst-case analysis of iterative algorithms. It was pioneered by Drori and Teboulle in 2014, and has since been applied successfully to a variety of methods, including (stochastic) gradient descent, accelerated gradient descent, the convex-concave procedure (DCA), the alternating direction method of multipliers (ADMM), etc. In this talk I will discuss some recent developments in this area. My talk will cover joint work with Hadi Abbaszadehpeivasti and Moslem Zamani, performed as part of the NWO ENW-GROOT project Optimization for and with Machine Learning (OPTIMAL).

Abstract: In this talk we briefly describe the Christoffel-Darboux (CD) kernel and the Christoffel function (CF), well-known tools from the theory of approximation. We next describe some of their recent applications as a simple and easy to use tool for
- approximating the graph of a function,
- interpolation of a function from finitely many values,
- detection of outliers.
Finally we will also exhibit a simple and perhaps surprising connexion with optimization and sums-of-squares.

Abstract: Motivated by recent progress in quantum information theory, this talk aims at presenting how to optimize over trace polynomials, i.e., polynomials in noncommuting variables and traces of their products.
A novel Positivstellensatz certifying positivity of trace polynomials subject to trace constraints is presented, and a hierarchy of semidefinite relaxations converging monotonically to the optimum of a trace polynomial subject to tracial constraints is provided.
This hierarchy is applied to bound violations of polynomial Bell inequalities as well as to detect entanglement in multipartite Werner states. This is joint work with Felix Huber, Igor Klep and Jurij Volcic.

Abstract: Witsenhausen's problem asks: what is the maximum measure of a subset of the (n-1)-dimensional unit sphere having no orthogonal points? Only lower and upper bounds for this maximum measure are known for n >= 3. The best known upper bound is given by Kalai's double-cap conjecture, which states that the maximum is achieved by two open antipodal 45-degree-radius spherical caps. An upper bound for the maximum measure can be obtained from a suitable extension of the Lovász theta number. I will discuss a 3-point bound for this problem, based on copositive programming, which improves on the best known upper bounds.
Joint work with Bram Bekker, Olga Kuryatnikova, and Juan Vera.

Abstract: The local Hamiltonian (LH) problem serves as a natural quantum generalization of classical constraint satisfaction problems (CSP). We leverage this connection to generalize classical approximation algorithms for CSP, based on semidefinite programming hierarchies, to the quantum LH case. We employ the recently introduced Quantum Max Cut (QMC) problem as a model QMA-hard 2-LH instance to illustrate our approach, in the same vein that Max Cut is a model 2-CSP that has driven development of classical approximation and hardness results for CSPs. We will discuss many recent results on approximation and hardness for QMC and more general instances of 2-LH. Although approximating 2-LH bears similarity to approximating 2-CSP, the former does take some unexpected turns.

Abstract: The Lovász Theta function provides a well studied tool to get bounds for the stability number and the chromatic number of graphs. It is the optimal value of a semidefinite program in matrices of order n having m equality constraints plus possibly some additional sign constraints. Here n denotes the number of vertices and m the number of edges of the underlying graph. The number m of equations may be of order quadratic in n which limits the practical use of the Theta function.
We introduce a new way to obtain bounds which is derived from a quadratic 0-1 optimization problem having exactly k variables equal to 1. This allows us to move the m equality constraints into the objective function, leaving a semidefinite program with only 2n equality constraints independent of the number m of edges. Surprisingly, this relaxation is closely related to Schrijver's refinement of the Theta function for the stability number, and to Szegedy's strengthening of the Theta function in the coloring case.
We propose a further tightening of this bound using the exact subgraph idea in a new way. Rather than looking at subgraphs with a small number of vertices which should be contained in the respective polytope, we now consider subgraphs where the stability number is small (but could have a large number of vertices) and require them to be contained in the corresponding polytope. Computational results on a series of graphs from the literature show the strong potential of this approach.

Abstract: The Chvátal-Gomory (CG) cutting-plane procedure is considered to be among the most celebrated results in integer programming. We extend the Chvátal-Gomory (CG) cutting-plane procedure to integer semidefinite programs (ISDPs). We present an explicit formulation of the elementary closure of spectrahedra that relies on the data matrices of the ISDP. This formulation enables us to introduce Chvátal-Gomory cuts and strengthened Chvátal-Gomory cuts for ISDPs. We also show how to derive a polyhedral description of the elementary closure for a specific class of spectrahedra based on the SDP equivalent of total dual integrality.
In the second part of the talk, we show how to exploit (strengthened) CG cuts in a branch-and-cut framework for ISDPs. Different from existing algorithms for solving ISDPs, the separation routine in our approach exploits both the semidefinite and the integrality constraints. We derive separation routines for common classes of binary SDPs resulting from combinatorial optimization problems. We also demonstrate the practical strength of the CG cuts in a branch-and-cut algorithm, which outperforms alternative ISDP solvers.
This is joint work with F. de Meijer

Abstract:

Abstract: Least distortion embeddings of flat tori into Hilbert space were first studied by Khot and Naor in 2006. A flat torus is the metric space given by the quotient $R^n / L$ with some $n$-dimensional lattice $L$. Khot and Naor showed that these kind of metric spaces can be highly non-Euclidean in the sense that all embeddings of the flat torus into some Hilbert space have distortion at least $\Omega(\sqrt{n})$.
Haviv, Regev (2010) and Agarwal, Regev, Tang (2020) extended these results and constructed excellent embeddings of flat tori having low distortion. One motivation is that studying the Euclidean distortion of flat tori might have applications to the complexity of lattice problems, like the closest vector problem, and might also lead to more efficient algorithms for lattice problems through the use of our metric embeddings.
In this talk I want to add a semidefinite optimization perspective to this story. For finite metric spaces it is known that one can compute least distortion Euclidean embeddings via an SDP. I want to extend this result from finite metric spaces to flat tori. This will yield, via SDP duality, an algorithmic method for proving nonembeddability results. In particular, this leads to new, simple proofs of (strengthenings of) previous results as well as the possibility to find optimal embeddings of given flat tori.
Based on joint work with A. Heimendahl, M. Lücke, M.C. Zimmermann.

Abstract: In this lecture, we will discuss a new storage-optimal first-order method for solving a special class of semidefinite programs (SDPs) to high accuracy. The class of SDPs that we consider, the "exact QMP-like SDPs" is characterized by low-rank solutions, a priori knowledge of the restriction of the SDP solution to a small subspace, and standard regularity assumptions such as strict complementarity. Crucially, we show how to use a "certificate of strict complementarity" to construct a low-dimensional strongly convex minimax problem whose optimizer coincides with a factorization of the SDP optimizer. From an algorithmic standpoint, we show how to construct the necessary certificate and how to solve the minimax problem efficiently.

Abstract: Posed by Shannon in 1956, understanding the amount of information that can be transmitted perfectly over a noisy communication channel (the Shannon capacity of graphs) is a longstanding and central open problem in information theory, graph theory and combinatorial optimization. This problem is part of the broader theme of direct-sum problems, which ask: What is the cost of a task if we have to perform it many times? We will discuss an approach to the study of Shannon capacity (and other direct-sum problems) via real algebraic geometry, and in particular a Positivstellensatz of Strassen that provides a dual description (called asymptotic spectrum duality) of the Shannon capacity. This realizes a framework that unifies known computational methods and structural theorems, and provides new directions in the study of Shannon capacity (including a new notion of graph limits).