TOP
Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminare
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Publishing
Innerhalb dieser Seite:
Externe Seiten:
dblp
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp


Dagstuhl-Seminar 17041

Randomization in Parameterized Complexity

( 22. Jan – 27. Jan, 2017 )

(zum Vergrößern in der Bildmitte klicken)

Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite: https://www.dagstuhl.de/17041

Organisatoren

Kontakt



Programm

Motivation

Randomization plays a prominent role in many subfields of theoretical computer science. Typically, this role is twofold: On the one hand, randomized methods can be used to solve essentially classical problems easier or more efficiently. In many cases, this allows for simpler, faster, and more appealing solutions for problems that have rather elaborate deterministic algorithms; in other cases, randomization provides the only known way to cope with the problem (e.g. polynomial identity testing, or deciding whether there exists a perfect matching with exactly b red edges in an edge-colored bipartite graph). On the other hand, there are also cases where randomness is intrinsic to the question being asked, such as the study of properties of random objects, and the search for algorithms which are efficient on average for various input distributions.

Parameterized complexity is an approach of handling computational intractability, where the main idea is to analyze the complexity of problems in finer detail by considering additional problem parameters beyond the input size. This area has enjoyed much success in recent years, and has yielded several new algorithmic approaches that help us tackle computationally challenging problems. While randomization already has an important role in parameterized complexity, for instance in techniques such as color-coding or randomized contractions, there is a common opinion within researchers of the field that the full potential of randomization has yet to be fully tapped.

In this seminar we hope to help bridge this gap, by bringing together experts in the areas of randomized algorithms and parameterized complexity. In doing so, we hope to:

  • Establish domains for simpler and/or more efficient FPT algorithms via randomization.
  • Identify problems which intrinsically need randomization.
  • Study parameterized problems whose instances are generated by some underlying distribution.
  • Stimulate the development of a broadened role of randomness within parameterized complexity.
Copyright Marek Cygan, Fedor V. Fomin, Danny Hermelin, and Magnus Wahlström

Summary

Randomization plays a prominent role in many subfields of theoretical computer science. Typically, this role is twofold: On the one hand, randomized methods can be used to solve essentially classical problems easier or more efficiently. In many cases, this allows for simpler, faster, and more appealing solutions for problems that have rather elaborate deterministic algorithms; in other cases, randomization provides the only known way to cope with the problem (e.g. polynomial identity testing, or deciding whether there exists a perfect matching with exactly b red edges in an edge-colored bipartite graph). On the other hand, there are also cases where randomness is intrinsic to the question being asked, such as the study of properties of random objects, and the search for algorithms which are efficient on average for various input distributions.

Parameterized complexity is an approach of handling computational intractability, where the main idea is to analyze the complexity of problems in finer detail by considering additional problem parameters beyond the input size. This area has enjoyed much success in recent years, and has yielded several new algorithmic approaches that help us tackle computationally challenging problems. While randomization already has an important role in parameterized complexity, for instance in techniques such as color-coding or randomized contractions, there is a common opinion within researchers of the field that the full potential of randomization has yet to be fully tapped.

The goal of this seminar was to help bridge this gap, by bringing together experts in the areas of randomized algorithms and parameterized complexity. In doing so, we hope to:

  • Establish domains for simpler and/or more efficient FPT algorithms via randomization.
  • Identify problems which intrinsically need randomization.
  • Study parameterized problems whose instances are generated by some underlying distribution.
  • Stimulate the development of a broadened role of randomness within parameterized complexity.
Copyright Marek Cygan, Fedor V. Fomin, Danny Hermelin, and Magnus Wahlström

Teilnehmer
  • Amir Abboud (Stanford University, US) [dblp]
  • Arturs Backurs (MIT - Cambridge, US) [dblp]
  • Andreas Björklund (Lund University, SE) [dblp]
  • Édouard Bonnet (Middlesex University, GB) [dblp]
  • Cornelius Brand (Universität des Saarlandes, DE) [dblp]
  • Karl Bringmann (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Yixin Cao (Hong Kong Polytechnic University, CN) [dblp]
  • Radu Curticapean (Hungarian Academy of Sciences - Budapest, HU) [dblp]
  • Marek Cygan (University of Warsaw, PL) [dblp]
  • Holger Dell (Universität des Saarlandes, DE) [dblp]
  • Fedor V. Fomin (University of Bergen, NO) [dblp]
  • Tobias Friedrich (Hasso-Plattner-Institut - Potsdam, DE) [dblp]
  • Petr A. Golovach (University of Bergen, NO) [dblp]
  • Gregory Z. Gutin (Royal Holloway University of London, GB) [dblp]
  • Danny Hermelin (Ben Gurion University - Beer Sheva, IL) [dblp]
  • Petr Hlinený (Masaryk University - Brno, CZ) [dblp]
  • Petteri Kaski (Aalto University, FI) [dblp]
  • Eun Jung Kim (University Paris-Dauphine, FR) [dblp]
  • Yiannis Koutis (University of Puerto Rico - Rio Piedras, PR) [dblp]
  • Lukasz Kowalik (University of Warsaw, PL) [dblp]
  • Stefan Kratsch (Universität Bonn, DE) [dblp]
  • Bingkai Lin (National Institute of Informatics - Tokyo, JP) [dblp]
  • Daniel Lokshtanov (University of Bergen, NO) [dblp]
  • Dániel Marx (Hungarian Academy of Sciences - Budapest, HU) [dblp]
  • Jesper Nederlof (TU Eindhoven, NL) [dblp]
  • Fahad Panolan (University of Bergen, NO) [dblp]
  • Christophe Paul (CNRS - Montpellier, FR) [dblp]
  • Geevarghese Philip (Chennai Mathematical Institute, IN) [dblp]
  • Marcin Pilipczuk (University of Warsaw, PL) [dblp]
  • Michal Pilipczuk (University of Warsaw, PL) [dblp]
  • Peter Rossmanith (RWTH Aachen, DE) [dblp]
  • Marc Roth (Universität des Saarlandes, DE) [dblp]
  • Saket Saurabh (The Institute of Mathematical Sciences, India, IN) [dblp]
  • Ildikó Schlotter (Budapest University of Technology & Economics, HU) [dblp]
  • Ramanujan Sridharan (TU Wien, AT) [dblp]
  • Stefan Szeider (TU Wien, AT) [dblp]
  • Dimitrios M. Thilikos (University of Athens, GR) [dblp]
  • Magnus Wahlström (Royal Holloway University of London, GB) [dblp]
  • Gerhard J. Woeginger (RWTH Aachen, DE) [dblp]
  • David P. Woodruff (IBM Almaden Center - San Jose, US) [dblp]
  • Meirav Zehavi (University of Bergen, NO) [dblp]

Verwandte Seminare
  • Dagstuhl-Seminar 19041: New Horizons in Parameterized Complexity (2019-01-20 - 2019-01-25) (Details)
  • Dagstuhl-Seminar 24411: New Tools in Parameterized Complexity: Paths, Cuts, and Decomposition (2024-10-06 - 2024-10-11) (Details)

Klassifikation
  • data structures / algorithms / complexity
  • networks

Schlagworte
  • Parameterized complexity
  • fixed-parameter tractability
  • randomness
  • intractability