DIAMANT Symposium Autumn 2022

The multi-arm bandit problem

Consider a machine with K arms, where each arm provides a random reward from an unknown probability distribution that potentially can change over time. The objective of the player is to maximize the sum of rewards by using an appropriate strategy. The crucial tradeoff that the player faces at each step is the tradeoff between „exploitation” of the arm that she believes has the highest expected payoff and “exploration” to get more information on the underlying probability distributions. In this talk we provide new optimal algorithms for some versions of the problem.

Many-Visits Traveling Salesman Problems

The traveling salesman problem (TSP) is arguably one of the most important problems in combinatorial optimization. It requires a salesman to visit each city from a list of n cities exactly once, and return to the origin, such that the overall length of their tour is minimized. Recently, there is a growing interest in powerful extensions of TSP to allow for many visits, where each city c comes with a request r_c of how many times it should be visited. Such variants opens up new real-life applications such as aircraft sequencing, vehicle routing, and scheduling. The challenge is to design efficient algorithms for such problems despite the fact that the requests r_c can be exponentially large in the total number n of cities.

We propose several new algorithms for many-visit TSP variants, which efficiently compute optimal or near-optimal solutions, for variants with single salesman and multiple salesmen. The algorithms are guaranteed to quickly compute high-quality solutions for all problem instances, and thus complement the extensive literature on heuristics for such problems.

Convex characters, algorithms and matchings

A phylogenetic (i.e. evolutionary) tree is an unrooted binary tree T in which the leaves are in bijection with a set of labels X, where X represents a set of contemporary species. Here we present a number of enumeration results pertaining to convex characters: partitions of X in which the spanning trees induced by the blocks of the partition, are vertex disjoint in T. Via a number of transformations we show that enumerating specially chosen subfamilies of convex characters is sufficient to give an algorithm with running time O*(1.6181^n) for computing the “2-state maximum parsimony distance” between two phylogenetic trees, where n=|X| and O*(.) suppresses polynomial factors – this distance, which is NP-hard to compute, is used to quantify how different two evolutionary histories are. Next, we show that one of these subfamilies of convex characters is actually in bijection with a constrained subfamily of matchings (i.e. disjoint sets of edges) defined over a secondary, auxiliary tree structure. By proving that there are at most O(1.5895^n) such constrained matchings, we obtain a faster algorithm for the aforementioned distance problem, and as a corollary obtain a tight upper bound on the number of matchings in general trees with certain degree restrictions, extending results from the matchings literature. For the O(1.5895^n) result we leverage recent techniques that have been developed for bounding the rate of growth of certain structured families of recurrences.

This is joint work with Ruben Meuwese (Maastricht) and Stephan Wagner (Uppsala).

Twists of elliptic curves with CM

We consider certain families of sextic twists of the elliptic curve y^2=x^3+1 and compute formulas that relate the central values of their L-functions L(E, 1) to the square of a trace of a modular function evaluated at a CM point. When the value above is non-zero, we recover the order of the Tate-Shafarevich group, and we show that the value is indeed an integer square. 

Genus Distribution of Random q-ary Lattices

The genus is an efficiently computable arithmetic invariant for lattices up to isomorphism. Given the recent proposals of basing cryptography on the lattice isomorphism problem, it is of cryptographic interest to classify relevant families of lattices according to their genus.
We propose such a classification for q-ary lattices, and also study their distribution. In particular, for an odd prime q, we show that random q-ary lattices are mostly concentrated on two genera.

Weil polynomials of abelian varieties over finite fields with many rational points

In this work, we establish a relation between totally positive algebraic integers with minimal trace, and maximal isogeny classes of simple abelian varieties defined over finite fields with cardinality an even power of a prime, and which have a field as endomorphism algebra. As a consequence, we obtain results about the cyclicity of the group of rational points of such abelian varieties.
This is joint work with A. J. Giangreco-Maidana published this year in the International Journal of Number Theory.

Code-Based Cryptography and AG Codes

In this talk, I will provide an introduction to code-based cryptography and algebraic geometry (AG) codes and discuss the effects when the latter are applied to code-based cryptography, specifically to the McEliece cryptosystem. I will also give an overview of some work in progress which generalizes the structure of the McEliece cryptosystem while retaining the benefits derived from AG codes.

Orientations and Cycles in Supersingular Elliptic Curve Isogeny Graphs

In joint work with M. Chen, K. Lauter, R. Scheidler, K. Stange, and H. Tran, we provide a bijection between the rims of the union of all oriented supersingular ell-isogeny volcanoes and isogeny cycles (certain closed walks) in the supersingular l-isogeny graph. Compositions of isogeny cycles are nontrivial endomorphisms of supersingular elliptic curves. We use our bijection to count isogeny cycles of given length in the supersingular ell-isogeny graph exactly as a sum of class numbers of certain imaginary quadratic orders, and we also give an explicit upper bound by estimating the class numbers.

