BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
BEGIN:VEVENT
UID:379@lincs.fr
DTSTART;TZID=Europe/Paris:20180514T100000
DTEND;TZID=Europe/Paris:20180514T103000
DTSTAMP:20180515T055809Z
URL:https://www.lincs.fr/events/on-the-performance-of-a-canonical-labeling
 -for-matching-correlated-erdos-renyi-graphs/
SUMMARY:On the Performance of a Canonical Labeling for Matching Correlated
 Erdos-Renyi Graphs
DESCRIPTION:Recent results have characterized the exact
 information-theoretic threshold for graph matching in correlated
 Erd?s-Rényi graphs. However\, very little is known about the existence of
 efficient algorithm to achieve graph matching without seeds. In this work\,
 we identify a region in which a straightforward and efficient canonical
 labeling algorithm\, initially introduced in the context of graph
 isomorphism\, succeeds in matching correlated Erd?s-Rényi graphs. The
 algorithm has two steps. In the first step\, all vertices are labeled by
 their degrees and a trivial minimum distance matching (i.e.\, simply
 sorting vertices according to their degrees) matches the a fixed number of
 highest degree vertices in the two graphs. Having identified this subset of
 vertices\, the remaining vertices are matched using a noisy variant of a
 bipartite matching algorithm.\n\nJoint work with Osman Dai\, Daniel Cullina
 and Negar Kiyavash
CATEGORIES:Seminars,Youtube
LOCATION:LINCS / EIT Digital\, 23 avenue d'Italie\, 75013 Paris\, France
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=23 avenue d'Italie\, 75013
 Paris\, France;X-APPLE-RADIUS=100;X-TITLE=LINCS / EIT Digital:geo:0,0
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20180325T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR