DMO Seminar Archives

21 juni 2024 11:00 t/m 12:00

[DMO] Blaine Keetch: Graph diffusion applied to isomorphic and non-isomorphic graphs

"Given two graphs G1 and G2, a graph isomorphism is a bijection which maps the nodes of G1 to the nodes of G2, such that the edges of the graphs are preserved in the bijection. Two graphs are said to be isomorphic if there exists an isomorphism of their nodes.
In this talk, I will present some preliminary results showing that two graphs are isomorphic, if and only if, their graph diffusion operators are isomorphic, and show how, subject to an appropriate choice of initial condition, graph diffusion can be applied to test for graph isomorphism. I will also present some preliminary context on algorithm complexity classes, the graph isomorphism problem, spectral graph theory, and graph diffusion."

14 juni 2024 16:00 t/m 17:00

[DMO] Tomohiro Koana: Determinantal sieving

"We introduce a new, remarkably powerful tool to the toolbox of algebraic FPT algorithms, determinantal sieving. Given a polynomial P(x_1,..,x_n) over a field F of characteristic 2, on a set of variables X={x_1,...,x_n}, and a linear matroid M=(X, I) over F of rank k, in 2^k evaluations of P we can sieve for those terms in the monomial expansion of P which are multilinear and whose support is a basis for M. The known tools of multilinear detection and constrained multilinear detection then correspond to the case where M is a uniform matroid and the truncation of a disjoint union of uniform matroids, respectively. More generally, let the odd support of a monomial m be the set of variables which have odd degree in m. Using 2^k evaluations of P, we can sieve for those terms m whose odd support spans M. Applying this framework to well-known efficiently computable polynomial families allows us to simplify, generalize and improve on a range of algebraic FPT algorithms, such as:
* Solving q-Matroid Intersection in time O*(2^{(q-2)k}) and q-Matroid Parity in time O*(2^{qk}), improving on O*(4^{qk}) for matroids represented over general fields (Brand and Pratt, ICALP 2021)
* T-Cycle, Colourful (s,t)-Path, Colourful (S,T)-Linkage in undirected graphs, and the more general Rank k (S,T)-Linkage problem over so-called frameworks (see Fomin et al., SODA 2023), all in O*(2^k) time, improving on O*(2^{k+|S|}) and O*(2^{|S|+O(k^2 log(k+|F|))}), respectively
* Many instances of the Diverse X paradigm, finding a collection of r solutions to a problem with a minimum mutual distance of d in time O*(2^{r^2 d/2}), improving solutions for k-Distinct Branchings from time 2^{O(k \log k)} to O*(2^k) (Bang-Jensen et al., ESA 2021), and for Diverse Perfect Matchings from O*(2^{2^{O(rd)}}) to O*(2^{r^2d/2}) (Fomin et al., STACS 2021)
For several other problems, such as Set Cover, Steiner Tree, Graph Motif and Subgraph Isomorphism, where the current algorithms are either believed to be optimal or are proving exceedingly difficult to improve, we show matroid-based generalisations at no increased cost to the running time. In the above, all matroids are assumed to be represented over fields of characteristic 2 and all algorithms use polynomial space. Over general fields, we achieve similar results at the cost of using exponential space by working over the exterior algebra. For a class of arithmetic circuits we call strongly monotone, this is even achieved without any loss of running time. However, the odd support sieving result appears to be specific to working over characteristic 2.
This is joint work with Eduard Eiben and Magnus Wahlström."

13 juni 2024 16:00 t/m 17:00

[DMO] Yinyu Ye: Recent Computational Progress on Linear Programming Solvers

"We describe some recent algorithmic advances in the development of general-purpose linear and semidefinite programming (LP/SDP) solvers. They include:
LP pre-solver based on a fast online LP algorithm
Smart crossover from approximate LP solution to optimal basic solution
ADMM-based method
First-order method PDHG using GPU architecture

Most of these techniques have been implemented in the emerging optimization numerical solver COPT, and they increased the average solution speed by over 3x in the past three years on a set of benchmark LP/SDP problems. For certain problem types, the speedup is more than 50x, and problems that have taken days to solve or never been solved before are now solved in minutes to high accuracy."