Makespan Scheduling of Unit Jobs with Precedence Constraints in O(1.995^n) time

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|C_{max}. 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.

Algorithmic Solutions for Maximizing Shareable Costs

We address the optimization problem to maximize the total costs that can be shared among a group of agents, while maintaining stability in the sense of the core constraints of a cooperative transferable utility game, or TU game. This means that all subsets of agents have an outside option at a certain cost, and stability requires that the cost shares are defined so that none of the outside options is preferable. When maximizing total shareable costs, the cost shares must satisfy all constraints that define the core of a TU game, except for being budget balanced. We give a fairly complete picture of the computational complexity of this optimization problem, in relation to classical computational problems on the core. We also show that, for games with an empty core, the problem is equivalent to computing minimal core relaxations for several relaxations that have been proposed earlier. As an example for a class of cost sharing games with non-empty core, we address minimum cost spanning tree games. While it is known that cost shares in the core can be found efficiently, we show that the computation of maximal cost shares is NP-hard for minimum cost spanning tree games. We also derive a tight 2-approximation algorithm. (Joint work with B. Lin, M. Walter, M. Uetz)

A Universal Error Measure for Input Predictions Applied to Online Graph Problems

We introduce a novel measure for quantifying the error in input predictions. The error is based on a minimum-cost hyperedge cover in a suitably defined hypergraph and provides a general template which we apply to online graph problems. The measure captures errors due to absent predicted requests as well as unpredicted actual requests; hence, predicted and actual inputs can be of arbitrary size. We achieve refined performance guarantees for previously studied network design problems in the online-list model, such as Steiner tree and facility location. Further, we initiate the study of learning-augmented algorithms for online routing problems, such as the online traveling salesperson problem and the online dial-a-ride problem, where (transportation) requests arrive over time (online-time model). We provide a general algorithmic framework and we give error-dependent performance bounds that improve upon known worst-case barriers, when given accurate predictions, at the cost of slightly increased worst-case bounds when given predictions of arbitrary quality.

About maximal distance minimizers

A maximal distance minimizer for a given compact set M in R^n and a given positive real r is a connected set Σ of minimal length (one-dimensional Hausdorff measure) such that M in B_r(Σ) (i.e. every point from M has a point from Σ in its closed r-neighbourhood). There are a lot of meaningful open questions concerning regularity of maximal distance minimizers and also about the explicit examples of the minimizers. It appears that for every compact set M a maximal distance minimizer Σ should be ’good’: for every point x ∈ Σ there exists one, two or three tangent rays and the pairwise angles between these rays are at least 2π/3. Moreover for a planar set M a maximal distance minimizer Σ has a finite number of points with three tangent rays (a non-planar case remains open problem). We know maximal distance minimizers for a “big” circle (or other sets with “‘big” radius of curvature) and we know the topology of maximal distance minimizers for a “big” rectangle. I will talk both about open questions and the known results. Everybody is welcome, no prior knowledge needed.

Numerical nonlinear algebra in particle physics

We show how numerical methods from nonlinear algebra can be used to study scattering amplitudes in particle physics. The story involves solving systems of polynomial equations, computing Euler characteristics of point configuration spaces, and numerical elimination. We discuss problems that were solved using these techniques and were previously out of reach.

Classification of 2-term L∞-algebras

L∞-algebras are generalizations of Lie algebras. They are chain complexes of vector spaces on which there is a graded anti-symmetric bracket which satisfies Jacobi-like identities. We show that 2-term L∞-algebras are classified by a Lie algebra, a vector space, a representation (all up to isomorphism) and a cohomology class of the corresponding Lie algebra cohomology.

Generalized class polynomials

The Hilbert class polynomial is a polynomial whose roots are the j-invariants of elliptic curves that have a given endomorphism ring. It can be used to construct elliptic curves over finite fields with a prescribed number of points. Since its coefficients are typically rather large, there has been continued interest in finding alternative class polynomials that are smaller. We generalize class polynomials to a multivariate setting, where in special cases we obtain size reductions better than those previously known. This is joint work with Marco Streng.

The first negative Fourier coefficient of an Eisenstein series newform

There have been a number of papers on statistical questions concerning the sign changes of Fourier coefficients of newforms. In one such paper, Linowitz and Thompson gave a conjecture describing when, on average, the first negative sign of the Fourier coefficients of an Eisenstein series newform occurs. In this talk, we correct their conjecture and prove the corrected version.