Welcome!
Group seminars occur regularly on Fridays. There is also a Google calendar with the schedule.
Seminars of 2022
Makespan Scheduling of Unit Jobs with Precedence Constraints in \(O(1.995^n)\) time
Speaker: Celine Swennenhuis (TU Eindhoven)
When and Where: Friday, 28/10/2022, at 16:00, Timmanzaal
Abstract:
In a classical scheduling problem, we are given a set of n jobs of unit length along with precedence constraints and the goal is to find a schedule of these jobs on m identical machines that minimizes the makespan. This problem is well-known to be NP-hard for an unbounded number of machines. Using standard 3-field notation, it is known as P|prec,pj=1|Cmax. We present an algorithm for this problem that runs in \(O(1.995^n)\) time. Before our work, even for m=3 machines the best known algorithms ran in \(O(2^n)\) time. In contrast, our algorithm works when the number of machines m is unbounded. A crucial ingredient of our approach is an algorithm with a runtime that is only single-exponential in the vertex cover of the comparability graph of the precedence constraint graph. This heavily relies on insights from a classical result by Dolev and Warmuth (Journal of Algorithms 1984) for precedence graphs without long chains. (Joint work with Jesper Nederlof and Karol Wegrzycki.)
I will be at the TU Delft somewhere after lunch probably.
Constrained error control codes for DNA-based data storage
Speaker: Jos Weber
When and Where: Friday, 17/6/2022, at 16:00, EWI Room J
Abstract:
In order to deal with the constantly growing amounts of digital data to be stored, there is a need for high-capacity durable storage media beyond the current magnetic and optical discs. DNA-based storage is considered to be a promising alternative option to accommodate huge amounts of archival data. However, errors may corrupt the data, particularly in the writing and reading processes of the DNA strings consisting of the nucleotides adenine (A), thymine (T), guanine (G), and cytosine (C). In order to reduce the error probability, the strings should satisfy constraints on the ratio of A's and T's versus the number of G's and C's, and on the maximum number of repeated identical nucleotides. Also, it is desirable that the set of DNA-strings in use possesses certain error correction or detection capabilities. This can be established by designing quaternary constrained codes with a specified minimum distance.
In this presentation, first a general introduction will be given on some basic coding aspects related to the DNA-based data storage problem: (i) determining the maximum size of a code with a specified length and minimum distance, (ii) runlength-limited codes, and (iii) balanced codes. Then, a result is discussed on determining the maximum size of a single-error-detecting quaternary code with certain runlength and balance constraints. It is the speaker’s intention to present the material in such a way that it can also be fully understood by people who have little or no background in coding theory.
How to use supervised machine learning in algorithm design
Speaker: Esther Julien
When and Where: Friday, 3/6/2022, at 16:00, EWI Room J
Abstract:
When you want to apply machine learning (ML) to enhance your algorithm, you have to decide on many factors: where to use ML, what to predict, and how to train your model. In this talk, I will show several methods for using supervised machine learning models in algorithm design. These methods are originated from recent work in phylogeny and robust optimization.
A recursive Lovász theta number for simplex-avoiding sets
Speaker: Fernando M. de Oliveira Filho
When and Where: Friday, 3/6/2022, at 14:00, EWI Room J
Abstract:
How much of the unit sphere can be covered by a set that does not contain the vertices of a spherical simplex? What fraction of Eculidean space can be covered by sets not containing the vertices of a unit simplex? In this talk, I will consider both these questions, and I will show how an extension of the Lovász theta number can be used to provide upper bounds for the maximum density of simplex-avoiding sets on the sphere and in Euclidean space. I will also show that these upper bounds decay exponentially fast with the dimension of the space.
(Joint work with D. Castro Silva, L. Slot, and F. Vallentin.)
Lattice reformulation cuts
Speaker: Karen Aardal
When and Where: Friday, 13/5/2022, at 16:00, EWI Room J
Abstract:
Download the abstract.
Excluding affine configurations over a finite field
Speaker: Dion Gijswijt
When and Where: Friday, 13/5/2022, at 14:00, EWI Room J
Abstract:
This is a more technical exposition of the topic from the previous seminar (i.e. proofs on the blackboard).
It was shown in 2016 that the maximum size of a cap set in \(F_3^n\) is \(O(2.756^n)\). The solution uses a new branch of the polynomial method that is now commonly referred to as the "slice rank method".
A cap set is a set without solutions to the equation \(x_1-2x_2+x_3=0\). More generally, one may ask when the density of a subset of \(F_q^n\) without non-trivial solutions to a given (homogeneous, balanced) system of linear equations must have exponentially small density. Moreover, one may ask for solutions that are not just non-trivial, but "all-different" of even "generic".
We will prove that under natural condition on the system, sets without generic solutions indeed have exponentially small density.
A random Hall-Paige conjecture
Speaker: Alp Muyesser
When and Where: Monday, 2/5/2022, at 15:00, room HB 01.230 Elektron
Abstract:
A complete mapping of a group \(G\) is a bijection \(\phi\colon G\to G\) such that \(x\mapsto x\phi(x)\) is also bijective. The Hall-Paige conjecture from 1955 states that \(G\) has a complete mapping whenever the product of all elements of \(G\) is contained in the commutator subgroup of \(G\). The conjecture is a theorem since 2009 thanks to breakthrough work of Wilcox, Evans, and Bray. In this talk, we discuss a "random" variant of Hall-Paige theorem. The proof avoids the usage of classification of finite simple groups, and result allows us to settle several longstanding conjectures in combinatorial group theory (though only for large groups). A sample application is a characterisation of groups whose elements can be ordered so that the product of each consecutive pair of elements is distinct, which settles a problem of Evans.
This is joint work with Alexey Pokrovskiy.
Excluding affine configurations using the slice rank method
Speaker: Dion Gijswijt (TU Delft)
When and Where: Friday, 22/4/2022, at 16:00, EWI Room J
Abstract:
A cap set is a subset of \(F_3^n\) that contains no three points on a line. How large can such a set be as a function of the dimension \(n\)?
The cap set problem asks whether the maximum size of a cap set is exponentially small compared to the whole space and has several connections to problems in number theory, extremal combinatorics and arithmetic complexity.
The cap set problem was solved in 2016 using a new method, now commonly referred to as the slice-rank method.
In this talk, we will review the slice-rank method and touch upon recent results for excluding more complicated affine structures than three points on a line.
The list-packing number
Speaker: Wouter Cames van Batenburg (TU Delft)
When and Where: Friday, 1/4/2022, at 16:00, EWI Room J
Abstract:
List-colouring is an influential and classic topic in graph theory. We initiate the study of a natural strengthening of this problem, where instead of one list-colouring, we seek many in parallel. Given the assignment of a list \(L(v)\) of \(k\) colours to each vertex \(v\) of a graph \(G\), we study the existence of \(k\) pairwise-disjoint proper colourings of \(G\) using colours from these lists. We refer to this as a list-packing and we define the list-packing number \(\chi_\ell^{\star}(G)\) as the smallest \(k\) for which every list-assignment of \(G\) admits a list-packing. We prove several results that (asymptotically) match the best-known bounds for the usual list chromatic number. Our main open question is whether in general \(\chi_\ell^\star(G)\) can be bounded by a constant times the list chromatic number.
(Based on joint work with Stijn Cambie, Ewan Davies and Ross Kang)
A new road to polynomial-time methods for Linear Optimization
Speaker: Kees Roos (TU Delft)
When and Where: Friday, 25/3/2022, at 16:00, EWI Room J
Abstract:
Recently, a Von Neumann type method for solving homogeneous linear systems with positive variables was changed into a polynomial-time method, by Sergei Chubanov. We introduce a new variant of Chubanov's method. In the Basic Procedure we use a recently introduced cut in combination with Nemirovski's Mirror-Prox method. We show that generating a new cut requires at most \(n^3\) iterations of \(O(n)\) time. The new cut is at least as sharp as Chubanov's cut, which requires \(4n^3\) iterations of \(O(n)\) time. Our Modified Main Algorithm is in essence the same as Chubanov's Main Algorithm, except that it uses the new Basic Procedure as a subroutine. The new method has \(O(n^{3.5} log(1/\delta_A)\) time complexity, where \(\delta_A\) denotes a suitably defined condition number of the constraint matrix of the matrix \(A\). As we show, a simplified version of the new Basic Procedure competes well with the Smooth Perceptron Scheme of Peña and Soheili and, when combined with Rescaling, also with Gurobi and Mosek, two commercial codes for linear optimization.