25 april 2024 16:00 t/m 17:00

[DMO] Sam Mattheus: Good lower bounds for off-diagonal Ramsey numbers from explicit constructions over finite fields

We will present a recent approach, due to Mubayi and Verstraete, for lower bounds on off-diagonal Ramsey numbers. This approach, unlike previous results, has a strong non-probabilistic component. The main ingredient are certain explicit pseudorandom graphs which are often constructed from algebraic varieties over finite fields. This idea culminated in a recent breakthrough of Verstraete and myself in the determination of the asymptotic growth of the off-diagonal Ramsey number r(4,t), resolving a long-standing conjecture by Erdős. I will discuss some explicit constructions that appear in our and related work, and pose some open problems.

14 maart 2024 11:00 t/m 12:00

[DMO] Lander Verlinde: Optimal planning of autonomous reconnaissance missions

This talk will be about the research that I have done at the Netherlands Defence Academy during my internship. Under the supervision of Relinde Jurrius, I investigated how to optimise reconnaissance missions by autonomous systems. A reconnaissance mission behind enemy lines is a complex and dangerous task which should be carefully planned, even when performed by unmanned drones. Starting from a secure base, multiple surveillance locations need to be safely reached and the acquired information has to be transferred back to the base. Such a transfer can be achieved by transmitting information to the base or by physically returning it. However, each action in the mission carries the risk of detection – the drone could be spotted during movement, or transmissions might be intercepted. This task gives rise to a graph where the edge weights are the probabilities to safely cross without being spotted and the vertex weights are the probabilities of safely transmitting information. If information is not transmitted at a vertex, it is carried to the next one, where a new choice between transmitting or continuing is presented. The goal of the research was to find the route and send strategy which maximise the expected value of the amount of information that safely reaches the base.

26 januari 2024 14:00 t/m 15:00

[DMO] Nando Leijenhorst: Rounding SDP solutions to exact fields

In discrete geometry, we use semidefinite programming to bound quantities such as the maximum size of spherical codes. When these bounds are sharp (that is, there is a construction reaching the bound), complementary slackness can give us information about these constructions. However, to use the complementary slackness, we need exact optimal solutions to the SDP rather than numerical approximations. We improve the rounding procedure of Dostert, de Laat and Moustrou, which works well for small semidefinite programs but is too slow for larger examples. In this talk, I will explain the main difficulties when rounding, and how we approach them. This is joint work with Henry Cohn and David de Laat.

20 december 2023 14:00 t/m 15:00

[DMO] Josse van Dobben de Bruyn: A graph with trivial automorphism group and non-trivial quantum automorphism group

A current research theme in quantum graph theory is to determine which classical/quantum groups can occur as the classical/quantum automorphism group of finite graphs. One question in this direction is to determine how far the classical and quantum automorphism groups can be apart. In this talk, I will present a class of graphs which have trivial automorphism group and non-trivial quantum automorphism group, thereby answering a question asked by several authors in recent years. The construction is inspired by linear constraint system games in quantum information theory. This talk is based on joint work<https://arxiv.org/abs/2311.04889> with David E. Roberson and Simon Schmidt.

14 december 2023 14:00 t/m 15:00

[DMO] Esther Julien: Neur2RO: Neural two-stage robust optimization

Robust optimization provides a mathematical framework for modeling and computing solutions to decision-making problems under worst-case uncertainty. In this talk I will present recent work in two-stage robust optimization (2RO) problems, wherein first-stage and second-stage decisions are made before and after uncertainty is realized. This results in a nested min-max-min optimization problem, which generally means that we are dealing with computationally challenging problems, especially in case of integer decisions. Together with my co-authors, we propose Neur2RO, an efficient machine learning-based algorithm. We learn to estimate the value function of the second-stage problem via a neural network architecture designed to construct an easy-to-solve surrogate optimization problem. Our computational experiments on two 2RO benchmarks demonstrate that we can find near-optimal solutions among different sizes of instances, often within orders of magnitude less computing time.
In this talk we mostly focus on multi-colouring. An (n,k)-colouring of a graph is an assignment of a k-subset of {1, 2, . . . , n} to each vertex such that adjacent vertices receive disjoint subsets. And the question we are looking at is: given a graph G that is (n,k)-colourable, how large can we guarantee an (n',k')-colourable induced subgraph to be (for some given (n',k'))? Answering that question leads to having to look at combinatorial objects such as set systems and Kneser graphs, and is connected to several open problems in those areas.
This is joint work with Xinyi Xu.

23 november 2023 14:00 t/m 15:00

[DMO] Lara Scavuzzo Montaña : Lattice reformulations for Integer Programming

Integer Programs (IP) play a pivotal role in addressing complex optimization problems with discrete decision variables. IPs are typically solved with the branch-and-bound algorithm using single-variable disjunctions. In contrast, all algorithms for IP that offer theoretical guarantees use a non-binary search tree with general disjunctions based on lattice structure. These algorithms are not used in practice because such disjunctions are expensive to compute and challenging to implement. However, some lessons can be drawn. In this presentation, we will discuss algorithms for IP using that point of view. In particular, we will discuss lattice reformulations for IP, which can be re-interpreted as heuristic methods to obtain general disjunctions in the original space.

17 november 2023 14:00 t/m 15:00

[DMO] Carla Groenland: Graph reconstruction from small cards

The graph reconstruction conjecture states that each graph G on at least 3 vertices can be reconstructed from the multiset of all induced subgraphs on n-1 vertices. Although this conjecture is notoriously difficult, it is easy to reconstruct some information about the graph, e.g. the degree sequence of G and whether G is connected. We study a set-up with smaller induced subgraphs ('small cards'). Using a theorem about the number of positive real roots of a complex polynomial, we show the induced subgraphs on 0.9n vertices determine whether an n-vertex graph is connected and we also develop counting techniques to reconstruct trees from subgraphs of size about 8n/9.
This is based on joint work with Tom Johnston, Alex Scott and Jane Tan.

10 november 2023 14:00 t/m 15:00

[DMO] Clément Legrand-Duchesne: The structure of quasi-transitive graphs

An infinite graph is quasi-transitive if its vertex set has finitely many orbits under the action of its automorphism group. We obtain a structure theorem for locally finite quasi-transitive graphs avoiding a minor, which is reminiscent of the Robertson-Seymour Graph Minor Structure Theorem. As applications of this result, we prove that every locally finite quasi-transitive graph attains its Hadwiger number, that is, if such a graph contains arbitrarily large clique minors, then it contains an infinite clique minor. This answers a question of Thomassen from 1992. We also prove the minor-excluded case of a conjecture of Ballier and Stein (2018) on the domino problem.

03 november 2023 14:00 t/m 15:00

[DMO] Jan van den Heuvel : Partial Colourings

Suppose you have a graph G for which you know the vertices can be properly coloured with t colours, but you only have s < t colours available. Then it is an easy observation that you can still properly colour at least a fraction s/t of the vertices of G. (More formally: there exists an induced subgraph H of G such that H is s-colourable and |V(H)| ≥ s/t|V(G)|.) But the situation is less clear when we look at other types of colourings, such as list-colourings, fractional colourings, multi-colourings, etc.
In this talk we mostly focus on multi-colouring. An (n,k)-colouring of a graph is an assignment of a k-subset of {1, 2, . . . , n} to each vertex such that adjacent vertices receive disjoint subsets. And the question we are looking at is: given a graph G that is (n,k)-colourable, how large can we guarantee an (n',k')-colourable induced subgraph to be (for some given (n',k'))? Answering that question leads to having to look at combinatorial objects such as set systems and Kneser graphs, and is connected to several open problems in those areas.
This is joint work with Xinyi Xu.

27 oktober 2023 14:00 t/m 15:00

[DMO] Norbert Zeh: An FPT Algorithm for Scanwidth

We show that the scanwidth of a directed acyclic graph can be computed in O(f(k) * poly(n)) time, where k is the scanwidth. The scanwidth is yet another width measure of graphs, one that has been shown to be useful in phylogenetics; as an example, the tree containment problem can be solved efficiently when parameterized by the scanwidth of the network given as part of the input. Recently, Holtgrefe presented an O(n^f(k)) algorithm to compute the scanwidth of a DAG, leaving open the question whether there exists an algorithm with FPT running time (O(f(k) * poly(n))). Over the last two weeks, Holtgrefe, van Iersel, Jones, and I developed such an algorithm, borrowing ideas from similar algorithms for treewidth, pathwidth, and cutwidth. This talk reviews what scanwidth is and describes our algorithm.

13 oktober 2023 14:00 t/m 15:00

[DMO] Mark Jones: Reconstructing phylogenetic networks from DNA under Markov models of evolution

In this talk, I will discuss the new research project that Leo van Iersel, Niels Holtgrefe and I are starting on (along with Steven Kelk and Martin Frohn at the university of Maastricht).

In phylogenetics, the primary goal is to infer the evolutionary history of a set of species, given access only to the DNA data of their present-day successors. Mathematically speaking, we wish to reconstruct an unknown directed acyclic graph (the phylogenetic network), given a sequence of vectors that map each leaf to one of 4 states {A,C,G,T} (the DNA data). Such data is generated under a certain probabilistic model, that assumes genetic data is inherited from one's parents with some (unknown) probability of mutation.

Using algebraic invariants, it is possible to show that, at least for some classes of network, it is possible to reconstruct the network topology with extremely high confidence (in the sense that almost every possible output from a given network is vanishingly improbably for any other network). Algebraic statistics thus presents a powerful tool for network reconstruction. However finding these invariants is very time-consuming, and only practical for very small networks.
On the other hand, graph theory techniques developed by Leo and others allow us to reconstruct the network from its smaller subnetworks, without saying anything about how to find those smaller networks. Our aim is to combine these algebraic and graph theoretical approaches, in order to prove reconstructibility results for much larger classes of phylogenetic networks.

I'll give an overview of the central problem, the algebraic and combinatorial techniques involved, the results we have so far and future goals.

27 juni 2023 11:00 t/m 12:00

[DMO] Anurag Bishnoi: Determining Ramsey numbers using finite geometry

We will look at the new breakthrough in Ramsey theory by Sam Mattheus and Jacques Verstraete that solves an 80-year-old open problem by using a random-algebraic approach. In particular, they start with a finite geometric graph and then take a random subgraph to obtain sharp lower bounds on the Ramsey number r(4, t). I will present their result, describe it's historical context and importance, and give a sketch of their argument.
Here is their preprint: https://arxiv.org/abs/2306.04007

23 juni 2023 14:00 t/m 15:00

[DMO] Bram Bekker: Semidefinite programming bounds for distance-avoiding set problems in quantum communication

Witsenhausen’s problem asks for the set with largest area on the n-dimensional unit sphere such that no two points in this set are orthogonal. A very simple argument shows that this area relates to a lower bound on the efficiency of quantum communication channels, as shown by A. Montina. By exposing Witsenhausen’s problem as a maximal independent set problem on an infinite graph, we can use semidefinite programming to obtain upper bounds to this maximal area. Using copositive cuts, we developed a hierarchy of strengthenings of the Lovász theta-number to obtain the best upper bounds known. A result of theoretical significance is the proof that this copositive hierarchy converges to exactly the independence number of the graph.

19 juni 2023 13:00 t/m 14:00

[DMO] Marijn Heule: Computer-aided Mathematics: Successes, Advances, and Trust

Progress in satisfiability (SAT) solving has made it possible to determine the correctness of complex systems and answer long-standing open questions in mathematics. The SAT-solving approach is completely automatic and can produce clever though potentially gigantic proofs. We can have confidence in the correctness of the answers because highly trustworthy systems can validate the underlying proofs regardless of their size.

