BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Google Inc//Google Calendar 70.9054//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
DESCRIPTION:Systèmes complexes seminar of IRIF
NAME:Systèmes complexes
REFRESH-INTERVAL:PT4H
TIMEZONE-ID:Europe/Paris
X-WR-CALDESC:Systèmes complexes seminar of IRIF
X-WR-CALNAME:Systèmes complexes
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:Online k-compaction - Claire Mathieu\, DI - ENS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171017T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171017T150000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:324
DESCRIPTION:Given\, at each time t = 1\, 2\, …\, n\, a new file of lengt
h l(t) and a read rate r(t)\, an\nonline k-compaction algorithm must maint
ain a collection of at most k files\, choosing (at each time t\, without k
nowing future inputs) some of the files to merge into one\, thereby incurr
ing a merge cost equal to the total length of the merged files and a read
cost equal to the read rate r(t) times the number of files present at time
t. The goal is to minimize the total cost over time. K-compaction algorit
hms are a key component of log-structured merge trees\, the file-based dat
a structure underlying NoSQL databases such as Accumulo\, Bigtable\, Cassa
ndra\, HBase\,and others. We initiate the theoretical study of k-compactio
n algorithms. We formalize the problem\, consider worst-case\, average-cas
e and competitive analysis (per-instance optimality)\, and propose new alg
orithms that are optimal according to these metrics. \n\nThis is joint wor
k with Carl Staelin\, Neal E. Young\, and Arman Yousefi.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Rapid Mixing of Local Graph Dynamics - Laurent Massoulié\, MSR-In
ria
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171114T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171114T150000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:342
DESCRIPTION:Graph dynamics arise naturally in many contexts. For instance
in \npeer-to-peer networks\, a participating peer may replace an existing
\nconnection with one neighbour by a new connection with a neighbour's \nn
eighbour. Several such local rewiring rules have been proposed to ensure \
nthat peer-to-peer networks achieve good connectivity properties (e.g. hig
h \nexpansion) in equilibrium. However it has remained an open question wh
ether \nthere existed such rules that also led to fast convergence to equi
librium.\nIn this work we provide an affirmative answer: We exhibit a loca
l rewiring \nrule that converges to equilibrium after each participating n
ode has \nundergone only a number of rewirings that is poly-logarithmic in
the system \nsize. The proof involves consideration of the whole isoperim
etric profile of \nthe graph\, and may be of independent interest.\n\nThis
is joint work with Rémi Varloot.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Incremental Update for Graph Rewriting - Jean Krivine\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20171212T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20171212T150000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:419
DESCRIPTION:Graph rewriting formalisms are well-established models for the
representation of biological systems such as protein-protein interaction
networks. The combinatorial complexity of these models usually prevents an
y explicit representation of the variables of the system\, and one has to
rely on stochastic simulations in order to sample the possible trajectorie
s of the underlying Markov chain. The bottleneck of stochastic simulation
algorithms is the update of the propensity function that describes the pro
bability that a given rule is to be applied next. In this talk we present
an algorithm based on a data structure\, called extension basis\, that can
be used to update the counts of predefined graph observables after a rule
of the model has been applied. \n\nReference: Boutillier P.\, Ehrhard T.\
, Krivine J. (2017) Incremental Update for Graph Rewriting. In: Yang H. (e
ds) Programming Languages and Systems. ESOP 2017. Lecture Notes in Compute
r Science\, vol 10201. Springer\, Berlin\, Heidelberg
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Computing huge subspaces of diagonal harmonic polynomials: symmetr
ies to the rescue! - Nicolas Thiery\, Université Paris Sud
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180116T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180116T150000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:505
DESCRIPTION:Last spring\, I visited François Bergeron and we worked on hi
s favorite objects: the spaces H(n\,k) of diagonal harmonic polynomials in
k sets of n variables. Those spaces connect to many areas of algebraic co
mbinatorics\, representation theory and beyond\, and the case H(n\,2) beca
me famous a decade ago with the n! conjecture and its proof by Haiman.\n\n
To fuel his ongoing studies François needed to compute the structure of H
(5\,6). This is a space of dimension 6.10^5 made of polynomials in 30 vari
ables of degree up to 15\, each having thousands of terms.\n\nIn this talk
\, I'll explain how the calculation can now be completed in 45 minutes wit
h a dozen cores and ~15Go of memory. This exploits a combination of strate
gies (symmetries\, representation theory of the symmetric and general line
ar group\, ...)\, each of which reduces the complexity in time and memory
by one or two orders of magnitude.\n\nThere will be little prerequisites a
nd it's my hope that some strategies (and maybe the code!) could be used i
n other contexts.
LOCATION:Salle 3014
END:VEVENT
BEGIN:VEVENT
SUMMARY:Combinatorics of stochastic rewriting systems - Nicolas Behr\, ENS
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180213T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180213T150000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:506
DESCRIPTION:Based on recent joint work with G.H.E. Duchamp and K.A. Penson
(arXiv:1712.06575\, on the combinatorics of chemical reaction systems) an
d with V. Danos and I. Garnier (in preparation)\, I will explain how dynam
ical and statistical aspects of stochastic graph rewriting systems may be
computed using combinatorial techniques. The main part of the talk will fo
cus on the special case of discrete graph rewriting (i.e. chemical reactio
ns) for clarity and brevity\, but time permitting the generalization to ge
neric graph rewriting in the form of a stochastic mechanics formalism base
d on the concept of rule algebras will be discussed as well.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Fully Dynamic k-center Clustering and Graph Partitioning - Mauro S
ozio\, Telecom Paristech
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180502T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180502T150000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:549
DESCRIPTION:Recently\, we have witnessed an explosion in the amount of dat
a being readily available to us. This allows us to study and understand th
e world we live in with unprecedented details. However\, the challenges of
processing large amounts of data evolving over time are non-trivial. Our
talk will start with discussing a few recent results in large-scale graph
mining. In particular\, we will briefly discuss the main ideas which allow
ed us to find dense subgraphs in graphs containing up to 20 billion edges.
We will then continue our talk presenting a fully dynamic algorithm for k
-center clustering\, which is the problem of finding a partition of the in
put data points into k sets with minimum maximum radius. Most of the effor
ts in developing dynamic data mining algorithms have been focusing on the
sliding window model (where at any given point in time only the most recen
t data items are retained) or more simplistic models. However\, in many re
al-world applications one might need to deal with arbitrary deletions and
insertions. For example\, one might need to remove data items that are not
necessarily the oldest ones\, because they have been flagged as containin
g inappropriate content or due to privacy concerns. Clustering trajectory
data might also require to deal with more general update operations.\n\nWe
develop a (2+epsilon)-approximation algorithm for the k-center clustering
problem with "small" amortized cost under the fully dynamic adversarial m
odel. In such a model\, points can be added or removed arbitrarily\, provi
ded that the adversary does not have access to the random choices of our a
lgorithm. The amortized cost of our algorithm is poly-logarithmic when the
ratio between the maximum and minimum distance between any two points in
input is bounded by a polynomial\, while k and epsilon are constant. Our t
heoretical results are complemented with an extensive experimental evaluat
ion on dynamic data from Twitter\, Flickr\, as well as trajectory data\, d
emonstrating the effectiveness of our approach. We conclude our talk with
some interesting directions for future work. In particular\, we are going
to discuss the challenges in developing a fully dynamic algorithm for grap
h partitioning.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Searching in the presence of errors\, revisited - Przemyslaw Uznan
ski\, ETH Zurich
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180322T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180322T150000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:566
DESCRIPTION:In searching with errors\, the Questioner has to locate a targ
et among $n$ objects\, by repeatedly asking queries to Responder. The poss
ible queries are limited by the structure of the searched space\, and depe
nding on the error model\, the answers are subject to either adversarial l
ies (bound in absolute number\, or bound in rate $r \\in [0\,1]$)\, or to
probabilistic errors with rate $p \\in [0\,1]$. Our interest lies in dista
nce-based searching in graphs and in comparison based searching of integer
ranges. \n\nIn graph searching with vertex queries\, whenever Questioner
queries a vertex $v$\, Responder answers with neighbor $w$ of $v$ that lie
s on the shortest path from $v$ to target or with $v$ itself (as introduce
d by Emamjomeh-Zadeh et al. [STOC 2016]). We show that a simple strategy o
f querying weighted-1-median vertex and multiplicatively updating weights
of vertices leads to $O(\\log n + L)$ queries with fixed $L$ lies\, genera
lizing results of Emamjomeh-Zadeh et al. By careful selection of potenti
al this leads to $O(\\log n / \\varepsilon^2)$ queries when number of lies
is bounded linearly by ratio $r = 1/2-\\varepsilon$\, or are subject to e
rrors with probability $p = 1/2-\\varepsilon$ (in that case target is loca
ted correctly w.h.p.). This improves result of Emamjomeh-Zadeh et al. for
some selection of parameters (locating w.h.p. when $\\varepsilon = \\Omega
(1/\\sqrt{\\log n})$\, and generalizes their result to other error models.
\n\nWe introduce an edge queries model\, in which\, whenever Questioner q
ueries an edge $e$\, Responder answers with endpoint of $e$ that is not fu
rther to target. We show that appropriately defining weighted-1-median edg
e leads to $O(\\Delta(\\log n + L))$ length strategy in graphs of max degr
ee $\\Delta$\, which leads to $O(\\Delta \\log n / \\varepsilon^2)$ querie
s when lies are bounded linearly with rate $r = \\frac{1}{\\Delta+1}(1-\\v
arepsilon)$ and $O(\\Delta \\log^2 n/\\varepsilon^2)$ with error probabili
ty $p = 1/2-\\varepsilon$.\n\nOur results for edge queries almost automati
cally apply to comparison based search of integer ranges\, simplifying and
improving many existing results. We also note that vertex based queries t
ranslate to (not considered previously to our knowledge) ternary compariso
ns\, and this shows a separation between power of binary and ternary compa
risons in the linearly bounded lies (Questioner can find target iff $r < \
\frac13$ for former case\, $r < \\frac12$ for latter case).\n\nTweaking in
itial distribution of potentials\, our results apply to searching in unbou
nded integer domains as well\, leading to both simplification and signific
ant improvement in length of strategies\, and providing first results for
many combinations of query model and error model.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Computing node centrality in large graphs: from theory to practice
and back - Pierluigi Crescenzi\, Universite de Pise
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180320T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180320T150000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:567
DESCRIPTION:The computation of several graph measures\, based on the dista
nce between nodes\, is very often part of the analysis of real-world compl
ex networks. The diameter\, the betweenness and the closeness centrality\,
and the hyperbolicity are typical examples of such measures. In this talk
\, we will focus on the computation of one specific measure\, that is\, th
e node closeness centrality which is basically the inverse of the average
distance of a node from all other nodes of the graph. Even though polynomi
al-time algorithms are available for the computation of this measure\, in
practice these algorithms are not useful\, due to the huge size of the net
works to be analysed. One first theoretical question is\, hence\, whether
better algorithms can be designed\, whose worst-case complexity is (almost
) linear in the size of the input graph. We will first show that\, unfortu
nately\, for the closeness centrality no such algorithm exists (under reas
onable complexity theory assumptions). This will lead us back to the pract
ical point of view: we will then describe a heuristics that allows us to c
ompute the above measure in (practical) linear time\, even though its wors
t-case complexity is (in practice) intractable. This result will finally m
otivate our return to theory in order to understand the reason why\, in pr
actice\, this heuristics works so well: we will indeed conclude by showing
that\, in the case of several random graph generating models\, the averag
e time complexity of the heuristics is indeed (almost) linear. This talk w
ill summarise the research work that I have done in collaboration with Eli
sabetta Bergamini\, Michele Borassi\, Michel Habib\, Andrea Marino\, Henni
ng Meyerhenke\, and Luca Trevisan\, and will be mostly based on two papers
presented at ALENEX 2016\, and SODA 2017.
LOCATION:Salle 1007
END:VEVENT
BEGIN:VEVENT
SUMMARY:Pooling or Sampling: Collective Dynamics for Electrical Flow Estim
ation - Emanuele Natale\, Max-Planck-Institut für Informatik
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180504T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180504T120000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:590
DESCRIPTION:The computation of electrical flows is a crucial primitive for
many recently proposed optimization algorithms on weighted networks. Whil
e typically implemented as a centralized subroutine\, the ability to perfo
rm this task in a fully decentralized way is implicit in a number of biolo
gical systems. Thus\, a natural question is whether this task can provably
be accomplished in an efficient way by a network of agents executing a si
mple protocol.\nWe provide a positive answer\, proposing two distributed a
pproaches to electrical flow computation on a weighted network: a determin
istic process mimicking Jacobi's iterative method for solving linear syste
ms\, and a randomized token diffusion process\, based on revisiting a clas
sical random walk process on a graph with an absorbing node. We show that
both processes converge to a solution of Kirchhoff's node potential equati
ons\, derive bounds on their convergence rates in terms of the weights of
the network\, and analyze their time and message complexity.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Introduction to the blockchain - Laurent Viennot\, Inria Paris et
IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180705T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180705T150000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:623
DESCRIPTION:The collaborative construction of a blockchain is the core of
Bitcoin protocol for allowing various participants to agree on a list of v
alid transactions. The talk will be very informal\, the intent is to give
a very basic introduction on how Bitcoin works and highlight some of the s
cientific challenges behind it.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Human-Computable Passwords - Nicolas K. Blanchard\, IRIF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20180710T150000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20180710T160000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:632
DESCRIPTION:Despite 25+ years of online experience and many innovations\,
passwords are still central to security\, with all the risks and frustrati
on they imply. Neither biometrics\, nor password managers\, nor systems li
ke facebook connect can guarantee the security we require\, and rememberin
g dozens of different passwords becomes a usability nightmare.\n\nFollowin
g in the footsteps of Manuel Blum et al. we recently proposed a humanly-co
mputable password scheme called Cue-Pin-Select. It can generate (and regen
erate) passwords on the go using only the user's brain for computation. It
has the advantage of creating nigh-unforgettable passwords\, not requirin
g any external storage or computing device\, and can be executed in less t
han a minute to create a new password (potentially down to 30s with a bit
of training). All passwords generated are 52-bit secure and can maintain 4
0+ bit security even against adversaries in possession of a stolen passwor
d\n\nThis talk will summarize work done in the past 6 months with Ted Selk
er and doesn't require any prior knowledge. It will start with the Cue-Pin
-Select algorithm\, cover an improvement we found that applies to all pass
phrase-based security systems\, and explain some of the work currently bei
ng done to have better tools to study password schemes and human computati
on. \n\nThe talk will be given in English unless the audience is entirely
composed of French-speakers.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Stable Outcomes in Modified Fractional Hedonic Games - Yllka Velaj
\, CWI Amsterdam
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20181023T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20181023T150000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:690
DESCRIPTION:In coalition formation games\, self-organized coalitions are c
reated as a result of the strategic interactions of independent agents. Fo
r each couple of agents $(i\,j)$\, weight $w_{i\,j}=w_{j\,i}$ reflects how
much agents $i$ and $j$ benefit from belonging to the same coalition. We
consider the modified fractional hedonic game\, that is a coalition format
ion game in which agents' utilities are such that the total benefit of age
nt $i$ belonging to a coalition (given by the sum of $w_{i\,j}$ over all o
ther agents $j$ belonging to the same coalition) is averaged over all the
other members of that coalition\, i.e.\, excluding herself. Modified fract
ional hedonic games constitute a class of succinctly representable hedonic
games.\n\nWe are interested in the scenario in which agents\, individuall
y or jointly\, choose to form a new coalition or to join an existing one\,
until a stable outcome is reached. To this aim\, we consider common stabi
lity notions\, leading to strong Nash stable outcomes\, Nash stable outcom
es or core stable outcomes: we study their existence\, complexity and perf
ormance\, both in the case of general weights and in the case of 0-1 weigh
ts.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Computing Giant Diameters with Breadth-First Search and Range Quer
ies - Guillaume Ducoffe\, ICI Roumanie
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190122T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190122T150000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:754
DESCRIPTION:A well-known problem for which it is difficult to improve the
textbook algorithm is computing the graph diameter. We present two version
s of a simple algorithm (one being Monte Carlo and the other deterministic
) that for every fixed $h$ and unweighted undirected graph $G$ with $n$ ve
rtices and $m$ edges\, either correctly concludes that $diam(G) < hn$ or o
utputs $diam(G)$\, in time ${\\cal O}(m+n^{1+o(1)})$. The algorithm combin
es a simple randomized strategy for this problem (Damaschke\, {\\it IWOCA'
16}) with a popular framework for computing graph distances that is based
on range trees (Cabello and Knauer\, {\\it Computational Geometry'09}). We
also prove that under the Strong Exponential Time Hypothesis (SETH)\, we
cannot compute the diameter of a given $n$-vertex graph in truly subquadra
tic time\, even if the diameter is an $\\Theta(n/\\log{n})$.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Spectral embedding for graph classification - Marc Lelarge\, Inria
& ENS Paris
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190306T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190306T120000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:774
DESCRIPTION:Learning on graphs requires a graph feature representation abl
e to discriminate among different graphs while being amenable to fast comp
utation. The graph isomorphism problem tells us that no fast representatio
n of graphs is known if we require the representation to be both invariant
to nodes permutation and able to discriminate two non-isomorphic graphs.
Most graph representations explored so far require to be invariant. We exp
lore new graph representations by relaxing this constraint. We present a g
eneric embedding of graphs relying on spectral graph theory called Spectra
l Graph Embedding (SGE). We show that for a large family of graphs\, our e
mbedding is still invariant. To evaluate the quality and utility of our SG
E\, we apply them to the graph classification problem. Through extensive e
xperiments\, we show that a simple Random Forest based classification algo
rithm driven with our SGE reaches the state-of-the-art methods.\n\nAlthoug
h our SGE is handcrafted\, we also show how our generic embedding techniqu
e can be learned and built in a data-driven manner opening the way to new
learning algorithms and deep learning architectures with some invariant co
nstraints built-in.
LOCATION:Salle 3052
END:VEVENT
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:20200919T020302Z
UID:805
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. Most recent works that this talk is based on
are with Sebastian Krinninger (FOCS 2018) and Aaron Bernstein (ArXiv 2018
).\nGraphes
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Distributed Reconfiguration of Graph Problems - Mikaël Rabie\, IR
IF
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190305T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190305T150000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:814
DESCRIPTION:In Graph Theory\, a reconfiguration problem is as following:\n
given two solutions of a problem and a transition definition\, is there a
path of acceptable solutions from the first to the second using a transiti
on one after another? What is the length of the shortest reconfiguration p
ath? What complexities are involved? \n\nFor example\, a recoloration prob
lem asks if we can go from a coloration to another\, by changing the color
of a node at each transition (with the coloring still valid in the interm
ediate steps).\n\nIn this talk\, the goal is to consider distributed versi
on of two reconfiguration problems: recoloring\, and reconfiguring indepen
dent sets. To parallelise the process\, we will accept to change the state
of different nodes at once\, under certain hypothesis (for example\, we w
ill recolor an independent set of nodes). The questions will be\, using th
e LOCAL model\, how much communication is needed (i.e. how much a node nee
ds knowledge of its neighborhood) in order to produce a reconfiguration sc
hedule of a given length.\n\nFor the distributed recoloring\, we prove tha
t the addition of colors for the intermediate steps is needed for some cas
es in order to have a solution. I will provide the analysis of trees and t
oroidal grids\, where we want to go from a 3-coloring to another with the
use of a 4th color. In the case of trees\, a constant schedule can be foun
d after O(log n) communications. In the case of grids\, a linear number of
communications is necessary.\n\nFor the reconfiguration of independent se
ts\, we will present different transitions from the centralized settings\,
to then justify the one we use. We prove that a constant schedule can be
found after O(log*n) communications\, and a linear schedule can be found a
fter a constant number of communications.\n\nThose works are the result of
collaborations with Marthe Bonamy\, Keren Censor-Hillel\, Paul Ouvrard\,
Jara Uitto and Jukka Suomela
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Contention-related crash failures - Anaïs Durand\, LIP6\, Sorbonn
e Université
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190326T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190326T150000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:825
DESCRIPTION:In the literature\, two kinds of process crashes are usually c
onsidered: initially dead processes and "classical" crash failures (that c
an occur at any time). A new notion of process failure explicitly related
to contention has recently been introduced by Gadi Taubenfeld (NETYS 2018)
. More precisely\, given a predefined contention threshold λ\, this notio
n considers the execution in which process crashes are restricted to occur
only when process contention is smaller than or equal to λ. If crashes o
ccur after contention bypassed λ\, there are no correctness guarantees. I
t was shown that\, when λ = n-1\, consensus can be solved in an n-process
asynchronous read/write system despite the crash of one process\, thereby
circumventing the well-known FLP impossibility result.\n\nIn this talk\,
I will present k-set agreement and renaming algorithms that are resilient
to two types of process crash failures: "λ-constrained" crash failures (a
s previously defined) and classical crash failures.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Evolutionary Algorithms -- From Theory to Practice and Back - Caro
la Doerr\, CNRS\, LIP6 Sorbonne University
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20190624T110000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20190624T120000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:893
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.\n\nIn the last 15 years\, the theory of randomized black-box optimizati
on has advanced considerably\, and has contributed to efficient optimizati
on by providing insights into the working principles of black-box optimiza
tion which are hard or impossible to obtain by empirical means. On the oth
er hand\, empirically-guided benchmarking has opened up new research direc
tions for theoretical investigations.\n\nIn this presentation we will disc
uss the state of the art in the theory of randomized black-box optimizatio
n algorithms. As part of this critical survey we will also mention a numbe
r of open questions and connections to other fields of Computer Science.
LOCATION:Salle 3052
END:VEVENT
BEGIN:VEVENT
SUMMARY:Lower bounds for maximal matchings and maximal independent sets -
Mikaël Rabie\, LIP6\, Sorbonne Université
DTSTART;TZID=Europe/Paris;VALUE=DATE-TIME:20200604T140000
DTEND;TZID=Europe/Paris;VALUE=DATE-TIME:20200604T150000
DTSTAMP;VALUE=DATE-TIME:20200919T020302Z
UID:1165
DESCRIPTION:There are distributed graph algorithms for finding maximal mat
chings and maximal independent sets in O(Delta+log^*n) communication round
s\; here n is the number of nodes and Delta is the maximum degree. The low
er bound by Linial (1987\, 1992) shows that the dependency on n is optimal
: these problems cannot be solved in o(log^*n) rounds even if Delta=2. How
ever\, the dependency on Delta is a long-standing open question\, and ther
e is currently an exponential gap between the upper and lower bounds. We p
rove that the upper bounds are tight. In this presentation\, I will first
provide previous results on the bounds depending on n\, before providing t
he tools and ideas we used for the case of Delta dependency. This is a joi
nt work with Alkida Balliu\, Sebastian Brandt\, Juho Hirvonen\, Dennis Oli
vetti\, and Jukka Suomela. These results got the Best Paper award at FOCS
2019.
LOCATION:Online
END:VEVENT
END:VCALENDAR