The calendar of events (iCal format).
In order to add the event calendar to your favorite agenda, subscribe to the calendar by using this link.


Contact(s)



Year 2024

Algorithms and discrete structures
Friday September 13, 2024, 2PM, Salle 3052
Shuichi Hirahara (National Institute of Informatics, Japan) Planted Clique Conjectures Are Equivalent

Planted Clique Conjecture states that no polynomial-time algorithm can find a k-clique in an n-vertex Erdős-Rényi random graph with a k-clique planted for $k << n^{1/2}$. We present the equivalence among many variants of planted clique conjectures, including search versions of a success probability exponentially close to 1 and with a non-negligible success probability, a worst-case version (the k-clique problem on incompressible graphs), and decision versions with small and large probabilities. In particular, this equivalence identifies the optimality of a simple edge counting algorithm: By counting the number of edges, one can efficiently distinguish an n-vertex random graph from a random graph with a k-clique planted with probability $k^2/n$ for any $k \le n^{1/2}$. We show that for *any* k, no polynomial-time algorithm can distinguish these two random graphs with probability significantly larger than $k^2/n$ *if and only if* the planted clique conjecture holds.

Joint work with Nobutaka Shimizu. Paper: https://eccc.weizmann.ac.il/report/2024/058/

Algorithms and discrete structures
Friday June 14, 2024, 3:30PM, Salle 3052
Venkatesan Guruswami (Simons Institute) When and why do efficient algorithms exist (for constraint satisfaction and beyond)?

Computational problems exhibit a diverse range of behaviors in terms of how quickly and effectively they can be solved. What underlying mathematical structure (or lack thereof) in a computational problem leads to an efficient algorithm for solving it (or dictates its intractability)? Given the vast landscape of problems and algorithmic approaches, it would be simplistic to hope for a universal theory explaining the underpinnings of easiness/hardness. Yet, in the realm of constraint satisfaction problems (CSP), the algebraic dichotomy theorem gives a definitive answer: a polynomial time algorithm exists when there are non-trivial local operations called polymorphisms under which the solution space is closed; otherwise the problem is NP-complete.

Inspired and emboldened by this, one might speculate a polymorphic principle in more general contexts, with symmetries in the solution space governing efficient algorithms. Beginning with some background on CSP and the polymorphic approach to understanding their complexity, the talk will discuss some extensions beyond CSP where the polymorphic principle seems promising (yet far from understood). In particular, we will discuss “promise CSP” (PCSP) where one is allowed to satisfy a relaxed version of the constraints (a framework that includes important problems like approximate graph coloring). We will provide glimpses of the emerging polymorphic theory characterizing the (in)tractability of interesting classes of PCSP as well as the ability of natural classes of algorithms to solve them.


Year 2023

Algorithms and discrete structures
Tuesday April 18, 2023, 3:30PM, 3052, Sophie Germain
Mamadou Kanté (LIMOS, Clermond-Ferrand) Lettericity of graphs and griddability of permutations

Lettericity is a graph parameter measuring how close a graph is to a word and geometric griddability measures how close a permutation is to a monotone permutation. Both of these parameters enjoy nice properties, in particular graphs of lettericity k are definable in Monadic second-order logic and permutations that are geometric M-griddability are in bijection with a regular language. I will first present both and some properties, and show that these seemingly unrelated parameters are in fact equivalent in permutation graphs, i.e., a permutation class has small geometric griddability iff the associated permutation graph class has small lettericity.

Algorithms and discrete structures
Wednesday April 5, 2023, 3PM, 3052
Lélia Blin (LIP6) Self-Stabilizing Distributed Algorithms

In the context of large-scale networks, fault tolerance is a necessity. Self-stabilization is an algorithmic approach to fault tolerance in distributed systems. Its aim is to manage processors' memory corruption due to transient failures. The efficiency of a self-stabilizing algorithm is characterized by several parameters, including (1) the time taken by the system to return to a legal configuration after an arbitrary corruption of its processors' memory, and (2) the memory space used by the processors to execute the algorithm. Minimizing memory space is motivated by many aspects, such as networks (e.g. sensor networks) with limited memory space, minimizing data exchanges between processors, and limiting information storage to use redundancy techniques. This seminar will present self-stabilization through two main classical problems: constructing spanning trees, especially those of minimum weight, and electing a leader. It will cover the links between self-stabilization and distributed decision techniques, including computing lower bounds on memory space needed to solve the aforementioned problems using self-stabilizing algorithms.

Algorithms and discrete structures
Wednesday March 22, 2023, 3PM, 3052
Michail Lampis (LAMSADE) First Order Logic on Pathwidth Revisited Again

Courcelle's theorem, which states that all MSO-expressible properties can be decided in linear time on graphs of bounded treewidth, is one of the most celebrated results in parameterized complexity, because it implies the existence of linear-time FPT algorithms for a host of NP- hard problems. Unfortunately, the hidden constant implied by this theorem is a tower of exponentials whose height increases with each quantifier alternation in the formula.

In this talk we take a high-level view of this area of research and survey results that attempt to improve upon this performance by considering more restricted classes of inputs. This is known to be impossible, even if we restrict the input to graphs of treewidth 1 (trees) and only consider FO logic; or if we consider graphs of pathwidth 1 (caterpillars) and consider MSO logic. This would seem to indicate that Courcelle's theorem is “best possible”. Surprisingly, we discover that in the only remaining case which has so far been overlooked, namely FO logic on graphs of constant pathwidth, all known hardness results fail, because the problem becomes tractable with an elementary parameter dependence on the input formula. Our result generalizes previously known meta-theorems for the much more restricted parameter tree-depth.

Results based on a preprint available here: https://arxiv.org/abs/2210.09899


Year 2022

Algorithms and discrete structures
Tuesday October 11, 2022, 9:30AM, Amphi Turing
Anual Meeting Of Pole Asd, Presentation From New Members (IRIF)

09:30-10:00 - Marie Albenque

10:00-10:30 - Sergio Rajsbaum

10:30-11:15 Short introduction of new postdocs and Ph.D. students followed by General discussion and then coffee break

11:15-11:45 - Monika Csikos

11:45-12:15 - Sophie Laplante


Year 2021

Algorithms and discrete structures
Tuesday November 16, 2021, 1:30PM, Room 234C, Halle aux farines
Pole Day (ASD) Journée du pôle Algorithmes et structures discrètes 2021

Journée du pôle Algorithmes et structures discrètes 2021

Tuesday November 16, 2021 · Room 234C, Halle aux farines

13:30-14:00 - Mikael Rabie
14:00-14:30 - Matej Stehlik
14:40 – 15:10 Informal introduction of new postdocs and docs
15:15-15:45 - Adrian Vladu
15:45-16:15 - Simon Apers

16:15 Goûter (à l'IRIF)

Algorithms and discrete structures
Tuesday June 15, 2021, 2PM, Salle 3052
Magnús Halldórsson (Reykjavik University) New Vistas in Distributed Graph Coloring

The first and possibly the most fundamental problem in distributed graph algorithmics is the vertex coloring problem. The nodes of a network are processes that communicate via the edges in synchronous rounds. The most basic problem is to color the network using Delta+1 colors in as few rounds a possible, where Delta is the maximum degree of the graph.

We present a new approach for randomized distributed Delta+1-coloring that is dramatically simpler than the previous best: the seminal work of Chang, Li, and Pettie (CLP) in SICOMP 2020. This approach offers numerous refinements: It matches the O(log^3 log n) round complexity in general, while on high-degree graphs (Delta » log^2 n), it uses only O(log* n) rounds. It uses small messages, i.e., works also in the CONGEST model. It also offers tradeoffs between the number of colors used, the round complexity, and the clique number of the graph.

We expect that the approach presented will lead the way towards improved results for various coloring problems in the near future.

This is based on a paper at STOC'21, joint work with Fabian Kuhn, Yannic Maus, and Tigran Tonoyan; and a more recent one on arXiv, joint with Alexandre Nolin, and Tigran Tonoyan.

The seminar will be available online by the following ZOOM-link:

https://u-paris.zoom.us/j/84049775680?pwd=Yk5lMDhlZUNQRGMyelExMVdoM2poQT09


Year 2020

Algorithms and discrete structures
Tuesday May 26, 2020, 11AM, Online
Édouard Bonnet (ENS Lyon) Twin-width

Inspired by an invariant defined on permutations by Guillemot and Marx [SODA '14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, $K_t$-free unit ball graphs, posets with antichains of bounded size, and proper subclasses of permutation graphs all have bounded twin-width. On all these classes we will see how to compute in polynomial time a sequence of d-contractions, witness that the twin-width is at most d. FO model checking, that is deciding if a given first-order formula $\phi$ evaluates to true on a given binary structure G on a domain D, happens to be FPT in $|\phi|$ on classes of bounded twin-width, provided the witness is given. More precisely, being given a d-contraction sequence for G, our algorithm runs in time $f(d,|\phi|) |D|$ where f is a computable but non-elementary function. We will also see that bounded twin-width is preserved by FO interpretations and transductions. This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarsky et al. [FOCS '15]. Finally we mention a curious connection between bounded twin-width and small classes.

Joint work with Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant

Algorithms and discrete structures
Monday January 27, 2020, 9:30AM, 3052
Amaury Pouly (IRIF) Continuous models of computation: computability, complexity, universality

In 1941, Claude Shannon introduced a continuous-time analog model of computation, namely the General Purpose Analog Computer (GPAC). The GPAC is a physically feasible model in the sense that it can be implemented in practice through the use of analog electronics or mechanical devices. It can be proved that the functions computed by a GPAC are precisely the solutions of a special class of differential equations where the right-hand side is a polynomial. Analog computers have since been replaced by digital counterpart. Nevertheless, one can wonder how the GPAC could be compared to Turing machines.

A few years ago, it was shown that Turing-based paradigms and the GPAC have the same computational power. However, this result did not shed any light on what happens at a computational complexity level. In other words, analog computers do not make a difference about what can be computed; but maybe they could compute faster than a digital computer. A fundamental difficulty of continuous-time model is to define a proper notion of complexity. Indeed, a troubling problem is that many models exhibit the so-called Zeno's phenomenon, also known as space-time contraction.

In this talk, I will present results from my thesis that give several fundamental contributions to these questions. We show that the GPAC has the same computational power as the Turing machine, at the complexity level. We also provide as a side effect a purely analog, machine- independent characterization of P and Computable Analysis.

I will present some recent work on the universality of polynomial differential equations. We show that when we impose no restrictions at all on the system, it is possible to build a fixed equation that is universal in the sense it can approximate arbitrarily well any continuous curve over R, simply by changing the initial condition of the system.

If time allows, I will also mention some recent application of this work to show that chemical reaction networks are strongly Turing complete with the differential semantics.

Algorithms and discrete structures
Thursday January 23, 2020, 11AM, Salle 1007
Moni Naor (Weizmann Institute) Instance Complexity and Unlabeled Certificates in the Decision Tree Model

Suppose that you want to check whether a graph satisfies some (graph) property. The goal is to minimize the number of queries to the adjacency matrix. You are given as an “untrusted hint” an isomorphic copy of the graph. You must always be correct, but the number of queries made is only measured when the hint is correct. Do such unlabeled certificates help? In the worst case? Per instance?

In this talk I will discuss labeled and unlabeled certificates, in particular in the context of ``instance optimality“. This is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, respectively.

Joint work with Tomer Grossman and Ilan Komargodski


Year 2019

Algorithms and discrete structures
Wednesday October 2, 2019, 11AM, Salle 3052
Sophie Laplante (IRIF) The sensitivity conjecture and a recent proof of it (part II)

Informal presentation.

Algorithms and discrete structures
Thursday September 26, 2019, 2PM, Salle 3052
Sophie Laplante (IRIF) The sensitivity conjecture and a recent proof of it (part I)

Informal presentation.

Algorithms and discrete structures
Monday June 24, 2019, 11AM, Salle 3052
Carola Doerr (CNRS, LIP6) Evolutionary Algorithms – From Theory to Practice and Back

Most real-world optimization problems do not have an explicit problem formulation, but only allow to compute the quality of selected solution candidates. Solving such black-box optimization problems requires iterative procedures which use the feedback gained from previous evaluations to determine the strategy by which the next solution candidates are generated. Many black-box optimization algorithms, such as Simulated Annealing, Evolutionary Algorithms, Swarm Intelligence Algorithms, are randomized – making it very difficult to analyze their performances mathematically. In the last 15 years, the theory of randomized black-box optimization has advanced considerably, and has contributed to efficient optimization by providing insights into the working principles of black-box optimization which are hard or impossible to obtain by empirical means. On the other hand, empirically-guided benchmarking has opened up new research directions for theoretical investigations. In this presentation we will discuss the state of the art in the theory of randomized black-box optimization algorithms. As part of this critical survey we will also mention a number of open questions and connections to other fields of Computer Science.

Algorithms and discrete structures
Thursday May 9, 2019, 3PM, Salle 1007
Amélie Gheerbrant (IRIF) Graph query languages

Graph databases use graph structure to represent and query data. The talk will survey some graph query languages used in this context, with a focus on regular path queries (RPQs) and conjunctive regular path queries (CRPQs). We will present the different semantics that graph database systems use for them (every path, simple path, trail), and recall computational complexities of query evaluation and query containment. We will finally discuss some issues related to querying not only the topology but also the data of the graph and present a few open problems that could be of interest both to the graph and algorithms group and to the automata group.

Algorithms and discrete structures
Tuesday February 19, 2019, 11AM, Salle 3052
Danupon Nanongkai (KTH) Distributed Shortest Paths, Exactly

This talk concerns the problem of quickly computing distances and shortest paths on distributed networks (the CONGEST model). There have been many developments for this problem in the last few year, resulting in tight approximation schemes. This left open whether exact algorithms can perform equally well. In this talk, we will discuss some recent progress in answering this question. Most recent works that this talk is based on are with Sebastian Krinninger (FOCS 2018) and Aaron Bernstein (ArXiv 2018).


Year 2018

Algorithms and discrete structures
Monday December 3, 2018, 11AM, Salle 3052
Cédric Boutillier (LPSM, Sorbonne Université) Statistical mechanics on isoradial graphs

Isoradial graphs are embedded planar graphs in such a way that every face is inscribed in a circle of radius 1. They are a perfect ground to develop a theory of discrete complex analysis and to define integrable models in statistical mechanics. In this talk, we will describe combinatorial and geometric aspects of these graphs, and their impact on locality of some models of statistical mechanics (dimer models, random walk, spanning trees…)