Workshop on Semidefinite and Polynomial Optimization CWI, Amsterdam29 August - 2 September, 2022Webpage under construction
The list of invited speakers includes (in alphabetic order)
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.
- Hamza Fawzi (University of Cambridge)
- Sevag Gharibian (Paderborn University)
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!
- Sander Gribling (IRIF, Université de Paris)
Abstract:
Two orthonormal bases of C^d are called mutually unbiased
if the squared modulus of the inner product of any two vectors
in distinct bases is equal to 1/d. A natural question is for which pairs (d,k) there
exist k mutually unbiased bases in dimension d.
- Krystal Guo (University of Amsterdam)
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.
- Etienne de Klerk (Tilburg University)
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).
- David de Laat (TU Delft)
- Jean-Bernard Lasserre (LAAS-CNRS, Toulouse)
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
- Victor Magron (LAAS-CNRS, Toulouse)
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.
- Fernando de Oliveira Filho (TU Delft)
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.
- Ojas Parekh (Center for Computing Research, Sandia National Laboratories)
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.
- Franz Rendl (Klagenfurt University)
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.
- Renata Sotirov (Tilburg University)
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.
- Jordi Tura Bregués (Leiden University)
Abstract:
- Frank Vallentin (Universität zu Köln)
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})$.
- Alex Wang (Carnegie Mellon University, CWI)
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.
- Jeroen Zuiddam (University of Amsterdam)
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). Program
The workshop is planned to start on Monday 29 August (first lecture at 9h30) and end on Friday 2 September (around 12h30).
Registration Participation is free, but registration is mandatory since the workshop has a limited capacity. Please register here. Location CWI, room TBA CWI, Science Park 123, 1098 XG Amsterdam. Accomodation Interested participants may make a hotel reservation at Hotel Casa . Hotel Casa (Eerste Ringdijkstraat 4, Amsterdam) is conveniently located near Amstel train station and from there you can walk, cycle or take the bus to CWI. Organizers
Jop Briët (CWI), Monique Laurent (CWI, Tilburg University)
|