BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Olivier Bournez//Algorithms of Saclay Plateau seminar//EN
X-WR-CALNAME:Algorithms of Saclay Plateau seminar
BEGIN:VEVENT
SUMMARY:Manon Blanc / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20230628T100000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20230628T110000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.832543859644
DESCRIPTION:Manon Blanc: Measuring robustness of dynamical systems. Relati
ng time and space to length and precision\n\nVerification of discrete time
or continuous time dynamical systems is known to be undecidable. However\
, undecidability is known not to hold for robust systems: if robustness is
defined as the fact that the reachability relation is stable under infini
tesimal perturbation\, then decidability holds. Similarly\, while undecid
ability holds for logical formulas over the reals\, it does not when consi
dering $\\delta$-undecidability\, i.e. when properties are either true or
delta-far from being true. We first relate these notions of robustness. Th
en\, we extend these statements at the complexity level: When a system is
robust\, it makes sense to quantify at which level of perturbation a syste
m is robust. We prove assuming robustness to polynomial perturbation on pr
ecision leads to PSPACE and even to a characterization of PSPACE. We prove
assuming robustness to polynomial perturbation on time or length leads to
similar statements but with PTIME. We also relate this to analogue models
of computation.\n
LOCATION:room Grace Hopper
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Olivier Bournez / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20230601T130000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20230601T140000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.972519842409
DESCRIPTION:Olivier Bournez: Analog computing is back\n\nThe idea of consi
dering analog models of computation (by opposition to today’s digital mo
dels) is not new\, and actually the first ever built computer were analog.
Some well-known models of analog computers have been proposed\, such as t
he GPAC (General Purpose Analog Computer) of Claude Shannon in 1941. Howe
ver\, these models have been mostly forgotten as they were 1) thought to b
e less powerful than a modern computer 2) not as good as modern computers
for doing precise computations. But it turns out that 1) is wrong\, and th
is was proved only a decade ago\, and analog computers could even solve s
ome problems faster and 2) that many modern applications of computers are
precisely contexts\, such as machine learning or deep learning\, where pre
cision is not so important. What matters most is speed and energy consumpt
ions\, which are precisely the strength of analog computers. Actually\, an
alog computing comes historically also from the idea of computing by analo
gy. We will review various recent rebirth of analog computing and analog m
odels\, including recent startups proposing very fast computing for deep l
earning\, or (re)birth of models based on analog computing\, such as neura
l ordinary differential equations\, or explanations of performances of som
e digital models through the eyes of analog computing.\n
LOCATION:room Salle Grace Hopper
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Philipp Fischbeck / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20230316T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20230316T113000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.321453433557
DESCRIPTION:Philipp Fischbeck: On the External Validity of Average-Case An
alyses of Graph Algorithms\n\nThe number one criticism of average-case ana
lysis is that we do not actually know the probability distribution of real
-world inputs. Thus\, analyzing an algorithm on some random model has no i
mplications for practical performance. At its core\, this criticism doubts
the existence of external validity\, i.e.\, it assumes that algorithmic b
ehavior on the somewhat simple and clean models does not translate beyond
the models to practical performance real-world input. With this paper\, we
provide a first step towards studying the question of external validity s
ystematically. To this end\, we evaluate the performance of six graph algo
rithms on a collection of 2745 sparse real-world networks depending on two
properties\; the heterogeneity (variance in the degree distribution) and
locality (tendency of edges to connect vertices that are already close). W
e compare this with the performance on generated networks with varying loc
ality and heterogeneity. We find that the performance in the idealized set
ting of network models translates surprisingly well to real-world networks
. Moreover\, heterogeneity and locality appear to be the core properties i
mpacting the performance of many graph algorithms\n
LOCATION:room Salle Emmy Noether
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Titouan Carette / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20230309T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20230309T113000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.812678830381
DESCRIPTION:Titouan Carette: Perfect matchings\, quantum computing and mon
oidal categories\n\nIn 2002\, Leslie Valiant designed a computational mode
l based on counting the number of perfect matchings of weighted graphs: th
e matchgates. Matchgates can directly be interpreted as quantum processes
providing an original combinatorial approach to quantum computing. In the
general case\, counting perfect matchings is #P-complete. However\, in the
specific case of planar graphs\, the FKT-algorithm allows counting perfec
t matchings in polynomial time. As a consequence\, planar matchgates provi
de a class of quantum computation that can be classically simulated in pol
ynomial time.Completely independently\, in 2010\, as a part of the categor
ical quantum mechanics program\, Coecke and Kissinger introduced the ZW-ca
lculus\, a graphical language inspired by two kinds of entanglement\, the
GHZ-states and W-states. This calculus quickly demonstrated interesting al
gebraic properties allowing it to be the first graphical language to be pr
oven universal and complete for all linear maps. In this talk\, I will pre
sent joint works with Étienne Moutot\, Thomas Perez and Renaud Vilmart\,
building a bridge between the two formalisms: matchgates and ZW-calculus.
It appears that reformulating matchgate theory into the category-theoretic
framework of ZW-calculus allows for a much simpler presentation. Converse
ly\, the matchgate approach provides the ZW-calculus with a straightforwar
d combinatorial interpretation. I will introduce a fragment of ZW-calculus
\, the planar W-calculus\, and show that it is universal and complete for
matchgates. Then I will present a variety of consequences\, from new algor
ithms for perfect matching counting and quantum simulation to a diagrammat
ical approach to determinant theory.\n
LOCATION:room Salle Grace Hopper
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Duri Andrea Janett / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20230105T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20230105T120000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.674172121661
DESCRIPTION:Duri Andrea Janett: Two-Dimensional Drift Analysis: Optimizing
Two Functions Simultaneously Can Be Hard\n\nThe performance of Evolutiona
ry Algorithms (EAs) in dynamic environments\, that is\, environments in wh
ich the fitness function changes over time\, has recently been studied (e.
g.\, [Lengler\, Meier\, 2020]). In this talk\, we develop and analyse a mi
nimal example TwoLinear of a dynamic environment that can be hard for EAs.
The environment consists of two linear functions f1 and f2 with positive
weights 1 and n\, and in each generation selection is based on one of them
at random. They only differ in the set of positions that have weight 1 an
d n. We show that the (1+1)-EA with mutation rate χ/n is efficient for sm
all χ on TwoLinear\, but does not find the shared optimum in polynomial t
ime for large χ.To obtain the above result\, we apply drift analysis in t
wo dimensions. Drift analysis is one of the most powerful techniques to an
alyse the performance and behaviour of EAs. Previously\, it has only been
applied in one dimension. Here\, we are in the case of two random variable
s X1\, X2\, and the drift is approximatively given by A·(X1\, X2)T for a
matrix A. More precisely\, we are in the case where X1 and X2 impede each
other’s progress\, and we give a full characterisation of this case. \n
LOCATION:room Salle Philippe Flajolet
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Hsien-Kuei Hwang / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20221109T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20221109T120000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.0176655802765
DESCRIPTION:Hsien-Kuei Hwang: Bell numbers in Matsunaga's and Arima's Genj
ikō combinatorics: Modern perspectives and local limit theorems\n\nWe exa
mine and clarify in detail the contributions of Yoshisuke Matsunaga (1694?
--1744) to the computation of Bell numbers in the eighteenth century (in t
he Edo period)\, providing modern perspectives to some unknown materials t
hat are by far the earliest in the history of Bell numbers. Later clarific
ation and developments by Yoriyuki Arima (1714--1783)\, and several new re
sults such as the asymptotic distributions (notably the corresponding loca
l limit theorems) of a few closely related sequences are also given.\n
LOCATION:room Grace Hopper
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Riccardo Gozzi / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20221019T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20221019T120000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.267344447425
DESCRIPTION:Riccardo Gozzi: Totalization of Ordinary Differential Equation
s\n\n"The totalization process was introduced by Denjoy in 1912 as an inte
rative procedure to obtain the antiderivative of any derivative. This idea
has generated the notion of Denjoy integral\, first of a serie of notions
of integration proposed in literature as alternatives to Riemann and Lebe
sgue integrals in order to successfully retrieve the antiderivative of som
e class of pathological derivatives. This talk follows the path taken by D
enjoy\, describing the details of its solution for the problem of integrat
ion\, and applies it to the realm of first order ODEs\, exploring the set
theoretical complexity of obtaining the solution of the dynamical system f
or ODEs with specific pathological right-hand terms."\n
LOCATION:room Grace Hopper
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Martin Krejca / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20221013T113000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20221013T123000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.387128696655
DESCRIPTION:Martin Krejca: Accelerated Information Dissemination on Networ
ks with Local and Global Edges\n\n"Bootstrap percolation is a classical mo
del for the spread of information in a network. In the round-based version
\, nodes of an undirected graph become active once at least r neighbors we
re active in the previous round. We consider a slightly modified variant\,
acting on graphs that contain two types of edges—modeling local and glo
bal interactions\, respectively. In this model\, information spreads immed
iately via local edges but still requires a certain number r of active nei
ghbors in order to spread via global edges. We show for certain graph clas
ses that this modified process\, when starting with a single active node\,
results in a phase transition with respect to how quickly further nodes a
re activated. Initially\, the spread is rather slow\, but it gains signifi
cant speed once global edges are being used to activate nodes."\n
LOCATION:room Nicolaas Govert de Bruijn
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Simon Wietheger / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20221007T113000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20221007T123000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.280613824702
DESCRIPTION:Simon Wietheger: Crossover for Cardinality-Constrained Optimiz
ation\n\n"In order to understand better how and why crossover can benefit
optimization\, we consider pseudo-Boolean functions with an upper bound
𝐵 on the number of 1s allowed in the bit string (cardinality constraint
). We consider the natural translation of the OneMax test function\, a lin
ear function where 𝐵 bits have a weight of 1 + 𝜀 and the remaining b
its have a weight of 1. The literature gives a bound of Θ(𝑛^2) for the
(1+1) EA on this function. Part of the difficulty when optimizing this pr
oblem lies in having to improve individuals meeting the cardinality constr
aint by flipping both a 1 and a 0. The experimental literature proposes ba
lanced operators\, preserving the number of 1s\, as a remedy. We show that
a balanced mutation operator optimizes the problem in 𝑂 (𝑛 log 𝑛
) if\,𝑛 − 𝐵 = 𝑂 (1). However\, if 𝑛 − 𝐵 = Θ(𝑛)\, we
show a bound of Ω(𝑛^2)\, just as classic bit flip mutation. Crossover
and a simple island model gives 𝑂 (𝑛^2/log 𝑛) (uniform crossover
) and 𝑂 (𝑛√𝑛) (3-ary majority vote crossover). For balanced uni
form crossover with Hamming distance maximization for diversity we show a
bound of 𝑂 (𝑛 log 𝑛)."\n
LOCATION:room Poincaré
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Riccardo Gozzi / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20220621T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20220621T120000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.406843287323
DESCRIPTION:Riccardo Gozzi: Analog characterization of complexity classees
\n\nIn the first part of the presentation I will introduce the concept of
analog computation in relation with integrator devices used in the 1940’
s to compute simple operations\, called differntial analyzers. A descripti
on of the theoretical model behind the behaviors of those machine was firs
t provided by Shannon\, with his GPAC model which stands for Generable Pur
pose Analog Computation model. I will describe some of the main modificati
ons that have been later applied in litterature to the model in order to s
implify its formulation and improve its computational power. Following thi
s guideline\, I will then explain how these modifications led to an equiva
lence between this model and the setting of computable analysis\, meaning
that every function that can be computed within the computable analysis fr
amework can also be computed by the GPAC model\, and viceversa. During the
course of this first\, introductory\, part of the talk\, the motivations
at the core of this research will be discussed as well. In the second part
of the presentation I will illustrate how\, with the correct improvements
to the notion of computation of the GPAC model\, this particular equivale
nce can be extended to the case of polynomial time complexity\, leading to
an equivalence between the well known complexity calss P and a certain cl
ass of systems of ODEs. To obtain this result it is required a way to enco
de and reproduce the behavior of the transiction function of a Turing mach
ine in a continuous setting\, keeping bounded the error introduced during
this simulation.This second part of the talk will be more quantitative tha
n the first\, including more technical details. Finally\, in the last part
of the presentation\, I will briefly mention how the results previuosly s
howed can be applied to further characterize higher complexity classes\, s
uch as EXPTIME or PSPACE\, with similar dynamical system.\n
LOCATION:room Grace Hopper
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Zhongdi QU / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20220621T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20220621T150000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.610819749835
DESCRIPTION:Zhongdi QU: A First Runtime Analysis of the NSGA-II on a Multi
modal Problem\n\nVery recently\, the first mathematical runtime analyses o
f the multi-objective evolutionary optimizer NSGA-II have been conducted (
AAAI 2022\, GECCO 2022 (to appear)\, arxiv 2022). We continue this line of
research with a first runtime analysis of this algorithm on a benchmark p
roblem consisting of two multimodal objectives. We prove that if the popul
ation size $N$ is at least four times the size of the Pareto front\, then
the NSGA-II with four different ways to select parents and bit-wise mutati
on optimizes the OneJumpZeroJump benchmark with jump size $2 \\le k \\le n
/4$ in time $O(N n^k)$. When using fast mutation\, a recently proposed hea
vy-tailed mutation operator\, this guarantee improves by a factor of $k^{\
\Omega(k)}$. Overall\, this work shows that the NSGA-II copes with the loc
al optima of the OneJumpZeroJump problem at least as well as the global SE
MO algorithm.\n
LOCATION:room Philippe Flajolet
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Joël Ouaknine / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20220519T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20220519T153000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.422871417115
DESCRIPTION:Joël Ouaknine: The Skolem Landscape\n\nThe Skolem Problem ask
s how to determine algorithmically whether a given linear recurrence seque
nce (such as the Fibonacci numbers) has a zero. It is a central question i
n dynamical systems and number theory\, and has many connections to other
branches of mathematics and computer science. Unfortunately\, its decidabi
lity has been open for nearly a century! In this talk\, I will present a s
urvey of what is known on the Skolem Problem and related questions\, inclu
ding recent and ongoing developments. \n
LOCATION:room LIX Sophie Germain + online upon request
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Franck Djeumou / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20220414T150000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20220414T160000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.932226489086
DESCRIPTION:Franck Djeumou: Neural Networks with Physics-Informed Architec
tures and Constraints for Dynamical Systems Modeling\n\nEffective inclusio
n of physics-based knowledge into deep neural network models of dynamical
systems can greatly improve data efficiency and generalization. Such a pri
ori knowledge might arise from physical principles (e.g.\, conservation la
ws) or from the system's design (e.g.\, the Jacobian matrix of a robot)\,
even if large portions of the system dynamics remain unknown. We develop a
framework to learn dynamics models from trajectory data while incorporati
ng a priori system knowledge as inductive bias. By exploiting a priori sys
tem knowledge during training\, the proposed approach learns to predict th
e system dynamics two orders of magnitude more accurately than a baseline
approach that does not include prior knowledge\, given the same training d
ataset. \n
LOCATION:https://ecolepolytechnique.zoom.us/j/87240940887 (online\, live f
rom Austin\, Texas\, US)
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Léo Paviet Salomon / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20220324T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20220324T120000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.461776547805
DESCRIPTION:Léo Paviet Salomon: Groupe fondamental et pavages du plan: qu
elques constructions\n\nOn appelle sous-shift (ou sous-décalage) un ensem
ble de pavages ou de coloriages du plan respectant certaines contraintes l
ocales. Historiquement introduits comme discrétisations de systèmes dyna
miques continus\, on se propose ici d'en étudier un invariant topologique
\, introduit par W.Geller et J.Propp\, le Groupe Fondamental Projectif. A
l'instar de la définition habituelle du groupe fondamental\, un invariant
d'espaces topologiques\, il s'agira ici de comprendre comment l'on peut d
éfinir une notion de chemins dans les pavages\, reliant les configuration
s entre elles\, et d'étudier comment les déformations de ces chemins per
mettent d'associer à chaque pavage un unique objet algébrique: son group
e fondamental projectif. En particulier\, on montrera dans cet exposé com
ment réaliser une large classe de groupes comme groupes fondamentaux de c
ertains pavages.\n
LOCATION:room Salle Henri Poincaré
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nathan Grosshans / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20220317T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20220317T120000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.446841242061
DESCRIPTION:Nathan Grosshans: Visibly pushdown languages in AC^0\n\nOne im
portant research endeavour at the intersection of circuit complexity theor
y\, algebraic automata \ntheory and logic is the classification of regular
languages according to their localisation \nwithin the internal structure
of NC^1\, the class of languages decided by Boolean circuits of polynomia
l size\, logarithmic depth and with gates of constant fan-in. In some sens
e\, the search for such a classification concentrates most of the open que
stions we have about the relationship between NC1 and its well-studied sub
classes.\n\nWhile many questions are still open\, one of the greatest succ
esses of this research endeavour has been the characterisation of the regu
lar languages in AC^0\, the subclass of NC^1 corresponding to Boolean cir
cuits of polynomial length\, constant depth and with gates of unbounded fa
n-in. This characterisation takes the form of a triple languages-algebra-l
ogic correspondence: a regular language is in AC0 if and only if its synta
ctic morphism is quasi-aperiodic if and only if it is definable in first-o
rder logic over words with linear order and modular predicates.\n\nIt is n
atural to try to extend such results to classes of formal languages great
er than the class of regular languages. A well studied and robust such cl
ass is given by visibly pushdown languages (VPLs): languages recognised by
pushdown automata where the stack-height-behaviour only depends on the l
etters read from the input. Over the previous decade\, a series of works
concentrated on the fine complexity of VPLs\, with several achievements:
one of those was a characterisation of the class of visibly counter langu
ages (basically VPLs recognised by visibly pushdown automata with only on
e stack symbol) in AC^0 by Krebs\, Lange and Ludwig. However\, the charac
terisation of the VPLs in AC^0 still remains open. \n\nIn this talk\, I
shall present a conjectural characterisation of the VPLs in AC^0 obtained
with Stefan Göller at the Universität Kassel. It is inspired by the conj
ectural characterisation given by Ludwig in his Ph.D. thesis as a general
isation of the characterisation for visibly counter languages\, but that
is actually false. In fact\, we give a more precise general conjectural ch
aracterisation that builds upon recognisability by morphisms into Ext-alge
bras\, an extension of recognisability by monoid-morphisms proposed by Cz
arnetzki\, Krebs and Lange to suit the case of VPLs. This characterisation
classifies the VPLs into three categories according to precise conditions
on the Ext-algebra-morphisms that recognise them:\n- those that are TC^0-
hard\;\n- those that are in AC^0\;\n- those that correspond to a well-iden
tified class of "intermediate languages" that we believe to be neither in
AC^0 nor TC^0-hard.\n
LOCATION:https://ecolepolytechnique.zoom.us/j/87240940887 (online)
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Martin Krejca / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20220217T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20220217T120000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.203175735889
DESCRIPTION:Martin Krejca: The Power of Probabilistic Models in Optimizati
on\n\nFor many real-world optimization problems\, the objective function i
s only indirectly accessible\, for example\, via simulations. In this sett
ing\, randomized search heuristics (RSHs) are applied to great success\, g
uided solely by the quality of samples. One important class of these heuri
stics are estimation-of-distribution algorithms (EDAs)\, which maintain an
d refine a probabilistic model of the search space.\n\nIn this talk\, I di
scuss some of my results on the theoretical analysis of EDAs by presenting
properties of EDAs that set them apart from other RSHs. We see that EDAs
cope inherently well with noisy objective functions\, due to the probabili
stic model tolerating faulty updates to a certain degree. However\, we als
o show that these models typically degenerate if important updates are wit
hheld for longer periods of time. We conclude by presenting how this probl
em is circumvented when applying better rules to handle updates.\n
LOCATION:room Salle Philippe Flajolet
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Ulysse Chabaud / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20220203T163000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20220203T173000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.715380919425
DESCRIPTION:Ulysse Chabaud: Holomorphic Quantum Computing\n\nThe advent of
quantum information processing promises dramatic advantages with respect
to its classical counterpart\, notably for computing. I will give an intro
duction to quantum computing through the lens of holomorphic functions\, w
hich allow us to elegantly describe both discrete- and continuous-variable
quantum computations\, using classical dynamical systems. As an applicati
on\, I will discuss the characterisation of quantum properties that are ne
cessary resources for quantum computational advantages\, such as non-Gauss
ianity or entanglement.\n\nJoint work with Saeed Merhaban (arXiv:2111.0011
7).\n
LOCATION:https://ecolepolytechnique.zoom.us/j/87240940887 (online\, live f
rom California)
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Sonia Vanier / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210624T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210624T153000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.237727614182
DESCRIPTION:Sonia Vanier: Distributed Denial of Service cyber-attacks in 5
G networks: a robust approximation approach\n\nDistributed Denial of Servi
ce (DDoS) cyberattacks represent a major security risk for network operato
rs and internet service providers. They thus need to invest in security so
lutions to protect their network against DDoS attacks. The present work fo
cuses on deploying a network function virtualization based architecture to
secure a network against an on-going DDoS attack. We assume that the targ
et\, sources and volume of the attack have been identified. However\, due
e.g. to 5G network slicing\, the exact routing of the illegitimate flow in
the network is not known by the internet service provider. We seek to det
ermine the optimal number and locations of virtual network functions in or
der to remove all the illegitimate traffic while minimizing the total cost
of the activated virtual network functions. We propose a robust optimizat
ion framework to solve this problem. The uncertain input parameters corres
pond to the amount of illegitimate flow on each path connecting an attack
source to the target and can take values within a predefined uncertainty s
et. In order to solve this robust optimization problem\, we develop an adv
ersarial approach in which the adversarial sub-problem is solved by a Bran
ch & Price algorithm. The results of our computational experiments\, carri
ed out on medium-size randomly generated instances\, show that the propose
d solution approach is able to provide optimal solutions within short comp
utation times\n
LOCATION:https://ecolepolytechnique.zoom.us/j/87240940887
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Riccardo Gozzi / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210512T103000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210512T113000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.142169947162
DESCRIPTION:Riccardo Gozzi: Analog characterization of standard complexity
classes by means of ODEs\n\nIn this presentation it will be shown how to
make use of ordinary differential equations (ODEs) to describe standard co
mplexity classes. Previously it was shown that the classes P and FP can be
characterized with ODEs. Here we show that ODEs can also be used to chara
cterize a wide range of computable functions\, from exponentials up to inc
luding all elementary functions. It will be also discussed the case of spa
ce complexity classes\, introducing the definition of a particular dynamic
al system able to describe functions in FPSPACE. Finally\, to complement
what have been done with functions\, the treatment of classes of languages
such as EXPTIME and PSPACE will be included in the analysis.\n
LOCATION:https://ecolepolytechnique.zoom.us/j/87240940887
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Janna Burman / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210408T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210408T153000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.642641648101
DESCRIPTION:Janna Burman: Time-Optimal Self-Stabilizing Leader Election in
Population Protocols\n\nWe consider the standard population protocol mode
l\, where (a\npriori) indistinguishable and anonymous agents interact in p
airs\naccording to uniformly random scheduling. The self-stabilizing\nlead
er election problem requires the protocol to converge on a\nsingle leader
agent from any possible initial configuration. We\ninitiate the study of t
ime complexity of population protocols\nsolving this problem in its origin
al setting: with probability 1\,\nin a complete communication graph. The o
nly previously known\nprotocol by Cai\, Izumi\, and Wada [Theor. Comput. S
yst. 50] runs\nin expected parallel time \\Theta(n2) and has the optimal n
umber\nof n states in a population of n agents. The existing protocol\nhas
the additional property that it becomes silent\, i.e.\, the\nagents' stat
es eventually stop changing.\n\nObserving that any silent protocol solving
self-stabilizing leader election requires \\Omega (n) expected parallel t
ime\, we introduce a silent protocol that uses optimal O(n) parallel time
and states. Without any silence constraints\, we show that it is possible
to solve self-stabilizing leader election in asymptotically optimal expect
ed parallel time of O(log n)\, but using at least exponential states (a q
uasi-polynomial number of bits). All of our protocols (and also that of Ca
i et al.) work by solving the more difficult ranking problem: assigning ag
ents the ranks 1\, … \,n.\n
LOCATION:https://ecolepolytechnique.zoom.us/j/82016424508
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Benoit Monin / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210401T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210401T153000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.0396855563059
DESCRIPTION:Benoit Monin: Une petite histoire de la K-trivialité\n\nLa co
mplexité de Kolmogorov est utilisée avec succès pour\ncaractériser l'a
léatoire pour les chaînes binaires infinies : Il\ns'agit des chaînes do
nt la complexité de Kolmogorov de leurs\npréfixes est maximale. A l'oppo
sé\, les chaînes binaires infinies\ndites "K-triviales" sont celles dont
la complexité de Kolmogorov\nde leurs préfixes est minimale. La classe
des K-triviaux est\ndénombrable\, et contient "juste un peu plus" que les
chaînes\nbinaires infinies calculables. Les nombreuses études sur les\n
K-triviaux depuis une vingtaine d'années ont révélé la grande\nrichess
e de cette classe. Nous en présenterons les différents\naspects.\n
LOCATION:https://ecolepolytechnique.zoom.us/j/82016424508
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Giuseppe Di Molfetta / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210318T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210318T153000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.442586205931
DESCRIPTION:Giuseppe Di Molfetta: Gauge-invariance in celullar automata an
d multi-scales analysis\n\nCellular Automata constitute the most establish
ed distributed model of computation on space-time grid. It is clearly phys
ics-like\, in the sense that it shares some fundamental symmetries such as
homogeneity (invariance of the physical laws in time and space)\, causali
ty\, and often reversibility. When a CA is invariant under a transformatio
n identically performed at every point of the configuration space\, they a
re said to have a global symmetry. Typical global symmetries include refle
ctions\, rotations\, time inversion. Local symmetries\, the cornerstone of
gauge theories\, is a stronger constraint. I will provide a constructive
method\, a step-by-step procedure\, to make cellular automata invariant un
der the local action of a gauge group and the notion of gauge-equivalence
will be formalized. Then\, I will extend such results into the Quantum rea
lm by means of a concrete example. In conclusion\, I will discuss how such
discrete time and discrete space gauge invariant automata can be describe
d at larger scale\, e.g. by differential equations\, with and without info
rmation loss. \n
LOCATION:https://ecolepolytechnique.zoom.us/j/82016424508
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Miki Hermann / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20210218T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20210218T153000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.360163772345
DESCRIPTION:Miki Hermann: Logical Analysis of Data\n\nWe show how to cope
with Big Data by means of Automated Deduction. We generate a Horn or a bij
unctive formula from sets of positive and negative tuples T and F\, respe
ctively These sets of tuples have been previously shortened to a locally m
inimal length\, provided that the two sets T and F keep an empty intersect
ion. Since the problem to find the minimal length is an NP-optimization pr
oblem\, we apply different approximation strategies. We also apply two app
roaches to formula production: (1) the LARGE approach\, where only tuples
of F falsify the produced formula\, and (2) EXACT\, where only tuples of T
satisfy the formula. In case of the large approach we apply a set cover
approximation algorithm to keep the minimal set of clauses falsifying all
tuples from the set F. The produced formula can be used to further charact
erize subsequent sets of tuples and identify their membership among the tr
ue or false examples. The whole system\, called MCP for Multiple Character
ization Problem\, has been implemented and can be found at .\n\n(research done in collaboration with Gernot Sal
zer\, Technische Universität Wien\, Vienna\, Austria)\n
LOCATION:https://cnrs-nqa.my.webex.com/cnrs-nqa.my-en/j.php?MTID=m756d7af4
63e4bd67a15d975d98225be4
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Laurent Perron / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200312T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200312T153000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.372457903666
DESCRIPTION:Laurent Perron: Recherche Opérationnelle à Google\n\nA trave
rs une série d'exemples\, je décrierai les applications de\nla recherche
opérationnelle et de l'optimisation discrète à\nGoogle. Puis je me foc
aliserai sur l'apport récent des techniques\ndes moteurs SAT (satisfiabil
ité) et les challenges et opportunités\nqui lui sont liées.\n
LOCATION:room LRI\, room 445
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Guilhem Gamard / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200220T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200220T153000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.284773707529
DESCRIPTION:Guilhem Gamard: Rice-like theorems in Automata Networks\n\n\nA
n Automata Network (AN) consists of a finite digraph and a finite\nset of
states. Each node has a state and updates itself in\nfunction of the stat
e of its inbound neighbours. Updates are\nsynchronous and parallel\, as i
n cellular automata.\n\nThis model was initially defined in biology\, wher
e each node\nencodes the (non-)expression of a gene. As genes influence e
ach\nother's expression\, pretty complex dynamics may ensue. Later on\,\n
ANs were also considered in fields such as engineering. But\nsurprisingly
\, the theoretical and general study of ANs from a\ncomputer science persp
ective is rather recent.\n\nIn this talk\, we will argue that any nontrivi
al property of the\ndynamics of a given AN is computationally hard. This
parallels\nthe Rice theorem\, which states that any nontrivial property of
the\nfunction computed by a given Turing machine is undecidable.\n\nFirst
\, we will spend some time to define ANs and to precisely\nstate the theor
em. Then\, we will see some insights from the proof\nthat may be reused f
or other results\, maybe with other\ncomputational models. Finally\, we w
ill give a glimpse of the\nfuture\, discussing other related results that
are currently in\npreparation.\n
LOCATION:room LIX\, room Henri Poincaré
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nguyễn Kim Thắng / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200206T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200206T153000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.863949087128
DESCRIPTION:Nguyễn Kim Thắng: Online Non-monotone Submodular Maximizat
ion: Approximation and Regret Guarantees\n\nSubmodular and diminishing-ret
urns (DR) submodular optimization\nare important optimization problems wit
h many real-world\napplications in machine learning\, economics and commun
ication\nsystems. Moreover\, DR-submodular optimization captures a subclas
s\nof non-convex optimization that provides both practical and\ntheoretica
l guarantees.\n\nIn this talk\, we present algorithms with performance gua
rantees\nfor the fundamental problems of maximizing non-monotone\nsubmodul
ar and DR-submodular functions over convex sets in the\nonline environment
. In several settings\, these guarantees match\nthe currently best-known o
nes in the offline environment.\n
LOCATION:room LIX\, room Grace Hopper
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Olivier Bournez / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191114T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191114T153000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.0389024950669
DESCRIPTION:Olivier Bournez: Calcul analogique/ Analog computations / Comp
uting with proteins or with ordinary differential equations.\n\nIt turns o
ut that if you just know what 0\, 1\, -1 are\, as well as\nan addition\, a
nd a multiplication\, and if you remember what an\nordinary differential e
quation are\, then you can (re-)define\,\n(re-)discover and program many c
oncepts from Mathematics and\nComputer Science. An even explain many conce
pts in a very\nsimple(r) way to your kids\, colleagues\, and even grandmot
her.\n\nIn particular\, you can present/rediscover descriptive\ncomplexity
\, computability and complexity using polynomial\nordinary differential eq
uations only.\n\nA title for this talk could also be "Programing with Ordi
nary\nDifferential Equations”\, as these questions also relate to\nanalo
g models of computations\, and in particular to the 1941\nGeneral Purpose
Analog Computer of Claude Shannon\, and to the\nmachines at the time of yo
ur grandmother\, and the forgotten art\nof their programming. \n\nThis als
o relates to today’s and futuristic computation models\n with molecules/
proteins\, such as the one that was awarded the\n “Prix du journal La Re
cherche 2019”.\n\n Teaser/Divulgâchage:\n https://www.lemonde.fr/blog/b
inaire/2019/02/15/la-revanche-du-calcul-analogique/\n
LOCATION:room IBISC\, petit amphi\, bâtiment IBGBI\, 23 boulevard de Fran
ce\, Evry
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Nathalie Aubrun / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190927T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190927T153000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.145975097848
DESCRIPTION:Nathalie Aubrun: The Domino Problem is undecidable on surface
groups.\n\nThe domino problem for a finitely generated group asks whether\
nthere exists an algorithm which takes as input a finite alphabet\nand fin
itely many Wang tiles\, and decides whether there exists a\ntiling of the
group by this set of tiles. I will survey known\nresults and present the d
omino problem conjecture: finitely\ngenerated groups with decidable domino
problem are exactly\nvirtually free groups. Then I will explain why this
problem is\nundecidable on surface groups. Joint work with Sebastián Barb
ieri\nand Etienne Moutot.\n
LOCATION:room LRI\, salle 445
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
BEGIN:VEVENT
SUMMARY:Yannis Manoussakis / Algorithms of Saclay Plateau seminar
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191017T143000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191017T153000
DTSTAMP;VALUE=DATE-TIME:20230628T073917Z
UID:0.578799934156
DESCRIPTION:Yannis Manoussakis: Matchings and related structures with Spec
ified \nColor Properties In Vertex- or Edge-colored Graphs.\n\n\nWe consid
er problems in edge- or vertex colored graphs. As an\nexample\, the Web g
raph may be considered as a vertex-colored graph\nwhere the color of a ver
tex represents the content of the\ncorresponding page (red for mathematics
\, yellow for physics\,\netc.). When the edges/vertices of graphs are colo
red\, then we talk\nabout c-edge/vertex colored graphs (c is the number of
colors)\,\nmodels which in fact generalize various classes of graphs. In\
ngeneral\, one can observe that problems related to colored graphs\noften
consist in finding subgraphs such as paths\, cycles\,\nmatchings and trees
\, with\, in addition\, specified constraints on\ncolors.\n\nIn the case o
f c-edge-colored graphs\, original problems correspond\nto extracting subg
raphs\, for example\, Hamiltonian and Eulerian\npaths or cycles\, trees\,
matchings etc.\, colored in some specified\npattern. Here we survey a ser
ies of results concerning colored\nmatchings in c-colored graphs\, for arb
itrarily c.\n\nIn the case of vertex-colored graphs\, we deal with tropica
l\nsubgraphs\, a concept with direct applications to the web graph and\nin
bioinformatics. More precisely\, given a vertex-colored graph\, a\ntropic
al subgraph (induced or otherwise) is defined to be a\nsubgraph where each
color of the initial graph appears at least\nonce. Notice that in a tropi
cal subgraph\, adjacent vertices can\nreceive the same color\, thus a trop
ical subgraph may not be\nproperly colored. Potentially\, many graph invar
iants\, such as the\ndomination number\, the vertex cover number\, maximum
matchings\,\nindependent sets\, connected components\, shortest paths\, e
tc. can\nbe studied in their tropical version. This notion is close to\, b
ut\nsomewhat different from the colorful (or rainbow) concept (all\ncolors
of the subgraph are different) used for paths and elsewhere\nin vertex/ed
ge-colored graphs. It is also related to the concepts\nof color patterns (
the subgraph has fixed color patterns) used in\nbio-informatics. Here we
explain some results on our ongoing work\non colored matchings\, tropical
paths and tropical connected\nsubgraphs.\n
LOCATION:room LRI\, salle 445
ORGANIZER:MAILTO:olivier.bournez@lix.polytechnique.fr
END:VEVENT
END:VCALENDAR