Uni-Logo
Algorithms and Complexity
 

Welcome


Welcome to the Algorithms and Complexity group headed by Fabian Kuhn.

Computer systems of the future will be highly networked and decentralized. We study the mathematical Network - Edge Coloring foundations and algorithmc challenges of large-scale parallel and distributed systems:

  • Complexity of parallel and distributed computations

  • Theoretical foundations of networks and distributed system

  • Algorithms for wireless networks, peer-to-peer networks, dynamic networks, social networks, multicore computers, ...

Open Positions

We are always looking for talented PhD students.

News

  • Salwa Faour and Fabian Kuhn received the best paper award of OPODIS 2020 for their paper Approximating Bipartite Minimum Vertex Cover in the CONGEST Model.
  • For his Ph.D. thesis, our former Ph.D. student Yannic Maus was awarded the 2018 dissertation award of the German Informatics Society (GI Preis) and the 2019 Wolfgang-Gentner-Nachwuchsförderpreis of the Faculty of Engineering of the University of Freiburg. Congratulations!
  • Our former postdoc Jara Uitto joins the computer science department of Aalto University in Finland as an assistant professor. Congratulations!
  • Our group member Yannic Maus defended his Ph.D. thesis "The Power of Locality: Exploring the Limits of Randomness in Distributed Computing" on 12.10.2018. Congratulations!
  • Our group member Hamid Ghodselahi defended his Ph.D. thesis "Serving Online Requests with Mobile Resources" on 9.7.2018. Congratulations!
  • Fabian Kuhn gave invited presentations about the role of randomization in local distributed algorithms at HALG 2018 and at WOLA 2018. A version of the talk given at the computer science colloquium of ETH Zurich is available online.
  • Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto received the best paper award of DISC 2017 for their paper Improved Distributed Degree Splitting and Edge Coloring.
  • Dan Hefetz, Fabian Kuhn, Yannic Maus, and Angelika Steger received the best paper award of DISC 2016 for their paper Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model.
  • Sebastian Daum, Fabian Kuhn, and Yannic Maus received the best paper award of SIROCCO 2016 for their paper Rumor Spreading with Bounded In-Degree.
  • Our group member Sebastian Daum defended his Ph.D. thesis "The Power of Frequency Hopping and Information Dissemination in Constrained Communication Models" on 12.10.2015. Congratulations!
  • Fabian Kuhn gave a keynote presentation about a distributed perspective on graph connectivity and cuts at SPAA 2014
  • Mohsen Ghaffari and Fabian Kuhn received the best paper award of DISC 2013 for their paper Distributed Minimum Cut Approximation.
  • Fabian Kuhn received an ERC Starting Grant on Algorithms and Complexity of Highly Decentralized Computations in 2013.
  • Fabian Kuhn joined the University of Freiburg as head of the Chair of Algorithms and Complexity on 1.4.2012.