CINXE.COM

<!DOCTYPE html> <html xmlns="http://www.w3.org/1999/xhtml" lang="en" dir="ltr" class="no-js"> <head> <meta charset="UTF-8" /> <title>Algorithms and discrete structures</title>  <script> var _paq = window._paq = window._paq || []; /* tracker methods like "setCustomDimension" should be called before "trackPageView" */ _paq.push(['trackPageView']); _paq.push(['enableLinkTracking']); (function() { var u="//apps.roulois.fr/matomo/"; _paq.push(['setTrackerUrl', u+'matomo.php']); _paq.push(['setSiteId', '1']); var d=document, g=d.createElement('script'), s=d.getElementsByTagName('script')[0]; g.async=true; g.src=u+'matomo.js'; s.parentNode.insertBefore(g,s); })(); </script>  <script>(function(H){H.className=H.className.replace(/\bno-js\b/,'js')})(document.documentElement)</script> <meta name="viewport" content="width=device-width,initial-scale=1" /> <link rel="shortcut icon" href="https://www.irif.fr/_media/favicon.ico" /> <link rel="apple-touch-icon" href="https://www.irif.fr/_media/apple-touch-icon.png" /> <meta name="generator" content="DokuWiki"/> <meta name="robots" content="index,follow"/> <meta name="keywords" content="en,seminaires,asd,index"/> <link rel="search" type="application/opensearchdescription+xml" href="https://www.irif.fr/lib/exe/opensearch.php" title=""/> <link rel="start" href="https://www.irif.fr/"/> <link rel="contents" href="https://www.irif.fr/en/seminaires/asd/index?do=index" title="Sitemap"/> <link rel="manifest" href="https://www.irif.fr/lib/exe/manifest.php"/> <link rel="alternate" type="text/html" title="Plain HTML" href="https://www.irif.fr/_export/xhtml/en/seminaires/asd/index"/> <link rel="alternate" type="text/plain" title="Wiki Markup" href="https://www.irif.fr/_export/raw/en/seminaires/asd/index"/> <link rel="canonical" href="https://www.irif.fr/en/seminaires/asd/index"/> <link rel="stylesheet" href="https://www.irif.fr/lib/exe/css.php?t=bootstrap3&tseed=999b1f07158911a883ed4b945a522775"/> <link type="text/css" rel="stylesheet" href="https://www.irif.fr/lib/plugins/datatables/assets/datatables.net-fixedheader-dt/css/fixedHeader.dataTables.min.css"/> <link type="text/css" rel="stylesheet" href="https://www.irif.fr/lib/plugins/datatables/assets/datatables.net-fixedcolumns-dt/css/fixedColumns.dataTables.min.css"/> <link type="text/css" rel="stylesheet" href="https://www.irif.fr/lib/plugins/datatables/assets/datatables.net/css/dataTables.bootstrap.min.css"/> <link type="text/css" rel="stylesheet" href="https://www.irif.fr/lib/plugins/datatables/assets/datatables.net-buttons/css/buttons.bootstrap.min.css"/> <link type="text/css" rel="stylesheet" href="https://www.irif.fr/lib/plugins/icons/assets/font-awesome/css/font-awesome.min.css"/> <link type="text/css" rel="stylesheet" href="https://www.irif.fr/lib/plugins/icons/assets/material-design-icons/css/materialdesignicons.min.css"/>  <script >/*<![CDATA[*/var NS='en:seminaires:asd';var JSINFO = {"plugin":{"datatables":{"config":{"dom":"lBfrtip","language":{"url":"https:\/\/www.irif.fr\/lib\/plugins\/datatables\/assets\/datatables.net-i18n\/en-GB.json"}},"enableForAllTables":1}},"move_renameokay":false,"move_allowrename":false,"bootstrap3":{"mode":"show","toc":[],"config":{"collapsibleSections":0,"fixedTopNavbar":1,"showSemanticPopup":0,"sidebarOnNavbar":1,"tagsOnTop":1,"tocAffix":1,"tocCollapseOnScroll":1,"tocCollapsed":0,"tocLayout":"default","useAnchorJS":1,"useAlternativeToolbarIcons":1}},"id":"en:seminaires:asd:index","namespace":"en:seminaires:asd","ACT":"show","useHeadingNavigation":1,"useHeadingContent":1}; /*!]]>*/</script> <script src="https://www.irif.fr/lib/exe/jquery.php?tseed=34a552433bc33cc9c3bc32527289a0b2" defer="defer"></script> <script src="https://www.irif.fr/lib/exe/js.php?t=bootstrap3&tseed=999b1f07158911a883ed4b945a522775&lang=en" defer="defer"></script> <script type="text/javascript" src="https://www.irif.fr/lib/plugins/datatables/assets/datatables.net/js/jquery.dataTables.min.js" defer="defer"></script> <script type="text/javascript" src="https://www.irif.fr/lib/plugins/datatables/assets/datatables.net-fixedheader-dt/js/fixedHeader.dataTables.min.js" defer="defer"></script> <script type="text/javascript" src="https://www.irif.fr/lib/plugins/datatables/assets/datatables.net-fixedcolumns-dt/js/fixedColumns.dataTables.min.js" defer="defer"></script> <script type="text/javascript" src="https://www.irif.fr/lib/plugins/datatables/assets/datatables.net-buttons/js/dataTables.buttons.min.js" defer="defer"></script> <script type="text/javascript" src="https://www.irif.fr/lib/plugins/datatables/assets/datatables.net-buttons/js/buttons.html5.min.js" defer="defer"></script> <script type="text/javascript" src="https://www.irif.fr/lib/plugins/datatables/assets/datatables.net-buttons/js/buttons.print.min.js" defer="defer"></script> <script type="text/javascript" src="https://www.irif.fr/lib/plugins/datatables/assets/jszip/jszip.min.js" defer="defer"></script> <script type="text/javascript" src="https://www.irif.fr/lib/plugins/datatables/assets/pdfmake/pdfmake.min.js" defer="defer"></script> <script type="text/javascript" src="https://www.irif.fr/lib/plugins/datatables/assets/pdfmake/vfs_fonts.js" defer="defer"></script> <script type="text/javascript" src="https://www.irif.fr/lib/plugins/datatables/assets/datatables.net/js/dataTables.bootstrap.min.js" defer="defer"></script> <script type="text/javascript" src="https://www.irif.fr/lib/plugins/datatables/assets/datatables.net-buttons/js/buttons.bootstrap.min.js" defer="defer"></script> <script type="text/x-mathjax-config">/*<![CDATA[*/MathJax.Hub.Config({ tex2jax: { inlineMath: [ ["$","$"], ["\$","\$"] ], displayMath: [ ["$$","$$"], ["\\[","\\]"] ], processEscapes: true } }); /*!]]>*/</script> <script type="text/javascript" charset="utf-8" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.9/MathJax.js?config=TeX-AMS_CHTML.js"></script>  <style type="text/css">@media screen { body { margin-top: 60px; } #dw__toc.affix { top: 50px; position: fixed !important; } #dw__toc .nav .nav .nav { display: none; } }</style>  </head> <body class="simplex dokuwiki mode_show tpl_bootstrap3 dw-fluid-container" data-page-id="en:seminaires:asd:index"><div class="dokuwiki"> <header id="dokuwiki__header" class="dw-container dokuwiki container-fluid mx-5">  <nav id="dw__navbar" class="navbar navbar-fixed-top navbar-inverse" role="navigation"> <div class="dw-container container-fluid mx-5"> <div class="navbar-header"> <button class="navbar-toggle" type="button" data-toggle="collapse" data-target=".navbar-collapse"> <span class="icon-bar"></span> <span class="icon-bar"></span> <span class="icon-bar"></span> </button> <a class="navbar-brand d-flex align-items-center" href="https://www.irif.fr/index" accesskey="h" title=""><img id="dw__logo" class="pull-left h-100 mr-4" alt="" src="https://www.irif.fr/_media/logo.png" /><div class="pull-right"><div id="dw__title"></div></div></a> </div> <div class="collapse navbar-collapse"> <ul class="nav navbar-nav"> <li class="level1 node dropdown"><a href="#" class="dropdown-toggle" data-target="#" data-toggle="dropdown" role="button" aria-haspopup="true" aria-expanded="false">INFORMATION <span class="caret"></span></a> <ul class="dropdown-menu" role="menu"> <li class="level2"> <a href="https://www.irif.fr/en/informations/presentation" class="wikilink1" title="en:informations:presentation" >Presentation</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/informations/contacts" class="wikilink1" title="en:informations:contacts" >Contact and access</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/informations/charte" class="wikilink1" title="en:informations:charte" >IRIF Members Charter</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/egalite-fh/index" class="wikilink1" title="en:egalite-fh:index" >Equality</a> </li> <li class="level2"> <a href="https://www.irif.fr/environnement/index" class="wikilink1" title="environnement:index" >Environment</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/informations/annuaire" class="wikilink1" title="en:informations:annuaire" >Directory</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/informations/mentorat" class="wikilink1" title="en:informations:mentorat" >IRIF’s mentoring program</a> </li> <li class="level2"> <a href="https://www.irif.fr/informations/childcare" class="wikilink1" title="informations:childcare" >Childcare program</a> </li> </ul> </li> </ul> <ul class="nav navbar-nav"> <li class="level1 node dropdown"><a href="#" class="dropdown-toggle" data-target="#" data-toggle="dropdown" role="button" aria-haspopup="true" aria-expanded="false">RESEARCH <span class="caret"></span></a> <ul class="dropdown-menu" role="menu"> <li class="level2"> <strong><a href="https://www.irif.fr/en/poles/asd/index" class="wikilink1" title="en:poles:asd:index" >Algorithms and discrete structures</a></strong> </li> <li class="level2"> <a href="https://www.irif.fr/en/equipes/algocomp/index" class="wikilink1" title="en:equipes:algocomp:index" >Algorithms and complexity</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/equipes/combi/index" class="wikilink1" title="en:equipes:combi:index" >Combinatorics</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/equipes/distribue/index" class="wikilink1" title="en:equipes:distribue:index" >Distributed computing</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/equipes/graphes/index" class="wikilink1" title="en:equipes:graphes:index" >Theory and algorithmics of graphs</a> </li> <li class="level2"> <strong><a href="https://www.irif.fr/en/poles/asv/index" class="wikilink1" title="en:poles:asv:index" >Automata, structures and verification</a></strong> </li> <li class="level2"> <a href="https://www.irif.fr/en/equipes/automates/index" class="wikilink1" title="en:equipes:automates:index" >Automata and applications</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/equipes/verif/index" class="wikilink1" title="en:equipes:verif:index" >Modeling and verification</a> </li> <li class="level2"> <strong><a href="https://www.irif.fr/en/poles/pps/index" class="wikilink1" title="en:poles:pps:index" >Proofs, programs and systems</a></strong> </li> <li class="level2"> <a href="https://www.irif.fr/en/equipes/algebre/index" class="wikilink1" title="en:equipes:algebre:index" >Algebra and computation</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/equipes/programmes/index" class="wikilink1" title="en:equipes:programmes:index" >Programs and Languages (PL)</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/equipes/preuves/index" class="wikilink1" title="en:equipes:preuves:index" >Proofs and programs</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/equipes/picube/index" class="wikilink1" title="en:equipes:picube:index" >Picube (Inria)</a><hr/> </li> <li class="level2"> <strong><a href="https://cnrs.hal.science/IRIF#" class="" title="https://cnrs.hal.science/IRIF#" rel="ugc nofollow">PUBLICATIONS (hal)</a></strong><br/> </li> </ul> </li> </ul> <ul class="nav navbar-nav"> <li class="level1 node active dropdown"><a href="#" class="dropdown-toggle" data-target="#" data-toggle="dropdown" role="button" aria-haspopup="true" aria-expanded="false">EVENTS <span class="caret"></span></a> <ul class="dropdown-menu" role="menu"> <li class="level2"> <strong><a href="https://www.irif.fr/en/seminaires/evenements" class="wikilink1" title="en:seminaires:evenements" >IRIF events</a></strong> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/irif/index" class="wikilink1" title="en:seminaires:irif:index" >IRIF Distinguished Talks Series</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/rencontres/irif/index" class="wikilink1" title="en:rencontres:irif:index" >IRIF days</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/rencontres/poles/index" class="wikilink1" title="en:rencontres:poles:index" >Pole meetings</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/env/index" class="wikilink1" title="en:seminaires:env:index" >IRIF and environment group</a> </li> <li class="level2"> <strong><a href="https://www.irif.fr/en/seminaires/seminaires" class="wikilink1" title="en:seminaires:seminaires" >Research seminars</a></strong> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/algocomp/index" class="wikilink1" title="en:seminaires:algocomp:index" >Algorithms and complexity</a> </li> <li class="level2 active"> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-curid="true">Algorithms and discrete structures</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/automates/index" class="wikilink1" title="en:seminaires:automates:index" >Automata</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/combi/index" class="wikilink1" title="en:seminaires:combi:index" >Enumerative and analytic combinatorics</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/adg/index" class="wikilink1" title="en:seminaires:adg:index" >Graphs and distributed computing</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/picube/index" class="wikilink1" title="en:seminaires:picube:index" >Formath</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/pps/index" class="wikilink1" title="en:seminaires:pps:index" >Proofs, programs and systems</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/verif/index" class="wikilink1" title="en:seminaires:verif:index" >Verification</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/doctorants/index" class="wikilink1" title="en:seminaires:doctorants:index" >Non-permanent members’ seminar</a> </li> <li class="level2"> <strong><a href="https://www.irif.fr/en/seminaires/onlineseminars" class="wikilink1" title="en:seminaires:onlineseminars" >Online seminars</a></strong> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/greta/index" class="wikilink1" title="en:seminaires:greta:index" >Graph Transformation Theory and Applications</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/numeration/index" class="wikilink1" title="en:seminaires:numeration:index" >One world numeration seminar</a> </li> <li class="level2"> <strong><a href="https://www.irif.fr/en/seminaires/gt" class="wikilink1" title="en:seminaires:gt" >Working groups</a></strong> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/cat/index" class="wikilink1" title="en:seminaires:cat:index" >Higher categories, polygraphs and homotopy</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/laag/index" class="wikilink1" title="en:seminaires:laag:index" >Logic, automata, algebra and games</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/programmation/index" class="wikilink1" title="en:seminaires:programmation:index" >Programming</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/semantique/index" class="wikilink1" title="en:seminaires:semantique:index" >Semantics</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/sms/index" class="wikilink1" title="en:seminaires:sms:index" >Syntax Meets Semantics</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/hott/index" class="wikilink1" title="en:seminaires:hott:index" >Type theory and homotopy theory</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/types/index" class="wikilink1" title="en:seminaires:types:index" >Type theory and realisability</a> </li> <li class="level2"> <strong><a href="https://www.irif.fr/en/seminaires/soutenances" class="wikilink1" title="en:seminaires:soutenances" >Defences</a></strong> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/these/index" class="wikilink1" title="en:seminaires:these:index" >PhD defences</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/seminaires/hdr/index" class="wikilink1" title="en:seminaires:hdr:index" >Habilitation defences</a> </li> </ul> </li> </ul> <ul class="nav navbar-nav"> <li class="level1 node dropdown"><a href="#" class="dropdown-toggle" data-target="#" data-toggle="dropdown" role="button" aria-haspopup="true" aria-expanded="false">MEDIATION <span class="caret"></span></a> <ul class="dropdown-menu" role="menu"> <li class="level2"> <a href="https://www.irif.fr/en/mediation/fdls" class="wikilink1" title="en:mediation:fdls" >Fête de la Science</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/mediation/scolaire" class="wikilink1" title="en:mediation:scolaire" >Middle/High school internships</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/portraits/index" class="wikilink1" title="en:portraits:index" >Research profiles</a> </li> <li class="level2"> <a href="https://icalp2022.irif.fr/?page_id=1111" class="" title="https://icalp2022.irif.fr/?page_id=1111" rel="ugc nofollow">50 Years Exhibitation</a> </li> <li class="level2"> <a href="https://qubobs.irif.fr" class="" title="https://qubobs.irif.fr" rel="ugc nofollow">Projet QuBOBS (quantum computing explained)</a> </li> </ul> </li> </ul> <ul class="nav navbar-nav"> <li class="level1 node dropdown"><a href="#" class="dropdown-toggle" data-target="#" data-toggle="dropdown" role="button" aria-haspopup="true" aria-expanded="false">HIGHLIGHTS <span class="caret"></span></a> <ul class="dropdown-menu" role="menu"> <li class="level2"> <a href="https://www.irif.fr/en/distinctions/index" class="wikilink1" title="en:distinctions:index" >Awards and Honors</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/logiciels/index" class="wikilink1" title="en:logiciels:index" >Software</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/contrats/index" class="wikilink1" title="en:contrats:index" >Grants</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/international/index" class="wikilink1" title="en:international:index" >International Collaborations</a> </li> <li class="level2"> <a href="https://epit.irif.fr" class="" title="https://epit.irif.fr" rel="ugc nofollow">The EPIT Research School</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/formation/index" class="wikilink1" title="en:formation:index" >Academics</a> </li> </ul> </li> </ul> <ul class="nav navbar-nav"> <li class="level1 node dropdown"><a href="#" class="dropdown-toggle" data-target="#" data-toggle="dropdown" role="button" aria-haspopup="true" aria-expanded="false">JOIN US <span class="caret"></span></a> <ul class="dropdown-menu" role="menu"> <li class="level2"> <a href="https://www.irif.fr/en/informations/visit" class="wikilink1" title="en:informations:visit" >Visitor program</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/postes/admin" class="wikilink1" title="en:postes:admin" >Research support position</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/postes/universite" class="wikilink1" title="en:postes:universite" >Faculty members</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/postes/chercheur" class="wikilink1" title="en:postes:chercheur" >Researchers</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/postes/postdoc" class="wikilink1" title="en:postes:postdoc" >Postdocs</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/postes/ater" class="wikilink1" title="en:postes:ater" >Teaching assistants</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/postes/these" class="wikilink1" title="en:postes:these" >PhD Studies</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/postes/stage" class="wikilink1" title="en:postes:stage" >Master Internships</a> </li> <li class="level2"> <a href="https://www.irif.fr/en/postes/stage-scolaire" class="wikilink1" title="en:postes:stage-scolaire" >Middle/High school internships</a> </li> </ul> </li> </ul> <ul class="nav navbar-nav"> <li class="level1"> <a href="https://www.irif.fr/en/intranet/index" class="wikilink1" title="en:intranet:index" >INTRANET</a> </li> </ul> <div class="navbar-right" id="dw__navbar_items">  <ul class="nav navbar-nav" id="dw__translation"> <li class="dropdown"> <a href="" class="dropdown-toggle" data-target="#" data-toggle="dropdown" title="Translations of this page" role="button" aria-haspopup="true" aria-expanded="false"> <span class="iconify" data-icon="mdi:flag"></span> <span class="hidden-lg hidden-md hidden-sm">Translations of this page</span><span class="caret"></span> </a> <ul class="dropdown-menu" role="menu"> <li class="dropdown-header hidden-xs hidden-sm"> <span class="iconify" data-icon="mdi:flag"></span> Translations of this page </li> <li><div class='li'><a href="https://www.irif.fr/seminaires/asd/index" class="wikilink1 flag" title="Français"><img src="https://www.irif.fr/lib/plugins/translation/flags/fr.gif" alt="fr" height="11" />Français</a></li><li><div class='li cur'><a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1 cur flag" title="English"><img src="https://www.irif.fr/lib/plugins/translation/flags/en.gif" alt="en" height="11" />English</a></li> </ul> </li> </ul>  <ul class="nav navbar-nav"> <li> <span class="dw__actions dw-action-icon"> <a href="https://www.irif.fr/en/seminaires/asd/index?do=login&sectok=" title="Log In" rel="nofollow" class="menuitem login btn btn-default navbar-btn"><svg xmlns="http://www.w3.org/2000/svg" width="24" height="24" viewBox="0 0 24 24"><path d="M10 17.25V14H3v-4h7V6.75L15.25 12 10 17.25M8 2h9a2 2 0 0 1 2 2v16a2 2 0 0 1-2 2H8a2 2 0 0 1-2-2v-4h2v4h9V4H8v4H6V4a2 2 0 0 1 2-2z"/></svg><span class=""> Log In</span></a> </span> </li> </ul> </div> </div> </div> </nav>  </header> <a name="dokuwiki__top" id="dokuwiki__top"></a> <main role="main" class="dw-container pb-5 dokuwiki container-fluid mx-5"> <div id="dokuwiki__pageheader"> <p class="text-right"> </p> <div id="dw__msgarea" class="small"> </div> </div> <div class="row"> <article id="dokuwiki__content" class="col-sm-12 col-md-12 " itemscope itemtype="http://schema.org/Article" itemref="dw__license">  <div class="no-panel" itemprop="articleBody"> <div class="page "> <div class="dw-content-page "><div class="dw-content"><div class="plugin_include_content plugin_include__en:seminaires:asd:indexheader" id="plugin_include__en__seminaires__asd__indexheader"> <div class="datatemplateentry"> <p> <br/> </p> <div class="wrap_right plugin_wrap"> <p> <div class="bs-wrap bs-wrap-well well"> <span class="bs-wrap bs-wrap-button" data-btn-type="primary" data-btn-size="sm" data-btn-disabled="1">Seminar</span> </p> <div class=""> <p> <span class="bs-wrap bs-wrap-label label label-default">Pole</span> <a href="https://www.irif.fr/en/seminaires/asd/0_pageid" class="wikilink2" title="en:seminaires:asd:0_pageid" rel="nofollow" data-wiki-id="en:seminaires:asd:0_pageid"><a href="https://www.irif.fr/en/poles/asd/index" class="wikilink1" title="en:poles:asd:index" data-wiki-id="en:poles:asd:index">Algorithms and discrete structures</a></a><br/> </p> </div><div class=""> <p> <span class="bs-wrap bs-wrap-label label label-default">Thematic team</span> <a href="https://www.irif.fr/en/seminaires/asd/0_pageid" class="wikilink2" title="en:seminaires:asd:0_pageid" rel="nofollow" data-wiki-id="en:seminaires:asd:0_pageid"><a href="https://www.irif.fr/en/equipes/algocomp/index" class="wikilink1" title="en:equipes:algocomp:index" data-wiki-id="en:equipes:algocomp:index">Algorithms and complexity</a></a><br/> <span class="bs-wrap bs-wrap-label label label-default">Thematic team</span> <a href="https://www.irif.fr/en/seminaires/asd/1_pageid" class="wikilink2" title="en:seminaires:asd:1_pageid" rel="nofollow" data-wiki-id="en:seminaires:asd:1_pageid"><a href="https://www.irif.fr/en/equipes/combi/index" class="wikilink1" title="en:equipes:combi:index" data-wiki-id="en:equipes:combi:index">Combinatorics</a></a><br/> <span class="bs-wrap bs-wrap-label label label-default">Thematic team</span> <a href="https://www.irif.fr/en/seminaires/asd/2_pageid" class="wikilink2" title="en:seminaires:asd:2_pageid" rel="nofollow" data-wiki-id="en:seminaires:asd:2_pageid"><a href="https://www.irif.fr/en/equipes/graphes/index" class="wikilink1" title="en:equipes:graphes:index" data-wiki-id="en:equipes:graphes:index">Theory and algorithmics of graphs</a></a><br/> </p> </div> <p> </div> </p> <div style='display:none'><div class="wrap_right plugin_wrap"> <p> <span class="bs-wrap bs-wrap-button" data-btn-type="default"><a href="https://www.irif.fr/admindb/seminaires/" class="urlextern" title="https://www.irif.fr/admindb/seminaires/" rel="ugc nofollow">Manage talks</a></span> </p> </div></div></div> <h2 id="algorithms_and_discrete_structures" class=" page-header pb-3 mb-4 mt-5">Algorithms and discrete structures</h2> <div class="level2"> <p> The <a href="http://www.irif.fr/_media/ical/asd.ics" class="urlextern" title="http://www.irif.fr/_media/ical/asd.ics" rel="ugc nofollow">calendar</a> of events (iCal format). <br/> In order to add the event calendar to your favorite agenda, subscribe to the calendar by using this link. </p> <p> <br/> </p> </div> <h4 id="contact_s">Contact(s)</h4> <div class="level4"> <div class=""> <p> <a href="https://www.irif.fr/~chapuy" class="urlextern" title="https://www.irif.fr/~chapuy" rel="ugc nofollow">Guillaume Chapuy</a><br/> <a href="https://www.irif.fr/~duchi/" class="urlextern" title="https://www.irif.fr/~duchi/" rel="ugc nofollow">Enrica Duchi</a><br/> <a href="https://www.irif.fr/~pierref/" class="urlextern" title="https://www.irif.fr/~pierref/" rel="ugc nofollow">Pierre Fraigniaud</a><br/> <a href="https://www.irif.fr/~laplante/" class="urlextern" title="https://www.irif.fr/~laplante/" rel="ugc nofollow">Sophie Laplante</a><br/> <a href="https://www.irif.fr/~reza/pmwiki/pmwiki.php" class="urlextern" title="https://www.irif.fr/~reza/pmwiki/pmwiki.php" rel="ugc nofollow">Reza Naserasr</a><br/> </p> </div> </div> </div></div> <p> <br/> </p> <h3 class="sectionedit3 page-header pb-3 mb-4 mt-5" id="previous_talks">Previous talks</h3> <div class="level3"> <p> <br/> </p> </div> <h4 id="year_2024">Year 2024</h4> <div class="level4"> </div> <div class="plugin_include_content plugin_include__en:seminaires:asd:asd2024" id="plugin_include__en__seminaires__asd__asd2024"> <div class="level4"> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Friday September 13, 2024, 2PM, Salle 3052<br/> <strong>Shuichi Hirahara</strong> (National Institute of Informatics, Japan) <em>Planted Clique Conjectures Are Equivalent</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3904"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3904"><div class="bs-wrap bs-wrap-well well well-sm"> Planted Clique Conjecture states that no polynomial-time algorithm can find a k-clique in an n-vertex Erdős-Rényi random graph with a k-clique planted for $k << n^{1/2}$. We present the equivalence among many variants of planted clique conjectures, including search versions of a success probability exponentially close to 1 and with a non-negligible success probability, a worst-case version (the k-clique problem on incompressible graphs), and decision versions with small and large probabilities. In particular, this equivalence identifies the optimality of a simple edge counting algorithm: By counting the number of edges, one can efficiently distinguish an n-vertex random graph from a random graph with a k-clique planted with probability $k^2/n$ for any $k \le n^{1/2}$. We show that for *any* k, no polynomial-time algorithm can distinguish these two random graphs with probability significantly larger than $k^2/n$ *if and only if* the planted clique conjecture holds. <p> Joint work with Nobutaka Shimizu. Paper: <a href="https://eccc.weizmann.ac.il/report/2024/058/" class="urlextern" title="https://eccc.weizmann.ac.il/report/2024/058/" rel="ugc nofollow">https://eccc.weizmann.ac.il/report/2024/058/</a> </div> </p> </div> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Friday June 14, 2024, 3:30PM, Salle 3052<br/> <strong>Venkatesan Guruswami</strong> (Simons Institute) <em>When and why do efficient algorithms exist (for constraint satisfaction and beyond)?</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3905"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3905"><div class="bs-wrap bs-wrap-well well well-sm"> Computational problems exhibit a diverse range of behaviors in terms of how quickly and effectively they can be solved. What underlying mathematical structure (or lack thereof) in a computational problem leads to an efficient algorithm for solving it (or dictates its intractability)? Given the vast landscape of problems and algorithmic approaches, it would be simplistic to hope for a universal theory explaining the underpinnings of easiness/hardness. Yet, in the realm of constraint satisfaction problems (CSP), the algebraic dichotomy theorem gives a definitive answer: a polynomial time algorithm exists when there are non-trivial local operations called polymorphisms under which the solution space is closed; otherwise the problem is NP-complete. <p> Inspired and emboldened by this, one might speculate a polymorphic principle in more general contexts, with symmetries in the solution space governing efficient algorithms. Beginning with some background on CSP and the polymorphic approach to understanding their complexity, the talk will discuss some extensions beyond CSP where the polymorphic principle seems promising (yet far from understood). In particular, we will discuss “promise CSP” (PCSP) where one is allowed to satisfy a relaxed version of the constraints (a framework that includes important problems like approximate graph coloring). We will provide glimpses of the emerging polymorphic theory characterizing the (in)tractability of interesting classes of PCSP as well as the ability of natural classes of algorithms to solve them. </div> </p> </div> </div> </div> <div class="level4"> <p> <br/> </p> </div> <h4 id="year_2023">Year 2023</h4> <div class="level4"> </div> <div class="plugin_include_content plugin_include__en:seminaires:asd:asd2023" id="plugin_include__en__seminaires__asd__asd2023"> <div class="level4"> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Tuesday April 18, 2023, 3:30PM, 3052, Sophie Germain<br/> <strong>Mamadou Kanté</strong> (LIMOS, Clermond-Ferrand) <em>Lettericity of graphs and griddability of permutations</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3906"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3906"><div class="bs-wrap bs-wrap-well well well-sm"> Lettericity is a graph parameter measuring how close a graph is to a word and geometric griddability measures how close a permutation is to a monotone permutation. Both of these parameters enjoy nice properties, in particular graphs of lettericity k are definable in Monadic second-order logic and permutations that are geometric M-griddability are in bijection with a regular language. I will first present both and some properties, and show that these seemingly unrelated parameters are in fact equivalent in permutation graphs, i.e., a permutation class has small geometric griddability iff the associated permutation graph class has small lettericity. </div> </div> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Wednesday April 5, 2023, 3PM, 3052<br/> <strong>Lélia Blin</strong> (LIP6) <em>Self-Stabilizing Distributed Algorithms</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3907"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3907"><div class="bs-wrap bs-wrap-well well well-sm"> In the context of large-scale networks, fault tolerance is a necessity. Self-stabilization is an algorithmic approach to fault tolerance in distributed systems. Its aim is to manage processors' memory corruption due to transient failures. The efficiency of a self-stabilizing algorithm is characterized by several parameters, including (1) the time taken by the system to return to a legal configuration after an arbitrary corruption of its processors' memory, and (2) the memory space used by the processors to execute the algorithm. Minimizing memory space is motivated by many aspects, such as networks (e.g. sensor networks) with limited memory space, minimizing data exchanges between processors, and limiting information storage to use redundancy techniques. This seminar will present self-stabilization through two main classical problems: constructing spanning trees, especially those of minimum weight, and electing a leader. It will cover the links between self-stabilization and distributed decision techniques, including computing lower bounds on memory space needed to solve the aforementioned problems using self-stabilizing algorithms. </div> </div> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Wednesday March 22, 2023, 3PM, 3052<br/> <strong>Michail Lampis</strong> (LAMSADE) <em>First Order Logic on Pathwidth Revisited Again</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3908"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3908"><div class="bs-wrap bs-wrap-well well well-sm"> Courcelle's theorem, which states that all MSO-expressible properties can be decided in linear time on graphs of bounded treewidth, is one of the most celebrated results in parameterized complexity, because it implies the existence of linear-time FPT algorithms for a host of NP- hard problems. Unfortunately, the hidden constant implied by this theorem is a tower of exponentials whose height increases with each quantifier alternation in the formula. <p> In this talk we take a high-level view of this area of research and survey results that attempt to improve upon this performance by considering more restricted classes of inputs. This is known to be impossible, even if we restrict the input to graphs of treewidth 1 (trees) and only consider FO logic; or if we consider graphs of pathwidth 1 (caterpillars) and consider MSO logic. This would seem to indicate that Courcelle's theorem is “best possible”. Surprisingly, we discover that in the only remaining case which has so far been overlooked, namely FO logic on graphs of constant pathwidth, all known hardness results fail, because the problem becomes tractable with an elementary parameter dependence on the input formula. Our result generalizes previously known meta-theorems for the much more restricted parameter tree-depth. </p> <p> Results based on a preprint available here: <a href="https://arxiv.org/abs/2210.09899" class="urlextern" title="https://arxiv.org/abs/2210.09899" rel="ugc nofollow">https://arxiv.org/abs/2210.09899</a> </div> </p> </div> </div> </div> <div class="level4"> <p> <br/> </p> </div> <h4 id="year_2022">Year 2022</h4> <div class="level4"> </div> <div class="plugin_include_content plugin_include__en:seminaires:asd:asd2022" id="plugin_include__en__seminaires__asd__asd2022"> <div class="level4"> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Tuesday October 11, 2022, 9:30AM, Amphi Turing<br/> <strong><a href="Https://www.irif.fr/poles/asd/rentree2022" class="urlextern" title="Https://www.irif.fr/poles/asd/rentree2022" rel="ugc nofollow"> Anual Meeting Of Pole Asd, Presentation From New Members</a></strong> (IRIF) <em></em><em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3909"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3909"><div class="bs-wrap bs-wrap-well well well-sm"> 09:30-10:00 - Marie Albenque <p> 10:00-10:30 - Sergio Rajsbaum </p> <p> 10:30-11:15 <code>Short introduction of new postdocs and Ph.D. students followed by General discussion and then coffee break</code> </p> <p> 11:15-11:45 - Monika Csikos </p> <p> 11:45-12:15 - Sophie Laplante </div> </p> </div> </div> </div> <div class="level4"> <p> <br/> </p> </div> <h4 id="year_2021">Year 2021</h4> <div class="level4"> </div> <div class="plugin_include_content plugin_include__en:seminaires:asd:asd2021" id="plugin_include__en__seminaires__asd__asd2021"> <div class="level4"> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Tuesday November 16, 2021, 1:30PM, Room 234C, Halle aux farines<br/> <strong>Pole Day</strong> (ASD) <em>Journée du pôle Algorithmes et structures discrètes 2021</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3910"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3910"><div class="bs-wrap bs-wrap-well well well-sm"> Journée du pôle Algorithmes et structures discrètes 2021 <p> Tuesday November 16, 2021 · Room 234C, Halle aux farines </p> <pre class="code">13:30-14:00 - Mikael Rabie 14:00-14:30 - Matej Stehlik</pre> <pre class="code">14:40 – 15:10 Informal introduction of new postdocs and docs</pre> <pre class="code">15:15-15:45 - Adrian Vladu 15:45-16:15 - Simon Apers 16:15 Goûter (à l'IRIF)</pre> <p> </div> </p> </div> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Tuesday June 15, 2021, 2PM, Salle 3052<br/> <strong>Magnús Halldórsson</strong> (Reykjavik University) <em>New Vistas in Distributed Graph Coloring</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3911"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3911"><div class="bs-wrap bs-wrap-well well well-sm"> The first and possibly the most fundamental problem in distributed graph algorithmics is the vertex coloring problem. The nodes of a network are processes that communicate via the edges in synchronous rounds. The most basic problem is to color the network using Delta+1 colors in as few rounds a possible, where Delta is the maximum degree of the graph. <p> We present a new approach for randomized distributed Delta+1-coloring that is dramatically simpler than the previous best: the seminal work of Chang, Li, and Pettie (CLP) in SICOMP 2020. This approach offers numerous refinements: It matches the O(log^3 log n) round complexity in general, while on high-degree graphs (Delta » log^2 n), it uses only O(log* n) rounds. It uses small messages, i.e., works also in the CONGEST model. It also offers tradeoffs between the number of colors used, the round complexity, and the clique number of the graph. </p> <p> We expect that the approach presented will lead the way towards improved results for various coloring problems in the near future. </p> <p> This is based on a paper at STOC'21, joint work with Fabian Kuhn, Yannic Maus, and Tigran Tonoyan; and a more recent one on arXiv, joint with Alexandre Nolin, and Tigran Tonoyan. </div> </p> </div> <p> The seminar will be available online by the following ZOOM-link: </p> <p> <a href="https://u-paris.zoom.us/j/84049775680?pwd=Yk5lMDhlZUNQRGMyelExMVdoM2poQT09" class="urlextern" title="https://u-paris.zoom.us/j/84049775680?pwd=Yk5lMDhlZUNQRGMyelExMVdoM2poQT09" rel="ugc nofollow">https://u-paris.zoom.us/j/84049775680?pwd=Yk5lMDhlZUNQRGMyelExMVdoM2poQT09</a> </p> </div> </div> <div class="level4"> <p> <br/> </p> </div> <h4 id="year_2020">Year 2020</h4> <div class="level4"> </div> <div class="plugin_include_content plugin_include__en:seminaires:asd:asd2020" id="plugin_include__en__seminaires__asd__asd2020"> <div class="level4"> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Tuesday May 26, 2020, 11AM, Online<br/> <strong>Édouard Bonnet</strong> (ENS Lyon) <em>Twin-width</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3912"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3912"><div class="bs-wrap bs-wrap-well well well-sm"> 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 proper 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 checking, 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 algorithm runs in time $f(d,|\phi|) |D|$ where f is a computable but non-elementary 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 Gajarsky et al. [FOCS '15]. Finally we mention a curious connection between bounded twin-width and small classes. <p> Joint work with Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant </div> </p> </div> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Monday January 27, 2020, 9:30AM, 3052<br/> <strong>Amaury Pouly</strong> (IRIF) <em>Continuous models of computation: computability, complexity, universality</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3913"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3913"><div class="bs-wrap bs-wrap-well well well-sm"> In 1941, Claude Shannon introduced a continuous-time analog model of computation, namely the General Purpose Analog Computer (GPAC). The GPAC is a physically feasible model in the sense that it can be implemented in practice through the use of analog electronics or mechanical devices. It can be proved that the functions computed by a GPAC are precisely the solutions of a special class of differential equations where the right-hand side is a polynomial. Analog computers have since been replaced by digital counterpart. Nevertheless, one can wonder how the GPAC could be compared to Turing machines. <p> A few years ago, it was shown that Turing-based paradigms and the GPAC have the same computational power. However, this result did not shed any light on what happens at a computational complexity level. In other words, analog computers do not make a difference about what can be computed; but maybe they could compute faster than a digital computer. A fundamental difficulty of continuous-time model is to define a proper notion of complexity. Indeed, a troubling problem is that many models exhibit the so-called Zeno's phenomenon, also known as space-time contraction. </p> <p> In this talk, I will present results from my thesis that give several fundamental contributions to these questions. We show that the GPAC has the same computational power as the Turing machine, at the complexity level. We also provide as a side effect a purely analog, machine- independent characterization of P and Computable Analysis. </p> <p> I will present some recent work on the universality of polynomial differential equations. We show that when we impose no restrictions at all on the system, it is possible to build a fixed equation that is universal in the sense it can approximate arbitrarily well any continuous curve over R, simply by changing the initial condition of the system. </p> <p> If time allows, I will also mention some recent application of this work to show that chemical reaction networks are strongly Turing complete with the differential semantics. </div> </p> </div> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Thursday January 23, 2020, 11AM, Salle 1007<br/> <strong>Moni Naor</strong> (Weizmann Institute) <em>Instance Complexity and Unlabeled Certificates in the Decision Tree Model</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3914"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3914"><div class="bs-wrap bs-wrap-well well well-sm"> Suppose that you want to check whether a graph satisfies some (graph) property. The goal is to minimize the number of queries to the adjacency 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? <p> In this talk I will discuss labeled and unlabeled certificates, in particular in the context of ``instance optimality“. This is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, respectively. </p> <p> Joint work with Tomer Grossman and Ilan Komargodski </div> </p> </div> </div> </div> <div class="level4"> <p> <br/> </p> </div> <h4 id="year_2019">Year 2019</h4> <div class="level4"> </div> <div class="plugin_include_content plugin_include__en:seminaires:asd:asd2019" id="plugin_include__en__seminaires__asd__asd2019"> <div class="level4"> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Wednesday October 2, 2019, 11AM, Salle 3052<br/> <strong>Sophie Laplante</strong> (IRIF) <em>The sensitivity conjecture and a recent proof of it (part II)</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3915"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3915"><div class="bs-wrap bs-wrap-well well well-sm"> Informal presentation. </div> </div> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Thursday September 26, 2019, 2PM, Salle 3052<br/> <strong>Sophie Laplante</strong> (IRIF) <em>The sensitivity conjecture and a recent proof of it (part I)</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3916"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3916"><div class="bs-wrap bs-wrap-well well well-sm"> Informal presentation. </div> </div> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Monday June 24, 2019, 11AM, Salle 3052<br/> <strong>Carola Doerr</strong> (CNRS, LIP6) <em>Evolutionary Algorithms – From Theory to Practice and Back</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3917"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3917"><div class="bs-wrap bs-wrap-well well well-sm"> Most real-world optimization problems do not have an explicit problem formulation, but only allow to compute the quality of selected solution candidates. Solving such black-box optimization problems requires iterative procedures which use the feedback gained from previous evaluations to determine the strategy by which the next solution candidates are generated. Many black-box optimization algorithms, such as Simulated Annealing, Evolutionary Algorithms, Swarm Intelligence Algorithms, are randomized – making it very difficult to analyze their performances mathematically. In the last 15 years, the theory of randomized black-box optimization has advanced considerably, and has contributed to efficient optimization by providing insights into the working principles of black-box optimization which are hard or impossible to obtain by empirical means. On the other hand, empirically-guided benchmarking has opened up new research directions for theoretical investigations. In this presentation we will discuss 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. </div> </div> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Thursday May 9, 2019, 3PM, Salle 1007<br/> <strong>Amélie Gheerbrant</strong> (IRIF) <em>Graph query languages</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3918"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3918"><div class="bs-wrap bs-wrap-well well well-sm"> Graph databases use graph structure to represent and query data. The talk will survey some graph query languages used in this context, with a focus on regular path queries (RPQs) and conjunctive regular path queries (CRPQs). We will present the different semantics that graph database systems use for them (every path, simple path, trail), and recall computational 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 group. </div> </div> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Tuesday February 19, 2019, 11AM, Salle 3052<br/> <strong>Danupon Nanongkai</strong> (KTH) <em>Distributed Shortest Paths, Exactly</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3919"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3919"><div class="bs-wrap bs-wrap-well well well-sm"> 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 can perform equally well. In this talk, we will discuss some recent progress in answering this question. Most recent works that this talk is based on are with Sebastian Krinninger (FOCS 2018) and Aaron Bernstein (ArXiv 2018). </div> </div> </div> </div> <div class="level4"> <p> <br/> </p> </div> <h4 id="year_2018">Year 2018</h4> <div class="level4"> </div> <div class="plugin_include_content plugin_include__en:seminaires:asd:asd2018" id="plugin_include__en__seminaires__asd__asd2018"> <div class="level4"> <p> <a href="https://www.irif.fr/en/seminaires/asd/index" class="wikilink1" title="en:seminaires:asd:index" data-wiki-id="en:seminaires:asd:index">Algorithms and discrete structures</a><br/> Monday December 3, 2018, 11AM, Salle 3052<br/> <strong>Cédric Boutillier</strong> (LPSM, Sorbonne Université) <em>Statistical mechanics on isoradial graphs</em> <span class="bs-wrap bs-wrap-button" data-btn-type="link" data-btn-size="xs" data-btn-collapse="b26-3920"><i class="dw-icons fa-lg fa fa-info-circle" style="color:#777" title=""></i></span><br/> </p> <div class="bs-wrap bs-wrap-collapse collapse" id="b26-3920"><div class="bs-wrap bs-wrap-well well well-sm"> Isoradial graphs are embedded planar graphs in such a way that every face is inscribed in a circle of radius 1. They are a perfect ground to develop a theory of discrete complex analysis and to define integrable models in statistical mechanics. In this talk, we will describe combinatorial and geometric aspects of these graphs, and their impact on locality of some models of statistical mechanics (dimer models, random walk, spanning trees…) </div> </div> </div> </div> <div class="level4"> </div> </div></div><p> <style> .page a.urlextern, .page a.interwiki, .page a.windows, .page a.mail, .page a.media { padding-left: 0 !important; background: none !important; } .page { text-align: justify; } body {font-size: 15px; font-weight: 300; color: #333333; } b,strong {font-weight: 600; color: #333333; } p {margin-bottom:1.3em} h1 {font-size: 2.8em; margin-bottom:1.5em; font-weight: 400; } h2 {font-size: 2.2em; margin-bottom:1.2em; font-weight: 400; } h3 {font-size: 1.9em; margin-bottom:0.9em; font-weight: 400; } h4 {font-size: 1.7em; margin-bottom:0.8em; font-weight: 300; } h5 {font-size: 1.5em; margin-bottom:0.8em; font-weight: 300; } h5 {font-size: 1.4em; margin-bottom:0.8em; font-weight: 300; } </style> </p> </div> </div> <div class="small text-right"> </div> </article> </div> </main> <footer id="dw__footer" class="dw-container py-5 dokuwiki container-fluid">  <div class="dw-container small container-fluid mx-5"> <div class="footer-dw-title"> <div class="media"> <div class="media-left">  <img src="https://www.irif.fr/_media/logo_footer.png" alt="" class="media-object" style="height:10px" /> </div> <div class="media-body"> <div class="row"> <div class="col-sm-2"> <h4 class="media-heading"></h4> <p> </p> </div> <div class="col-sm-10"> </div> </div> </div> </div> </div> <a style="font-size:12px" href="https://www.irif.fr/informations/mentions-legales">Mentions légales</a> <div class="footer-license row"> <hr/> <div id="dw__license" class="col-sm-6"> </div> <div class="col-sm-6"> </div> </div> </div>  </footer> <a href="#dokuwiki__top" class="back-to-top hidden-print btn btn-default" title="skip to content" accesskey="t"> <span class="iconify" data-icon="mdi:chevron-up"></span> </a> <div id="screen__mode"> <span class="visible-xs-block"></span> <span class="visible-sm-block"></span> <span class="visible-md-block"></span> <span class="visible-lg-block"></span> </div> <img src="https://www.irif.fr/lib/exe/taskrunner.php?id=en%3Aseminaires%3Aasd%3Aindex&1732750390" width="2" height="1" alt="" /> </div> </body> </html>