We demonstrate the effectiveness of the SAT approach by presenting some successes, including the solution of the Boolean Pythagorean Triples problem, computing the fifth Schur number, and resolving the remaining case of Keller’s conjecture. Moreover, we constructed and validated proofs for each of these results. The second part of the talk focuses on notorious math challenges for which automated reasoning may well be suitable. In particular, we discuss advances in applying SAT-solving techniques to the Hadwiger-Nelson problem (chromatic number of the plane), optimal schemes for matrix multiplication, and the Collatz conjecture.

09 juni 2023 14:00 t/m 15:00

[DMO] Martijn van Ee: Exact and approximation algorithms for routing a convoy through a graph

In convoy routing problems, we assume that each edge in the graph has a length and a speed at which it can be traversed, and that our convoy has a given length. At any moment, due to safety requirements, the speed of the convoy is dictated by the slowest edge on which currently a part of the convoy is located. In this talk, I will discuss the complexity and approximability of some classical routing problems in the convoy setting. This is joint work with Tim Oosterwijk (VU), René Sitters (VU), and Andreas Wiese (TU Munich).

26 mei 2023 15:00 t/m 16:00

[DMO] David de Boer: Random colourings of trees with constant down degree

15 mei 2023 14:00 t/m 15:00

[DMO] John Bamberg: Foundations of hyperbolic geometry

Abstract: The independent discovery by Lobachevsky and Bolyai of hyperbolic geometry in the 1830's was followed by slow acceptance of the subject from the 1860's on, with the publications of relevant parts of the correspondence of Gauss. A new phase was entered from 1903, when David Hilbert, in his work introducing the "calculus of ends", introduced an axiomatisation for hyperbolic plane geometry by adding a hyperbolic parallel axiom to the axioms for plane absolute geometry. In 1938, Karl Menger (of the famous Vienna Circle) made the important discovery that in hyperbolic geometry the concepts of betweenness and equidistance can be defined in terms of point-line incidence. Since an axiom system obtained by replacing all occurrences of betweenness and equidistance with their definitions in terms of incidence would look highly unnatural, Menger and his students looked for a more natural axiom system. In particular, Helen Skala showed in 1992 that there is a set of axioms whose models are the classical hyperbolic planes over Euclidean fields, and her axioms were the first that contained only first order statements. This talk will be on joint work with Tim Penttila (Emeritus, University of Adelaide) where we endeavour to simplify Skala's axioms and retain a characterisation of the classical hyperbolic planes.

03 mei 2023 14:00 t/m 15:00

[DMO] Ferdinand Ihringer : Some methods for modifying strongly regular graphs

17 april 2023 14:30 t/m 15:30

[DMO] David Conlon: Sumset estimates in higher dimensions

We will describe recent progress, in joint work with Jeck Lim, on the study of sumset estimates in higher dimensions.

05 april 2023 14:00 t/m 15:00

[DMO] Siv Sørensen: Topology reconstruction using time series data in telecommunication networks

We consider Hybrid fiber-coaxial (HFC) networks in which data is transmitted from a root node to a set of customers using a series of splitters and coaxial cable lines that make up a general (non-binary) tree. The physical locations of the components in a HFC network are always known but frequently the cabling is not. This makes cable faults difficult to locate and resolve.

In this study we consider time series data received by customer modems, to reconstruct the topology of HFC networks. We assume that the data can be translated into a series of events, and that two customers sharing many connections in the network will observe many similar events. This approach allows us to use maximum parsimony to minimize the total number of character-state changes in a tree based on observations in the leaf nodes. Furthermore, we assume that nodes located physically close to each other have a larger probability of being connected. Hence, our objective is a weighted sum of data distance and physical distance.

A variable-neighborhood search heuristic is presented for minimizing the combined distance. Furthermore, three greedy heuristics are proposed for finding an initial solution. Computational results are reported for both real-life and synthetic customer data with various degrees of background noise, showing that we are able to reconstruct the topology with a very high precision.

22 maart 2023 14:00 t/m 15:00

[DMO] Barbara Terhal & Maarten Stroeks: Fermionic Optimization

A basic problem in physics is to determine the lowest eigenvalue, or `ground state energy', of a many-body Hamiltonian. For fermionic Hamiltonians, modeling electrons in solids or chemistry, this problem is the minimization of a low-degree polynomial in non-commutative Majorana variables (forming a Clifford algebra). Since determining the lowest eigenvalue is a (QMA)-hard problem, it has been of interest to upper and lower bound the eigenvalue by optimizing over simple classes of states resp. relaxing the problem to a SDP.

We prove that for sparse fermionic Hamiltonians the upperbound over so-called Gaussian fermionic states, a well-known efficiently described class of quantum states, achieves a constant approximation ratio, meaning that the scaling with the number of variables is the same as for the true lowest eigenvalue. This is in contrast to recent work showing that for a class of random dense fermionic Hamiltonians, with high probability, there is no constant approximation ratio. We discuss some further results and open questions in this area.

References: 1. Herasymenko, Stroeks, Helsen, Terhal, https://arxiv.org/abs/2211.16518 ; 2. Hastings, O'Donnell, https://dl.acm.org/doi/10.1145/3519935.3519960

15 maart 2023 14:00 t/m 15:00

[DMO] Christopher Hojny: A Unified Framework for Symmetry Handling

Handling symmetries in optimization problems is essential for devising efficient solution methods. In this presentation, I present a general framework that captures many of the already existing symmetry handling methods (SHMs). While these SHMs are mostly discussed independently from each other, our framework allows to apply different SHMs simultaneously and thus outperforming their individual effect. Moreover, most existing SHMs only apply to binary variables. Our framework allows to easily generalize these methods to general variable types. Numerical experiments confirm that our novel framework is superior to the state-of-the-art SHMs implemented in the solver SCIP. This is joint work with Jasper van Doornmalen.

08 maart 2023 14:00 t/m 15:00

[DMO] Nils Van de Berg: Using slice rank for lower bounds on fast matrix multiplication

The exponent of matrix multiplication is an open problem in theoretical computer science. Since the initial development by Strassen it has been known that the complexity of multiplying two n by n matrices is somewhere between O(n^2) and O(n^3). Advances on the upper bound have brought the exponent down to 2.372. It is widely conjectured that the complexity is O(n^2) and indeed no better lower bounds have been found. However development of upper bounds has focussed on certain methods and it is possible to find lower bounds on these methods. In 2019 Alman showed that a general type of method could not obtain a better bound than 2.168. For this he used the slice rank, a notion defined by Tao based on work by Ellenberg and Gijswijt. For my master thesis I have studied his paper and the slice rank. I wish to present the ideas in this paper and some of my small own advancements.

03 maart 2023 14:00 t/m 15:00

[DMO] Giulia Montagna: Equiangular lines with a fixed angle

A set of lines through the origin in R^d is called equiangular when any two lines from the set share the same angle. Let N_α(d) denote the maximum number of lines through the origin in R^d with pairwise common angle arccos α. A few years ago Jiang, Tidor, Yao, Zhang and Zhao solved the problem of determining N_α(d) in large enough dimensions. Their result is as follows. Let k denote the minimum number of vertices in a graph whose adjacency matrix has spectral radius exactly (1−α)/(2α). If k exists, then N_α(d) = ⌊k(d-1)/(k-1)⌋ for all sufficiently large d. Otherwise, N_α(d) = d + o(d). In this talk I will present the proof of this result.

17 februari 2023 14:00 t/m 15:00

[DMO] Davi Castro-Silva: Noisy decoding and equidistribution of polynomial maps

A problem from theoretical computer science posed by Buhrman asks to show that a certain class of circuits (NC0[+]) is bad at decoding error-correcting codes under random noise. (This would be in contrast with an analogous class of quantum circuits.) These circuits can be modeled by constant-degree polynomial maps, which turns out to make the problem amenable to a structure-versus-randomness analysis based on a new notion of rank for polynomial maps.

In this talk I will aim to discuss a solution to Buhrman's problem along these lines as well as connections with other notions of rank for polynomials and tensors.

Based on joint work with Jop Briët.

Deel deze pagina: