Axe Complexités: Seminaire


Un séminaire bimensuel de l'axe complexités, où les membres du LIPN intéressés par la complexité viennent apprendre un sujet de façon approfondie, et développer des collaborations inter-équipes.

L'objectif est d'apprendre des techniques et des idées de base, fondamentales et intéressantes - en particulier les intuitions et les points de vue des experts. Il n'est pas nécessaire que les orateurs présentent leur propre travail.

Organizers: Sylvain Perifel, Nabil Mustafa.

B107, 13h.

Abstract.

2025

B107, 12h45.

Consider a data structure problem with possible data coming from a set \( \mathcal D \), queries coming from a set \(\mathcal Q\), and in the dynamic case updates coming from a set \(\mathcal U\). Then, the current state of the art in data structure lower bounds is \(t = \tilde\Omega(\log |\mathcal Q|)\) for static data structure problems, and \(\max(t_{\mathrm q},t_{\mathrm u}) = \tilde\Omega((\log n)^2)\) where \(n = \max(|\mathcal Q|,|\mathcal U|,\log |\mathcal D|)\) for dynamic.

We port Razborov and Rudich's natural-proofs framework to the setting of static and dynamic data structures in the cell probe model, in a way that strongly suggests this state of the art is unlikely to be improved anytime soon. A similar direction was recently taken also by Korten, Pitassi and Impagliazzo (FOCS 2025) who look at static data structure lower bounds in a different regime of parameters. Our contribution is:

- We define notions analogous to pseudorandom functions (PRF). We call these primitives *local PRFs*, in the context of static data structures, and *local and locally updatable (LLU) PRFs*, in the context of dynamic data structures.
- We then formulate cryptographic conjectures, namely, that secure local PRFs and secure LLU PRFs exist, precisely at the frontier where we are no longer able to prove static, respectively dynamic, data structure lower bounds. If these conjectures are true, it follows that the current state of the art in data structure lower bounds cannot be improved by a natural proof.
- We show that (almost) every single known data structure lower bound proof is a natural proof, by surveying all lower bounds in the literature (known to us). (The only exception is proofs based on lifting theorems.)
- It follows that, if our cryptographic conjecture is true, then all known lower bound proof techniques (minus the two exceptions) are unable to improve upon the state of the art. (We also present obstacles for the two exceptions.)
- Further, we provide concrete candidate constructions for our two pseudo-random primitives. We conjecture that our constructions are secure for parameters just above the state-of-the-art lower bounds. - We also show that, whether or not they are secure, our candidate PRFs at least satisfy the natural properties appearing in all (but one) known proofs.
- So if one is interested in improving upon the state of the art in static or dynamic data structure lower bounds, one must either find a non-natural method of proving such lower bounds (no such method currently exists), or one may as well begin by trying to break our PRF candidates.


Video.

B107, 12h45.

In this seminar, I will present one of the main formalisms used in structured prediction for text processing, namely Linear-Chain Conditional Random Fields (CRFs). These models are instances of Markov Random Fields specialized for defining discrete probabilities over sequences. I will present the methods used for inference (finding the most probable sequence) and learning (parametrisation by maximum likelihood estimation) for such models.

While this formalism is well-understood, wioth tractable inference,it is not amenable to parallel computing, which prevents it from leveraging modern architectures for computation, namely GPUs. I will then present a new convex approximation of the marginal inference problem, called mean regularization, from which we derive a parallelisable method to learn and predict based on Bregman projections.

Experimentally, our new method returns solutions closer to the original CRF than with other approximations such as Naive Mean-Field based on the minimization of the Kullback-Liebler divergence, while being orders or magnitude faster.

This is a joint work with Caio Corro (INSA Rennes) and Mathieu Lacroix (LIPN).

Slides.

Video.

Amphi Ampere, 12h30.

The talk will be a high-level presentation of expander graphs, not focused on the construction of such objects but rather on their applications in complexity. We will see how to use them to reduce the error of probabilistic algorithms, to design a logspace algorithm for undirected connectivity, and, if time permits (which from experience is never the case), to increase the Kolmogorov complexity of a string.

Video.

B107, 12h45.

