BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Google Inc//Google Calendar 70.9054//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
DESCRIPTION:Algorithmes et structures discrètes seminar of IRIF
NAME:Algorithmes et structures discrètes
REFRESH-INTERVAL:PT4H
TIMEZONE-ID:Europe/Paris
X-WR-CALDESC:Algorithmes et structures discrètes seminar of IRIF
X-WR-CALNAME:Algorithmes et structures discrètes
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
SUMMARY:Distributed Shortest Paths\, Exactly - Danupon Nanongkai\, KTH
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190219T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190219T120000
DTSTAMP;VALUE=DATE-TIME:20201026T210301Z
UID:934
DESCRIPTION: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 ca
n perform equally well. In this talk\, we will discuss some recent progres
s in answering this question. \nMost recent works that this talk is base
d on are with Sebastian Krinninger (FOCS 2018) and Aaron Bernstein (ArXiv
2018).
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Statistical mechanics on isoradial graphs - Cédric Boutillier\, L
PSM\, Sorbonne Université
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181203T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181203T120000
DTSTAMP;VALUE=DATE-TIME:20201026T210301Z
UID:935
DESCRIPTION:Isoradial graphs are embedded planar graphs in such a way that
every\nface is inscribed in a circle of radius 1. They are a perfect grou
nd\nto develop a theory of discrete complex analysis and to define\nintegr
able models in statistical mechanics.\nIn this talk\, we will describe com
binatorial and geometric aspects of\nthese graphs\, and their impact on lo
cality of some models of statistical\nmechanics (dimer models\, random wal
k\, spanning trees…)
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Evolutionary Algorithms -- From Theory to Practice and Back - Caro
la Doerr\, CNRS\, LIP6
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190624T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190624T120000
DTSTAMP;VALUE=DATE-TIME:20201026T210301Z
UID:936
DESCRIPTION:Most real-world optimization problems do not have an explicit
problem formulation\, but only allow to compute the quality of selected so
lution candidates. Solving such black-box optimization problems requires i
terative procedures which use the feedback gained from previous evaluation
s to determine the strategy by which the next solution candidates are gene
rated. Many black-box optimization algorithms\, such as Simulated Annealin
g\, Evolutionary Algorithms\, Swarm Intelligence Algorithms\, are randomiz
ed -- making it very difficult to analyze their performances mathematicall
y. \nIn the last 15 years\, the theory of randomized black-box optimizatio
n has advanced considerably\, and has contributed to efficient optimizatio
n by providing insights into the working principles of black-box optimizat
ion which are hard or impossible to obtain by empirical means. On the othe
r hand\, empirically-guided benchmarking has opened up new research direct
ions for theoretical investigations. \nIn this presentation we will discus
s 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.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Graph query languages - Amélie Gheerbrant\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190509T150000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190509T160000
DTSTAMP;VALUE=DATE-TIME:20201026T210301Z
UID:937
DESCRIPTION:Graph databases use graph structure to represent and query dat
a. The talk will survey some graph query languages used in this context\,
with a focus on regular path queries (RPQs) and conjunctive regular path q
ueries (CRPQs). We will present the different semantics that graph databas
e systems use for them (every path\, simple path\, trail)\, and recall com
putational 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 gro
up.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:The sensitivity conjecture and a recent proof of it (part I) - Sop
hie Laplante\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190926T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190926T150000
DTSTAMP;VALUE=DATE-TIME:20201026T210301Z
UID:941
DESCRIPTION:Informal presentation.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:The sensitivity conjecture and a recent proof of it (part II) - So
phie Laplante\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20191002T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20191002T120000
DTSTAMP;VALUE=DATE-TIME:20201026T210301Z
UID:950
DESCRIPTION:Informal presentation.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Instance Complexity and Unlabeled Certificates in the Decision Tre
e Model - Moni Naor\, Weizmann Institute
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200123T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200123T120000
DTSTAMP;VALUE=DATE-TIME:20201026T210301Z
UID:1055
DESCRIPTION:Suppose that you want to check whether a graph satisfies some
(graph) property. The goal is to minimize the number of queries to the adj
acency 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?\n \nIn this talk I will discuss la
beled and unlabeled certificates\, in particular in the context of ``insta
nce optimality". This is a measure of goodness of an algorithm in which th
e performance of one algorithm is compared to others per input. This is in
sharp contrast to worst-case and average-case complexity measures\,\nwher
e the performance is compared either on the worst input or on an average o
ne\, respectively. \n \nJoint work with Tomer Grossman and Ilan Komargodsk
i
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Continuous models of computation: computability\, complexity\, uni
versality - Amaury Pouly\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200127T093000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200127T103000
DTSTAMP;VALUE=DATE-TIME:20201026T210301Z
UID:1062
DESCRIPTION:In 1941\, Claude Shannon introduced a continuous-time analog m
odel of \ncomputation\, namely the General Purpose Analog Computer (GPAC).
The\nGPAC is a physically feasible model in the sense that it can be\nimp
lemented in practice through the use of analog electronics or\nmechanical
devices. It can be proved that the functions computed by a \nGPAC are prec
isely the solutions of a special class of differential\nequations where th
e right-hand side is a polynomial. Analog computers\nhave since been repl
aced by digital counterpart. Nevertheless\, one can\nwonder how the GPAC c
ould be compared to Turing \nmachines.\n\nA few years ago\, it was shown t
hat Turing-based paradigms and\nthe GPAC have the same computational power
. However\, this result did\nnot shed any light on what happens at a comp
utational complexity\nlevel. In other words\, analog computers do not make
a difference about\nwhat can be computed\; but maybe they could compute f
aster than a\ndigital computer. A fundamental difficulty of continuous-tim
e model is\nto define a proper notion of complexity. Indeed\, a troubling
problem is\nthat many models exhibit the so-called Zeno's phenomenon\, als
o known as\nspace-time contraction.\n\nIn this talk\, I will present resul
ts from my thesis that give several \nfundamental contributions to these q
uestions. We show that the GPAC has\nthe same computational power as the T
uring machine\, at the complexity\nlevel. We also provide as a side effect
a purely analog\, machine-\nindependent characterization of P and Computa
ble Analysis.\n\nI will present some recent work on the universality of po
lynomial\ndifferential equations. We show that when we impose no restricti
ons at\nall on the system\, it is possible to build a fixed equation that\
nis universal in the sense it can approximate arbitrarily well any \nconti
nuous curve over R\, simply by changing the initial condition of\nthe syst
em.\n\nIf time allows\, I will also mention some recent application of thi
s\nwork to show that chemical reaction networks are strongly Turing\ncompl
ete with the differential semantics.
LOCATION:3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Twin-width - Édouard Bonnet\, ENS Lyon
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200526T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200526T120000
DTSTAMP;VALUE=DATE-TIME:20201026T210301Z
UID:1158
DESCRIPTION: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 pr
oper 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 checki
ng\, 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 algorith
m runs in time $f(d\,|\\phi|) |D|$ where f is a computable but non-element
ary 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 Ga
jarsky et al. [FOCS '15]. Finally we mention a curious connection between
bounded twin-width and small classes.\n\nJoint work with Colin Geniet\, Eu
n Jung Kim\, Stéphan Thomassé\, and Rémi Watrigant
LOCATION:Online
END:VEVENT
END:VCALENDAR