CINXE.COM
Algorithms and Complexity - Max Planck Institute for Informatics
<!DOCTYPE html> <html lang="en-US"> <head> <meta charset="utf-8"> <!-- This website is powered by TYPO3 - inspiring people to share! TYPO3 is a free open source Content Management Framework initially created by Kasper Skaarhoj and licensed under GNU/GPL. TYPO3 is copyright 1998-2024 of Kasper Skaarhoj. Extensions are copyright of their respective owners. Information and contribution at https://typo3.org/ --> <base href="https://www.mpi-inf.mpg.de/"> <link rel="icon" href="/typo3conf/ext/mpi_inf_site_package/Resources/Public/favicon.ico" type="image/vnd.microsoft.icon"> <title>Algorithms and Complexity - Max Planck Institute for Informatics</title> <meta http-equiv="x-ua-compatible" content="IE=edge" /> <meta name="generator" content="TYPO3 CMS" /> <meta name="viewport" content="width=device-width, initial-scale=1, minimum-scale=1" /> <meta name="robots" content="index,follow" /> <meta name="twitter:card" content="summary" /> <meta name="apple-mobile-web-app-capable" content="no" /> <link rel="stylesheet" href="/typo3temp/assets/css/477c5e4dcc714b3ff0da8403884a460e.css?1697447411" media="all"> <link rel="stylesheet" href="/typo3conf/ext/mpi_inf_site_package/Resources/Public/Css/swiper-bundle-8.4.6.min.css?1725541122" media="screen"> <link rel="stylesheet" href="/typo3conf/ext/mpi_inf_site_package/Resources/Public/Css/style.css?1725541122" media="all"> <script src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/JavaScript/Build/head.js?1725541122"></script> <style>.page-141 .news__categories { display: none !important; }</style> <link rel="canonical" href="https://www.mpi-inf.mpg.de/departments/algorithms-complexity"/> </head> <body id="p37" class="page page-37 page-lvl--2 lang--0 be-layout--standard layout--5 dep--d1"><a name="top"></a> <div class="skip-link"> Skip to <a href="#main">main content</a> or <a href="#nav">main navigation</a> </div> <style> .department-lnk--d1 .department-lnk__icon { background: #a50d0f; } .department-lnk--d1.active, .department-lnk--d1:active, .department-lnk--d1:hover { background: #a50d0f; } .department-lnk--d1.active .department-lnk__id, .department-lnk--d1:active .department-lnk__id, .department-lnk--d1:hover .department-lnk__id { color: #a50d0f; } </style> <style> .department-lnk--d2 .department-lnk__icon { background: #db6413; } .department-lnk--d2.active, .department-lnk--d2:active, .department-lnk--d2:hover { background: #db6413; } .department-lnk--d2.active .department-lnk__id, .department-lnk--d2:active .department-lnk__id, .department-lnk--d2:hover .department-lnk__id { color: #db6413; } </style> <style> .department-lnk--d3 .department-lnk__icon { background: #758e25; } .department-lnk--d3.active, .department-lnk--d3:active, .department-lnk--d3:hover { background: #758e25; } .department-lnk--d3.active .department-lnk__id, .department-lnk--d3:active .department-lnk__id, .department-lnk--d3:hover .department-lnk__id { color: #758e25; } </style> <style> .department-lnk--d4 .department-lnk__icon { background: #0d82a1; } .department-lnk--d4.active, .department-lnk--d4:active, .department-lnk--d4:hover { background: #0d82a1; } .department-lnk--d4.active .department-lnk__id, .department-lnk--d4:active .department-lnk__id, .department-lnk--d4:hover .department-lnk__id { color: #0d82a1; } </style> <style> .department-lnk--d5 .department-lnk__icon { background: #87136e; } .department-lnk--d5.active, .department-lnk--d5:active, .department-lnk--d5:hover { background: #87136e; } .department-lnk--d5.active .department-lnk__id, .department-lnk--d5:active .department-lnk__id, .department-lnk--d5:hover .department-lnk__id { color: #87136e; } </style> <style> .department-lnk--d6 .department-lnk__icon { background: #03325d; } .department-lnk--d6.active, .department-lnk--d6:active, .department-lnk--d6:hover { background: #03325d; } .department-lnk--d6.active .department-lnk__id, .department-lnk--d6:active .department-lnk__id, .department-lnk--d6:hover .department-lnk__id { color: #03325d; } </style> <style> .department-lnk--rg1 .department-lnk__icon { background: #f0b006; } .department-lnk--rg1.active, .department-lnk--rg1:active, .department-lnk--rg1:hover { background: #f0b006; } .department-lnk--rg1.active .department-lnk__id, .department-lnk--rg1:active .department-lnk__id, .department-lnk--rg1:hover .department-lnk__id { color: #f0b006; } </style> <style> .department-lnk--rg2 .department-lnk__icon { background: #d7390b; } .department-lnk--rg2.active, .department-lnk--rg2:active, .department-lnk--rg2:hover { background: #d7390b; } .department-lnk--rg2.active .department-lnk__id, .department-lnk--rg2:active .department-lnk__id, .department-lnk--rg2:hover .department-lnk__id { color: #d7390b; } </style> <style> .department-lnk--rg3 .department-lnk__icon { background: #5aa1a8; } .department-lnk--rg3.active, .department-lnk--rg3:active, .department-lnk--rg3:hover { background: #5aa1a8; } .department-lnk--rg3.active .department-lnk__id, .department-lnk--rg3:active .department-lnk__id, .department-lnk--rg3:hover .department-lnk__id { color: #5aa1a8; } </style> <nav class="site__department-nav department-dd js-site-department-nav " title=""> <a class="department-dd__toggle js-site-department-dd-toggle" role="button" title="" href="javascript:"> <i class="mpg-icon mpg-icon-down2"></i> </a> <ul class="department-dd__menu"> <li> <a class="department-lnk department-lnk--home js-department-dd-lnk" href="/home"> <span class="department-lnk__ct"> <span class="department-lnk__icon"> <i class="mpg-icon mpg-icon-home"></i> </span> <span class="department-lnk__lbl"> Institute </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--d1 active current" href="/departments/algorithms-complexity" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> D1 </span> </span> <span class="department-lnk__lbl"> Algorithms and Complexity </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--d2 " href="/departments/computer-vision-and-machine-learning" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> D2 </span> </span> <span class="department-lnk__lbl"> Computer Vision and Machine Learning </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--d3 " href="/departments/inet" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> D3 </span> </span> <span class="department-lnk__lbl"> Internet Architecture </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--d4 " href="/departments/computer-graphics" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> D4 </span> </span> <span class="department-lnk__lbl"> Computer Graphics </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--d5 " href="/departments/databases-and-information-systems" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> D5 </span> </span> <span class="department-lnk__lbl"> Databases and Information Systems </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--d6 " href="/departments/visual-computing-and-artificial-intelligence" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> D6 </span> </span> <span class="department-lnk__lbl"> Visual Computing and Artificial Intelligence </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--rg1 " href="/departments/automation-of-logic" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> RG1 </span> </span> <span class="department-lnk__lbl"> Automation of Logic </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--rg2 " href="/departments/network-and-cloud-systems" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> RG2 </span> </span> <span class="department-lnk__lbl"> Network and Cloud Systems </span> </span> </a> </li> <li> <a class="department-lnk js-department-dd-lnk department-lnk--rg3 " href="/departments/mlp" target="" > <span class="department-lnk__ct"> <span class="department-lnk__icon"> <span class="department-lnk__id"> RG3 </span> </span> <span class="department-lnk__lbl"> Multimodal Language Processing </span> </span> </a> </li> </ul> <div class="department-dd__close-ct"> <a class="department-dd__close js-site-department-nav-close-lnk" role="button" title="" href="javascript:"> <svg width="12px" height="12px" viewBox="0 0 12 12" stroke="white" stroke-width="1"> <line x1="1" y1="1" x2="11" y2="11"></line> <line x1="1" y1="11" x2="11" y2="1"></line> </svg> </a> </div> </nav> <header class="site-header"> <div class="site-header__ct"> <div class="site-header__mob-ct"> <div class="site-header__logo-lnk-ct"> <a class="site-header__logo-lnk" href="/home"> <img class="site-header__logo" alt="Logo Max Planck Institute for Informatics" src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/Images/Core/mpi-logo-en.svg" width="1527" height="300" /> </a> <a class="site-header__department-lnk" href="/departments/algorithms-complexity"> <span class="site-header__department-lbl"> Algorithms and Complexity </span> </a> </div> <button class="site-header__nav-toggle js-toggle-mobile-nav" type="button" aria-label="Toggle navigation" > <svg width="40" height="40" viewBox="-25 -25 50 50"> <circle cx="0" cy="0" r="25" fill="none"></circle> <rect class="burgerline-1" x="-15" y="-12" width="30" height="4" fill="black"></rect> <rect class="burgerline-2" x="-15" y="-2" width="30" height="4" fill="black"></rect> <rect class="burgerline-3" x="-15" y="8" width="30" height="4" fill="black"></rect> </svg> </button> </div> <div class="site-header__mob-nav-ct js-mob-nav-ct"> <div class="site-header__mob-nav-ct-helper js-mob-nav-helper"> <div class="site-header__search"> <div class="tx-solr"> <div class="tx-solr-search-form"> <form method="get" id="tx-solr-search-form-pi-results" action="/search" data-suggest="/search?type=7384" data-suggest-header="Top Results" accept-charset="utf-8"> <input class="tx-solr-search-form__input js-solr-q" name="tx_solr[q]" placeholder="Search" value="" type="search" aria-label="Search" /> <button class="tx-solr-search-form__submit" aria-label="Search" type="submit"> <i class="mpg-icon mpg-icon-search" role="img" aria-hidden="true"></i> </button> </form> </div> </div> </div> <div class="site-header__main-nav"> <nav class="main-nav" id="nav"> <div class="main-nav__ct"> <ul class="main-nav__items"> <li class="main-nav__item js-main-nav-item has-children"> <a class=" has-children" href="/departments/algorithms-complexity/people/current-members" target="" > People </a> <button class="main-nav__expand-btn js-main-nav-expand" title="Toggle dropdown"> <span class="main-nav__expand-btn-wrap"> <i class="mpg-icon mpg-icon-down2"></i> </span> </button> <div class="site-nav__sub-menu js-main-nav-sub-menu"> <div class="site-nav__sub-menu-wrap js-main-nav-sub-menu-wrap"> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/people/current-members" target="" > Current Members </a> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/people/former-members" target="" > Former Members </a> </li> </ul> </div> </div> </div> </li> <li class="main-nav__item js-main-nav-item has-children"> <a class=" has-children" href="/departments/algorithms-complexity/research" target="" > Research </a> <button class="main-nav__expand-btn js-main-nav-expand" title="Toggle dropdown"> <span class="main-nav__expand-btn-wrap"> <i class="mpg-icon mpg-icon-down2"></i> </span> </button> <div class="site-nav__sub-menu js-main-nav-sub-menu"> <div class="site-nav__sub-menu-wrap js-main-nav-sub-menu-wrap"> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/research/algorithmic-game-theory" target="" > Algorithmic Game Theory </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/research/approximation-algorithms" target="" > Approximation Algorithms </a> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/research/fine-grained-complexity" target="" > Fine-Grained Complexity and Algorithm Design </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/research/graph-algorithms" target="" > Graph Algorithms </a> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/research/optimization" target="" > Optimization </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/research/parameterized-algorithms-and-complexity" target="" > Parameterized and Counting Algorithms and Complexity </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/research/robust-learning" target="" > Robust Learning </a> </li> </ul> </div> </div> </div> </li> <li class="main-nav__item js-main-nav-item has-children"> <a class=" has-children" href="/departments/algorithms-complexity/offers" target="" > Offers </a> <button class="main-nav__expand-btn js-main-nav-expand" title="Toggle dropdown"> <span class="main-nav__expand-btn-wrap"> <i class="mpg-icon mpg-icon-down2"></i> </span> </button> <div class="site-nav__sub-menu js-main-nav-sub-menu"> <div class="site-nav__sub-menu-wrap js-main-nav-sub-menu-wrap"> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/offers/postdoc" target="" > Postdoc Application </a> </li> </ul> </div> </div> </div> </li> <li class="main-nav__item js-main-nav-item has-children"> <a class=" has-children" href="/departments/algorithms-complexity/teaching" target="" > Teaching </a> <button class="main-nav__expand-btn js-main-nav-expand" title="Toggle dropdown"> <span class="main-nav__expand-btn-wrap"> <i class="mpg-icon mpg-icon-down2"></i> </span> </button> <div class="site-nav__sub-menu js-main-nav-sub-menu"> <div class="site-nav__sub-menu-wrap js-main-nav-sub-menu-wrap"> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter-2024/25" target="" > Winter 2024/25 </a> <ul class="sub-menu sub-menu--lvl-2"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="https://cms.sic.saarland/gralgodat24/" target="" > Introduction to Algorithms and Data Structures </a> </li> </ul> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer24" target="" > Summer 2024 </a> <ul class="sub-menu sub-menu--lvl-2"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="https://cms.sic.saarland/finegrained24/" target="" > Fine-Grained Complexity Theory </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer24/fair-div-game-theory" target="" > Topics in Computational Social Choice Theory </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer24/discrete-optimization" target="" > Discrete Optimization </a> </li> </ul> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter23" target="" > Winter 2023/24 </a> <ul class="sub-menu sub-menu--lvl-2"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="https://cms.sic.saarland/algodat23/" target="" > Algorithms and Data Structures </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="https://cms.sic.saarland/sublinear23/" target="" > Sublinear Algorithms </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="https://cms.sic.saarland/ideen2324/" target="" > Ideen und Konzepte der Informatik </a> </li> </ul> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer23" target="" > Summer 2023 </a> <ul class="sub-menu sub-menu--lvl-2"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer23/counting" target="" > Techniques for Counting Problems </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="https://cms.cispa.saarland/paramalg_23/" target="" > Parametrized Algorithms (external) </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer23/ml-foundations" target="" > Seminar: Foundations of Machine Learning </a> </li> </ul> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter22" target="" > Winter 2022/23 </a> <ul class="sub-menu sub-menu--lvl-2"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter22/random" target="" > Randomized Algorithms and Probabilistic Analysis of Algorithms </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter22/approx" target="" > Approximation Algorithms </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter22/ideen" target="" > Ideen und Konzepte der Informatik </a> </li> </ul> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer22" target="" > Summer 2022 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter21" target="" > Winter 2021/22 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer21" target="" > Summer 2021 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter20" target="" > Winter 2020/21 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer20" target="" > Summer 2020 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter19" target="" > Winter 2019/20 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer19" target="" > Summer 2019 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/winter18" target="" > Winter 2018/19 </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/teaching/summer18" target="" > Summer 2018 </a> </li> </ul> </div> </div> </div> </li> <li class="main-nav__item js-main-nav-item has-children"> <a class=" has-children" href="/departments/algorithms-complexity/seminars" target="" > Seminars </a> <button class="main-nav__expand-btn js-main-nav-expand" title="Toggle dropdown"> <span class="main-nav__expand-btn-wrap"> <i class="mpg-icon mpg-icon-down2"></i> </span> </button> <div class="site-nav__sub-menu js-main-nav-sub-menu"> <div class="site-nav__sub-menu-wrap js-main-nav-sub-menu-wrap"> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/seminars/algorithms-with-predictions" target="" > Algorithms with Predictions </a> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/quantum-lecture-series" target="" > Quantum Lecture Series </a> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/virtual-theory-seminar" target="" > Virtual Theory Seminar </a> </li> </ul> </div> </div> </div> </li> <li class="main-nav__item js-main-nav-item has-children"> <a class=" has-children" href="/departments/algorithms-complexity/publications" target="" > Publications </a> <button class="main-nav__expand-btn js-main-nav-expand" title="Toggle dropdown"> <span class="main-nav__expand-btn-wrap"> <i class="mpg-icon mpg-icon-down2"></i> </span> </button> <div class="site-nav__sub-menu js-main-nav-sub-menu"> <div class="site-nav__sub-menu-wrap js-main-nav-sub-menu-wrap"> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/publications/current-year" target="" > Current Year </a> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/publications/last-year" target="" > Last Year </a> </li> </ul> </div> <div class="site-nav__sub-menu-column"> <ul class="sub-menu sub-menu--lvl-1"> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/publications/the-year-before-last" target="" > The Year Before Last </a> </li> <li class="sub-menu__itm"> <a class="sub-menu__lnk " href="/departments/algorithms-complexity/publications/reports" target="" > Reports </a> </li> </ul> </div> </div> </div> </li> <li class="main-nav__item js-main-nav-item "> <a class=" " href="/departments/algorithms-complexity/adfocs" target="" > ADFOCS </a> </li> <li class="main-nav__item js-main-nav-item "> <a class=" " href="/departments/algorithms-complexity/news" target="" > News </a> </li> </ul> </div> </nav> </div> <div class="site-header__lang-switch"> <a title="Seite auf Deutsch anzeigen" href="/de/departments/algorithms-complexity">Deutsch</a> </div> </div> </div> </div> </header> <!--TYPO3SEARCH_begin--> <nav class="breadcrumb"> <div class="breadcrumb__ct"> <ol class="breadcrumb__items"> <li class="breadcrumb__item is-first is-sec-to-last " > <a class="breadcrumb__link" href="/departments" title="Departments"> <span class="breadcrumb__lbl">Departments</span> </a> </li> <li class="breadcrumb__item is-last is-active" > <span class="breadcrumb__lbl">Algorithms and Complexity</span> </li> </ol> </div> </nav> <main id="main" class="site__body "> <div class="site__main"> <div id="c28884" class="content content--text content--layout-0 has-header frame--default content--bg-none"><div class="content__ct"><div class="content__wrap"><header class="content__hd"><h1 class="content__ttl "> Department 1: Algorithms and Complexity </h1></header><div class="content__bd"><p>The department investigates a broad range of theoretical and practical aspects of modern algorithmics. We design new algorithms and algorithmic techniques, analyze their efficiency and the quality of their solutions, develop provably efficient and correct software, and package our programs in software libraries. The strength of our approach lies in the fact that we consider these aspects in unity and not in isolation.</p><h3>Headed by Prof. Danupon Na Nongkai, PhD.</h3></div></div></div></div> <div id="c4711" class="content content--menu_abstract content--layout-12 has-header frame--bg content--bg-none"><div class="content__ct"><div class="content__wrap"><header class="content__hd"><h2 class="content__ttl "> Research Areas </h2></header><div class="content__bd"><ul class="page-grid"><li class="page-grid__item has-abstract"><div class="page-grid-item js-page-grid-item"><h3 class="page-grid-item__ttl"><a href="/departments/algorithms-complexity/research/algorithmic-game-theory" title="Algorithmic Game Theory" class="page-grid-item__ttl-lnk" target=""> Algorithmic Game Theory </a></h3><div class="page-grid-item__abstract js-page-grid-item-abstract"><p> In the problems we consider in this group, we usually try to optimize some goal function while dealing with selfish agents that may have separate and conflicting goals, and that may lie to us in order to improve their own goal function. In algorithmic mechanism design, we ensure that it is in the best interest of the agents to tell us the truth. We also examine the price of anarchy and price of stability for various problems. <span class="js-page-grid-item-abstract-collapse-tester"></span></p></div><a href="javascript:" class="page-grid-item__abstract-toggle link-more link-more--expand is-collapsed js-page-grid-item-abstract-toggle" role="button" data-more="more" data-less="less"> more </a></div><a href="/departments/algorithms-complexity/research/algorithmic-game-theory" title="Algorithmic Game Theory" class="page-grid-item__more-button btn mob-full-width" target=""> More information </a></li><li class="page-grid__item has-abstract"><div class="page-grid-item js-page-grid-item"><h3 class="page-grid-item__ttl"><a href="/departments/algorithms-complexity/research/approximation-algorithms" title="Approximation Algorithms" class="page-grid-item__ttl-lnk" target=""> Approximation Algorithms </a></h3><div class="page-grid-item__abstract js-page-grid-item-abstract"><p> Most interesting optimization problems are NP-Hard. For such problems, unless P=NP, exact algorithms cannot be efficient. In the field of approximation algorithms, we take the reverse perspective: efficient algorithms cannot be exact. But if we naturally insist on efficient algorithms, how close can we get to an optimal solution? In this group we design efficient algorithms with provable guarantees on the distance between their output and the (unknown) optimal solution. Complementing this, we are also studying the limits of such algorithms. <span class="js-page-grid-item-abstract-collapse-tester"></span></p></div><a href="javascript:" class="page-grid-item__abstract-toggle link-more link-more--expand is-collapsed js-page-grid-item-abstract-toggle" role="button" data-more="more" data-less="less"> more </a></div><a href="/departments/algorithms-complexity/research/approximation-algorithms" title="Approximation Algorithms" class="page-grid-item__more-button btn mob-full-width" target=""> More information </a></li><li class="page-grid__item has-abstract"><div class="page-grid-item js-page-grid-item"><h3 class="page-grid-item__ttl"><a href="/departments/algorithms-complexity/research/fine-grained-complexity" title="Fine-Grained Complexity and Algorithm Design" class="page-grid-item__ttl-lnk" target=""> Fine-Grained Complexity and Algorithm Design </a></h3><div class="page-grid-item__abstract js-page-grid-item-abstract"><p> Fine-grained Complexity Theory is the design of reductions that prove running time lower bounds assuming a plausible complexity-theoretic conjecture such as the Strong Exponential Time Hypothesis. In this area the design of efficient algorithms goes hand in hand with proving fine-grained lower bounds: our goal is to prove matching upper and lower bounds, thus establishing best-possible algorithms, that achieve the optimal constant in the exponent of the running time. We apply this methodology to problems from various domains such as graphs, strings, geometry and optimization. <span class="js-page-grid-item-abstract-collapse-tester"></span></p></div><a href="javascript:" class="page-grid-item__abstract-toggle link-more link-more--expand is-collapsed js-page-grid-item-abstract-toggle" role="button" data-more="more" data-less="less"> more </a></div><a href="/departments/algorithms-complexity/research/fine-grained-complexity" title="Fine-Grained Complexity and Algorithm Design" class="page-grid-item__more-button btn mob-full-width" target=""> More information </a></li><li class="page-grid__item has-abstract"><div class="page-grid-item js-page-grid-item"><h3 class="page-grid-item__ttl"><a href="/departments/algorithms-complexity/research/graph-algorithms" title="Graph Algorithms" class="page-grid-item__ttl-lnk" target=""> Graph Algorithms </a></h3><div class="page-grid-item__abstract js-page-grid-item-abstract"><p> Our long-term vision is to develop techniques for designing efficient聽graph algorithms and use them to understand graph data.聽 We currently focus on algorithms that work across many models of computation,聽such as dynamic, distributed, streaming, parallel, and quantum聽algorithms. We aim to achieve two goals simultaneously: (i) solutions聽to notorious long-standing open problems, and (ii) efficient algorithms聽that can fully exploit both the features of modern computing devices聽and the characteristics of contemporary data. <span class="js-page-grid-item-abstract-collapse-tester"></span></p></div><a href="javascript:" class="page-grid-item__abstract-toggle link-more link-more--expand is-collapsed js-page-grid-item-abstract-toggle" role="button" data-more="more" data-less="less"> more </a></div><a href="/departments/algorithms-complexity/research/graph-algorithms" title="Graph Algorithms" class="page-grid-item__more-button btn mob-full-width" target=""> More information </a></li><li class="page-grid__item has-abstract"><div class="page-grid-item js-page-grid-item"><h3 class="page-grid-item__ttl"><a href="/departments/algorithms-complexity/research/optimization" title="Optimization" class="page-grid-item__ttl-lnk" target=""> Optimization </a></h3><div class="page-grid-item__abstract js-page-grid-item-abstract"><p> Many real world applications are naturally formulated as combinatorial optimization problems, i.e. problems of finding the best solution(s) out of a finite set. Various methods have been developed to tackle such problems: integer programming, fixed-parameter tractable and exact algorithms, approximation algorithms and combinatorial algorithms, among others. D1 works on applying these methods to various problems from different areas, ranging from bioinformatics to geometry, to scheduling, and several others. <span class="js-page-grid-item-abstract-collapse-tester"></span></p></div><a href="javascript:" class="page-grid-item__abstract-toggle link-more link-more--expand is-collapsed js-page-grid-item-abstract-toggle" role="button" data-more="more" data-less="less"> more </a></div><a href="/departments/algorithms-complexity/research/optimization" title="Optimization" class="page-grid-item__more-button btn mob-full-width" target=""> More information </a></li><li class="page-grid__item has-abstract"><div class="page-grid-item js-page-grid-item"><h3 class="page-grid-item__ttl"><a href="/departments/algorithms-complexity/research/parameterized-algorithms-and-complexity" title="Parameterized and Counting Algorithms and Complexity" class="page-grid-item__ttl-lnk" target=""> Parameterized and Counting Algorithms and Complexity </a></h3><div class="page-grid-item__abstract js-page-grid-item-abstract"><p> Parameterized complexity analyzes how different parameters of the input influence the complexity of hard algorithmic problems. The general goal is to show with fixed-parameter tractability results that the combinatorial explosion can be confined to certain well-defined parameters, or to understand why such algorithms are not possible.聽An interesting class of hard problems that we consider are counting problems (where the goal is to count all solutions), as they may allow for interesting phenomena that are not observed in the corresponding decision problems. <span class="js-page-grid-item-abstract-collapse-tester"></span></p></div><a href="javascript:" class="page-grid-item__abstract-toggle link-more link-more--expand is-collapsed js-page-grid-item-abstract-toggle" role="button" data-more="more" data-less="less"> more </a></div><a href="/departments/algorithms-complexity/research/parameterized-algorithms-and-complexity" title="Parameterized and Counting Algorithms and Complexity" class="page-grid-item__more-button btn mob-full-width" target=""> More information </a></li><li class="page-grid__item has-abstract"><div class="page-grid-item js-page-grid-item"><h3 class="page-grid-item__ttl"><a href="/departments/algorithms-complexity/research/robust-learning" title="Robust Learning" class="page-grid-item__ttl-lnk" target=""> Robust Learning </a></h3><div class="page-grid-item__abstract js-page-grid-item-abstract"><p> Machine learning algorithms have many applications. Can we theoretically prove they are consistent and helpful? We focus on two paradigms: algorithmic stability and algorithms with predictions. Stable algorithms, which can tolerate changes in their inputs, can inherit many desirable properties such as generalization, differential privacy, and replicability. Algorithms with predictions use their predictions to circumvent worst-case bounds when the predictions are good, and mitigate the effect of bad predictions <span class="js-page-grid-item-abstract-collapse-tester"></span></p></div><a href="javascript:" class="page-grid-item__abstract-toggle link-more link-more--expand is-collapsed js-page-grid-item-abstract-toggle" role="button" data-more="more" data-less="less"> more </a></div><a href="/departments/algorithms-complexity/research/robust-learning" title="Robust Learning" class="page-grid-item__more-button btn mob-full-width" target=""> More information </a></li></ul></div></div></div></div> <div id="c1543" class="content content--menu_abstract content--layout-0 has-header frame--default content--bg-none"><div class="content__ct"><div class="content__wrap"><header class="content__hd"><h2 class="content__ttl "> Overview </h2></header><div class="content__bd"><ul class="pages-menu pages-menu--layout-default"><li class="pages-menu__entry "><a href="/departments/algorithms-complexity/people/current-members" title="People" class="pages-menu__lnk" target=""><span class="pages-menu__page-ttl"> People </span></a></li><li class="pages-menu__entry "><a href="/departments/algorithms-complexity/research" title="Research" class="pages-menu__lnk" target=""><span class="pages-menu__page-ttl"> Research </span></a></li><li class="pages-menu__entry "><a href="/departments/algorithms-complexity/offers" title="Offers" class="pages-menu__lnk" target=""><span class="pages-menu__page-ttl"> Offers </span></a></li><li class="pages-menu__entry "><a href="/departments/algorithms-complexity/teaching" title="Teaching" class="pages-menu__lnk" target=""><span class="pages-menu__page-ttl"> Teaching </span></a></li><li class="pages-menu__entry "><a href="/departments/algorithms-complexity/seminars" title="Seminars" class="pages-menu__lnk" target=""><span class="pages-menu__page-ttl"> Seminars </span></a></li><li class="pages-menu__entry "><a href="/departments/algorithms-complexity/publications" title="Publications" class="pages-menu__lnk" target=""><span class="pages-menu__page-ttl"> Publications </span></a></li><li class="pages-menu__entry "><a href="/departments/algorithms-complexity/adfocs" title="ADFOCS" class="pages-menu__lnk" target=""><span class="pages-menu__page-ttl"> ADFOCS </span></a></li><li class="pages-menu__entry "><a href="/departments/algorithms-complexity/news" title="News" class="pages-menu__lnk" target=""><span class="pages-menu__page-ttl"> News </span></a></li></ul></div></div></div></div> </div> </main> <!--TYPO3SEARCH_end--> <footer class="site__footer"> <div class="site-footer__to-top-lnk-ct js-to-top-btn-ct"> <a class="site-footer__to-top-lnk js-to-top-btn js-scroll-lnk" role="button" href="#top"><span class="site-footer__to-top-lnk-lbl">Top</span></a> </div> <div class="site-footer site-footer--contact"> <div class="site-footer__ct"> <div class="site-footer__row"> <section class="site-footer__sec site-footer__sec--quick-links js-collapse-ct"> <h2 class="site-footer__sec-ttl"> <a href="javascript:" role="button" class="site-footer__sec-ttl-lnk js-collapse-toggle is-collapsed"> Quick Links <i class="site-footer__sec-expand-icon mpg-icon mpg-icon-down2"></i> </a> </h2> <div class="site-footer__sec-bd site-footer-links js-collapse-target-ct is-collapsed"> <div class="js-collapse-target"> <div id="c22759" class="content content--menu_pages content--layout-10 has-no-header frame--default content--bg-none"><div class="content__ct"><div class="content__wrap"><div class="content__bd"><ul><li><a href="/institute/address" target="" title="Location" class=""><span>Location</span></a></li><li><a href="/news/latest" target="" title="Press" class=""><span>Press</span></a></li><li><a href="/covid-19" target="" title="COVID-19" class=""><span>COVID-19</span></a></li></ul></div></div></div></div> </div> </div> </section> <section class="site-footer__sec site-footer__sec--social-media js-collapse-ct"> </section> <div class="site-footer__sec site-footer__sec--quick-actions"> <div id="c22761" class="content content--text content--layout-0 has-no-header frame--default content--bg-none"><div class="content__ct"><div class="content__wrap"><div class="content__bd"><p><a href="mailto:kontakt@mpi-inf.mpg.de" class="button">Contact</a></p></div></div></div></div> </div> </div> </div> </div> <div class="site-footer site-footer--legal"> <div class="site-footer__ct"> <div class="site-footer__row"> <div class="site-footer__sec site-footer__org"> <img class="site-footer__org-img" alt="Bildmarke Max Planck Gesellschaft" src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/Images/Core/mpg-bildmarke_w.svg" width="160" height="160" /> <div class="site-footer__org-lbl"> Max-Planck-Gesellschaft </div> </div> <div class="site-footer__sec site-footer__legal-links"> <div id="c22763" class="content content--menu_pages content--layout-10 has-no-header frame--default content--bg-none"><div class="content__ct"><div class="content__wrap"><div class="content__bd"><ul><li><a href="/sitemap" target="" title="Sitemap" class=""><span>Sitemap</span></a></li><li><a href="https://imprint.mpi-klsb.mpg.de/inf/www.mpi-inf.mpg.de" target="" title="Imprint" class=""><span>Imprint</span></a></li><li><a href="https://data-protection.mpi-klsb.mpg.de/inf/www.mpi-inf.mpg.de" target="" title="Data Protection" class=""><span>Data Protection</span></a></li></ul></div></div></div></div> </div> <div class="site-footer__sec site-footer__copyright"> 漏 2024, Max-Planck-Gesellschaft </div> </div> </div> </div> </footer> <script src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/JavaScript/Libraries/jquery-1.12.4.min.js?1725541122"></script> <script src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/JavaScript/Libraries/jquery-ui-1.13.2.min.js?1725541122"></script> <script src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/JavaScript/Libraries/swiper-bundle-8.4.6.min.js?1725541122"></script> <script src="/typo3conf/ext/powermail/Resources/Public/JavaScript/Powermail/Form.min.js?1726560232" defer="defer"></script> <script src="/typo3conf/ext/mpi_inf_site_package/Resources/Public/JavaScript/Build/main.js?1725541122"></script> </body> </html>