In 1999, Schoning gave a beautiful and simple (but I repeat myself!) algorithm for k-SAT and similar constraint satisfaction problems. This was extended to a more general setting by Brakensiek and Guruswami in the following nice paper:

     Bridging between 0/1 and linear programming via random walks.

In this talk I will present the above paper, a nice illustration of substituting convexity for sparsity. No knowledge of random walks will be assumed. A nice exposition of Schoning's paper can be read from the Mitzenmacher-Upfal book on randomized algorithms.

Video.

B107, 13h.

A biclique cover of a graph consists of a cover of its edge set by complete bipartite graphs. The size of such a cover is the sum of the number of vertices of the bicliques. Small-size biclique covers of graphs are ubiquitous in computational geometry, and have been shown to be useful compact representations of graphs. We give a brief survey of classical and recent results on biclique covers and their applications, and give new families of graphs having biclique covers of near-linear size.
Joint work with Yelena Yuditsky (ULB).

Video.

B107, 13h.

We introduce new semi-algebraic proof systems for Quantified Boolean Formulas (QBF) analogous to the propositional systems Nullstellensatz, Sherali-Adams and Sum-of-Squares. We show how to transfer to this setting techniques both from the QBF literature (strategy extraction) and from propositional proof complexity (size-degree relations and pseudo-expectation). We obtain a number of strong QBF lower bounds and separations between these systems, even when disregarding propositional hardness.
This is joint work with Olaf Beyersdorff, Ilario Bonacina, Kaspar Kasche, and Luc Spachmann; to appear in SAT 2025.

Amphitheatre C.

USPN, Villetaneuse.

Workshop link: CAALM 2025.

Speakers include: C. Aiswarya, Siddharth Barman, Amik Raj Behera, Olaf Beyersdorff, Patricia Bouyer-Decitre, Sourav Chakraborty, Supratik Chakraborty, Dmitry Chistikov, Carola Doerr, Jonas Ellert, Joanna Fijalkow, Sandra Kiefer, Nutan Limaye, Claire Mathieu, Benjamin Monmège, Partha Mukhopadhyay, Nabil Mustafa, Anantha Padmanabha, Sylvain Perifel, Sophie Pinchinat, Ramprasad Saptharishi, Saket Saurabh, B. Srivathsan, K.V. Subrahmanyam, Sébastien Tavenas, K.S. Thejaswini, Stéphane Vialette, Georg Zetzsche.

Detailed Program.

Amphitheatre C, 13h30.

Finite model theory studies the power of logics on the class of finite structures. One of its goals is to characterize symmetric computation, that is, computation that abstracts away details which are not essential for the given task, by respecting the symmetries of the input. In this talk I will discuss connections between proof complexity and finite model theory, focussing on lower bounds. For certain proof systems, the existence of a succinct refutation can be decided in a symmetry-preserving way. This allows for a transfer of lower bounds from finite model theory to proof complexity.

Video.

B107, 12h.

Can you transform any randomized algorithm into a deterministic one without impairing performance too much? Can you show lower bounds on the size of Boolean circuits? I will explain how these two questions are connected and show an indomitable problem that still holds out against derandomization.

Video.

B107, 13h.

This is a survey of research going back more than 60 years on the power of first order logic, along with various restrictions and extensions, to express the behavior of finite automata operating on strings over a finite alphabet. ‘Restrictions and extensions’ here means modifying the set of atomic formulas, bounding the quantifier depth, bounding the number of bound variables, etc. We want to be able to determine when a particular property (given in some other formalism, for example by a finite automaton) is expressible in the variant of first-order logic under study. When the atomic formulas are restricted in such a way that only regular languages can be defined, there is an intricate mathematical apparatus, based in the algebraic theory of finite semigroups, that provides very precise answers to these questions. This will be the subject of the first part of the talk. There are strong connections, known since the 1980’s, between this theory and questions about the complexity of fixed depth circuit families whose gates have unbounded fan-in. This, along with a few other extensions (for example, to automata operating on trees) and some recent results and open probems, will be explored in the second part of the talk.

Amphi Fermat, 12h.

