In 1963 Andrey Kolmogorov came up with the definition of Kolmogorov complexity : the kolmogorov complexity of a string $w\in {0;1}^*$ noted $K(w)$ is the size of the smallest program $p$ which stops after printing $w$. In this sense it can for instance be made formal to say that 0101010101010101 is a less random/complex string than 56748195473159418. This notion of complexity is universal and robust (for instance it doesn't matter in which language the program $p$ is written), it has been studied for its own sake and is also used in number theory, combinatorics, probabilisic theory, computability theory, complexity theory (P=NP) etc… where it has led to new or simplified proofs.

We will present an introduction to Kolmogorov theory and some beautiful applications. We will also talk about a new recent result of Léchine and Seiller ( https://hal.science/hal-04539439 ) which features a very neat open combinatorics problem which you may help solve. No background is needed.

Given a matrix $A$ with $m$ rows and $n$ columns, we want to approximate the maximum value of $||A x||_p$ when $||x||_q <= 1$. For general matrices, a $(1-\epsilon)$ approximation of the problem is hard, but for nonnegative matrices, when $q >= p >= 1$, the problem can be transformed into a concave maximization problem. In this talk, we will present a width-independent (i.e., the running time dependence on $n m$ is at most poly-logarithmic) algorithm to find $(1-\epsilon$) approximations in time nearly $O(nnz/\epsilon)$.

In the second part of the talk, we will see how such an algorithm can be used to compute competitive oblivious linear routings.

Universal algebra concerns the study of those mathematical objects that behave like 'algebraic structures' (i.e. groups, rings, vector spaces…). This talk is divided into two parts. In the first we try to understand what 'algebraic structures' have in common, offering an overview of the basic concepts of universal algebra. In the second we survey some selected topics that link universal algebra with logic and computer science.

Explorable automata lie on the border between deterministic and non-deterministic automata: they are non-deterministic automata where it is possible to solve the non-determinism. When given a word spelled one letter at a time, an automaton is said explorable if there exists a way to produce an accepting run by moving forward tokens in a given number of copies of the automata. (the case with exactly one copy corresponds to the history-deterministic case). In this joint work with Denis Kuperberg, I studied explorable automata on infinite words. More specifically, I studied, for different accepting conditions, their expressiveness and the decidability of the explorability property.

We all learned the formula for solving quadratic equations in school, but how would you go about finding the roots if you are given a polynomial of, say, degree 10? How about if someone asked you to give an algorithm to do that? The latter is an example of the type of problems considered in algorithmic algebra. In this talk, I will try to give a high level overview of computational problems concerning polynomials and systems of polynomials. We will look at different representations of polynomials and talk about problems such as polynomial identity testing or determining whether a system of equations admits a common solution. No (algebraic or other) preliminaries required — I will even remind you of the quadratic formula in case you forgot it.

We're all used to and familiar with proving interesting results and of course sometimes we can also prove that theorems are wrong. But is there something substantial one can say about the absence of proofs? The more philosophically inclined can go back to Gödel's famous work and convince themselves that there will always be true statements that are not provable in any particular system.

As such a statement will necessarily depend on a concrete theory of proof we are going to look into a specific technique commonly used in complexity theory called oracle separations (Impagliazzo, Rudich, STOC 1989) and how we can use an elementary counting argument to create a contradiction to proofs (Gennaro, Trevisan, FOCS 2000).

Given the topic at hand we are going to struggle with too many negations. Also it comes natural to re-introduce reduction proofs but it clearly helps to have seen those already (say in undergrad np completeness). There's virtually no cryptography in it and I assume we can keep it broadly accessible to all lab members even though it is a somewhat technical topic!

In graph theory, graph colouring is a special case of graph labelling; it is an assignment of labels traditionally called ‘’colours’’ to elements of a graph subject to certain constraints. In its simplest form, it is a way of colouring the vertices of a graph such that no two adjacent vertices are of the same colour, which is called vertex colouring. The problem of colouring a graph arises in many practical areas such as sports scheduling, designing seating plans, exam timetabling, the scheduling of taxis and so on.

In this talk, I will introduce some basic conceptions and theorems of graph colouring, such as brooks’ Theorem. Moreover, I will introduce a new conception called k-truncated-degree choosability and some open problems.

Random programs are very useful. In particular, they allow to write programs that are very efficient on average (such as randomized quick sort). It is however a bit hard to define what these programs compute without some form of hand waving. The goal of semantics is to define the probability distributions associated to a random program in a systemic and a modular way.

This approach has received an increase in interest following the rise of probabilistic programming. The goal of probabilistic programming is to write a random program, called a model, and to provide generic inference tools to condition this program with regard to some observations. It is then very important to assign a precise meaning to the distribution computed by the model, and to the inferred distribution. This is where semantics shines.

The goal of this talk is to provide an intuition of what the semantics of a functional programming language with higher order should look like. Surprisingly, this is deeply tied to linear logic and differential linear logic. In particular, a probabilistic program should be interpreted as an “analytic maps” in some sense.

Please be reassured. We will not talk about categorical abstract nonsense. The goal of the talk is to stay as grounded as possible and to provide intuitions, not to explain why the Kleisli category of the exponential comonad of probabilistic coherence spaces is a cartesian closed category (it is, though).

This will be a whiteboard talk.

An argument in favour of dynamically-typed programming languages is their flexibility, enabling quick code writing and prototyping. But this is also a weakness, as many bugs are only detected when executing the program. Hence, statically-typed versions of well-known languages are in rapid expansion, such as Typescript or Luau. To guarantee the safety of a program without sacrifing expressivity, augmenting types with set operations, such as union and intersection, has proven very useful. Considering those set-theoretic operators naturally leads to so-called semantic subtyping: types are interpreted as sets, union and intersection types with the corresponding set operators, and subtyping is derived from set inclusion in the interpretation. Systems with semantic subtyping and set-theoretic types now support first-order polymorphism à la ML, a powerful programming abstraction. This kind of polymorphism however, is not sufficient when considering a language with extensible records (or structs), as it does not capture precise enough typings. In this talk, I will give an introduction to type systems with set-theoretic types and semantic subtyping. I will showcase some programs with typing failures, and show how the addition of row polymorphism for records solves the problem. I will then describe how we integrated row polymorphism to a type system with set-theoretic types, semantic subtyping and first-order polymorphism.

Recent advances on linear algebraic problems such as matrix inversion suggest that quantum computers are strictly more powerful with limited space than classical computers. Building on these results we discuss a possible quantum advantage for graph connectivity. That is the problem of deciding whether two nodes in a graph are connected and is of fundamental importance to space-bounded complexity theory. The talk will cover some aspects of spectral graph theory and unambiguous computation. No quantum background is required to follow it.

Automatic generation of loop invariants is a fundamental challenge in software verification. A simpler version of this challenging task is the polynomial invariants generation for loops with linear updates. In the first part of the talk, I will explain for a given loop how to construct all its polynomial invariants and the relationship to Toric ideals. In the second part, I will reverse the problem from invariant synthesis to loop synthesis. That is, given an algebraic property we ask to construct a loop with an infinite set of reachable states that has the given property as an invariant. This is based on ongoing project with George Kenison, Mahsa Shirmohammadi, and Anton Varonka.

In the problem of airports and railways (AR), the goal is to establish an efficient transportation network for a given set of cities with minimum cost. This involves the strategic placement of airports in select cities and the establishment of railway connections between each city without airport to an airport. Once implemented, this network will enable passengers to travel from their hometowns to any desired destination by utilizing a combination of flights and trains. As a formal definition, we are given a complete graph G = (V,E) with weightsontheverticesa:V →R+,lengthoftheedgesl:V ×V →R+,anda positive integer k as the capacity parameter. The goal is to compute a spanning forest R of G and a subset A ⊆ V of minimum cost such that each component in R has one open facility and the number of cities in each component is at most k (the capacity constraint). The cost of the solution (A, R) is measured as \sum_{v∈A} a(v) + \sum_{e∈E(R)} l(e). In the unsplittable demand version of the problem (ARUD), additionally, we are given a function b : V → R+ that defines a non-zero demand for each city and the goal is to find a network of trees with minimum cost such that the total demand in each component is at most k. In this talk, we’ll discuss different versions of the problem (when the problem defined on different networks), bi-factor approximation algorithms for the metric AR and ARUD problems which violates the capacity constraints by O(k), and some complexity results of the problem.

Distributed systems have been a crucial component in the growth of large scale databases that power most of modern internet. While the algorithms used to run these systems are proven to be sound, the gap between implementations and on-paper algorithms leaves room for errors. Recurring downtimes in popular services such as Facebook and Cloudflare are mainly due to bugs in these implementations. In this talk, I will present two new approaches to test these implementations to guarantee correctness. One, improves on well known techniques for fuzzing using a TLA specification. Two, uses intelligent Reinforcement learning techniques to cover edge cases more efficiently and find new bugs. This is on going work with researchers from MPI and TU Delft.