Linear Programming is a pervasive tool in algorithm design for optimization problems. Linear Programs (LPs) are known to be able to effectively model any problem that can be efficiently solved on a computer. But are they also able to efficiently model NP-hard problems? An affirmative answer to this question will settle the P vs. NP problem affirmatively, and so it is no surprise that the answer is no. However, attempts to prove such limits on the power of LPs lead us to explore interesting connections to communication complexity. In this talk, I will explore such a connection that resulted in a proof that the Traveling Salesman Problem cannot be solved well using LPs. I will first discuss the subtleties involved in making the above claim precise. Then I will describe the result, its connection to communication complexity, and various generalizations to the quantum setting and beyond.

The talk is based on joint work with Samuel Fiorini, Serge Massar, Sebastian Pokutta, and Ronald de Wolf.

Video.

Part of Probability Seminar.

Room B405, 11h20.

In this talk (in English, because no one is perfect) I will give some examples of the crucial use of probabilistic methods and ideas for several basic problems in combinatorics and algorithms for geometric problems. In particular, we will see how constraints induced by geometry can be utililized to improve classic probabilistic constructions (Vapnik-Chervonenkis bounds, Talagrand's bound for approximations). I will also present two beautiful and simple open problems, whose solution probably will require a deeper combination of probability and combinatorics.

Parts of these talks will be taken from my book here (https://www.ams.org/books/surv/265/).

Room B107.

Tuesday, February 4th

  • 1.30pm: Geoffroy Caillat-Grenier (LIRMM)
    From combinatorics of graphs to communication complexity in algorithmic information theory
  • 2.30pm: Alexander Shen (LIRMM)
    Erdos, Miller and a simple combinatorial game
  • 4.30pm: Thomas Seiller (LIPN)
    Games and hierarchy for time-bounded Kolmogorov Complexity

Wednesday, February 5th

  • 10am: Ivan Titov (LaBRI)
    Schnorr randomness
  • 11am: Subin Pulari (LaBRI)
    One-way functions and polynomial-time dimension
  • 12pm: Andrei Romashchenko (LIRMM)
    High probability means brief description: time bounded versions of the optimal coding theorem

Room B107, 12h.

I'll give an introduction to algebraic complexity theory, which studies the computation of polynomials via arithmetic circuits and variants thereof. As in other areas of complexity, there is much we do not know. As a striking contrast, I will give a detailed presentation for the computation of non-commutative polynomials by algebraic branching programs, a rare setting which we understand very well.

Video.


2024

Room B107, 13h.

The character table of the symmetric group $S_n$, of permutations of n objects, is of fundamental interest in theoretical physics, combinatorics as well as computational complexity theory. We investigate the implications of an identity, which has a geometrical interpretation in combinatorial topological field theories, relating the column sum of normalised central characters of $S_n$, to a sum of structure constants of multiplication in the centre of the group algebra of $S_n$. The identity leads to the proof that a combinatorial computation of the column sum belongs to complexity class #P. The sum of structure constants has an interpretation in terms of the counting of branched covers of the sphere. This allows the identification of a tractable subset of the structure constants related to genus zero covers. We use this subset to prove that the column sum for a conjugacy class labelled by partition λ is non-vanishing if and only if the permutations in the conjugacy class are even. This leads to the result that the determination of the vanishing or otherwise of the column sum is in complexity class P.

Slides.
Video.

Room B107, 13h.

This talk explores the connection between graph mixing properties and the barriers in communication complexity. We show how the strong mixing property of a graph can be interpreted as the hardness of "extracting" the mutual information shared between vertices connected by an edge. This hardness, in turn, presents an inherent obstacle to solving some communication problems effectively, i.e., the remote parties (connected by a communication channel) cannot compute the result without sending to each other long enough messages. Building on these observations, we analyze the communication complexity of the problem of secret key agreement. Talk is based on joint works with G. Caillat-Grenier and R. Zyavgarov.

Video.

Room B107, 11h30.

Data compression is a key concept in computer science, relevant in contexts such as data storage and transmission, learnability of patterns from data, and complexity theory. In particular, in complexity theory, a Boolean function is considered hard if its truth table cannot be compressed by Boolean circuits. But how difficult is it to estimate the inherent compressibility of a string? This question is the focus of a thriving research program in "meta-complexity", ie., the complexity of complexity (since incompressibility can be considered as a measure of complexity of a string). I will discuss various recent results connecting this question to fundamental results and directions in areas such as learning theory, cryptography, complexity lower bounds, and Gödel-type incompleteness phenomena in computer science.

Video.

Room B107, 12h.

Among the many inequalities proved by Talagrand, the one which is most often labelled as Talagrand's inequality is the following: Let X_1... X_n be iid random variables in [0,1] and let f be a convex, 1-Lipschitz function from [0,1]^n to R. If M(f) stands for a median of f(X), then

P(|f(X) - Mf(X)|)>t < 4 exp (-t^2/4)

In particular, this inequality does not depend on n. We will see how this result compares with other concentration results and give some elements of the proof.

Video.

Amphi A.

See the schedule and talk details here:

https://lipn.univ-paris13.fr/~mustafa/ANR-ADDS/CGV/

Room B107, 12h.

A triangulation of a convex polygon Σ is a set of pairwise non-crossing diagonals of Σ that decompose this polygon into triangles. The flip-graph F(Σ) of Σ is the graph whose vertices are these triangulations and whose edges connect two triangulations when they differ by a single diagonal. It turns out that F(Σ) can be represented alternatively using any Catalan family instead of triangulations and one can for example replace triangulation by binary trees and flips by rotations between them. This graph is the edge-graph of a polytope---the associahedron---and the complexity of computing distances between its vertices is a major open problem in computer science.

In a first part, this talk will focus on an elementary 2-approximation algorithm for flip distance computation and on a popular heuristics for this problem, based on the number of arcs crossings between two triangulations.

The second part focuses on the Sleator--Tarjan--Thurston 3-dimensional triangulation model for the paths in F(Σ). In their seminal 1988 article, they prove that, if the path is a geodesic, then this 3-dimensional model is a simplicial complex. The recent proof that this simplicial complex is flag is presented as well as several consequences as for instance, a proof that the arc crossings based flip distance estimation heuristics is, at best, a 3/2-approximation algorithm.

This talk is based on joint work with Zili Wang.

Video.

PhD defence of Alexandre Dupont-Bouillard.

Video ... Congratulations Alexandre!!

Because Σp2- and Σp3-hardness proofs are usually tedious and difficult, not so many complete problems for these classes are known. This is especially true in the areas of min-max regret robust optimization, network interdiction, most vital vertex problems, blocker problems, and two-stage adjustable robust optimization problems. Even though these areas are well-researched for over two decades and one would naturally expect many (if not most) of the problems occurring in these areas to be complete for the above classes, almost no completeness results exist in the literature. We address this lack of knowledge by introducing over 70 new Σp2-complete and Σp3-complete problems. We achieve this result by proving a new meta-theorem, which shows Σp2- and Σp3-completeness simultaneously for a huge class of problems. The majority of all earlier publications on Σp2- and Σp3-completeness in said areas are special cases of our meta-theorem. Our precise result is the following: We introduce a large list of problems for which the meta-theorem is applicable (including clique, vertex cover, knapsack, TSP, facility location and many more). For every problem on this list, we show: The interdiction/minimum cost blocker/most vital nodes problem (with element costs) is Σp2-complete. The min-max-regret problem with interval uncertainty is Σp2-complete. The two-stage adjustable robust optimization problem with discrete budgeted uncertainty is Σp3-complete. In summary, our work reveals the interesting insight that a large amount of NP-complete problems have the property that their min-max versions are 'automatically' Σp2-complete.

Readings:
  • See the paper here.
Video.

We continue with the proof of the "switching lemma".

Readings: Video.

The fact that the PARITY function is not computable by bounded-depth polynomial-size families of Boolean circuits with unbounded fan-in is a fundamental result in circuit complexity, independently proved by Ajtai and by Furst, Saxe and Sipser in the 1980s.

I will give the basic definitions and an outline of the proof, which uses a powerful result called the "switching lemma". I will only prove the result using the switching lemma as a black box.

The proof of the switching lemma itself will be the topic of future talk.

Readings:
  • Section 13.1 from here. In particular, we will go through Section 13.1.1 but NOT 13.1.2.
Video.

List of topics for the year 2024 discussed, together with possible working groups on specific topics.