Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

Beide Seiten der vorigen Revision Vorhergehende Überarbeitung | |||

en:staff:stefankratsch [2015/04/11 12:43] kratsch [Prof. Dr. Stefan Kratsch] |
en:staff:stefankratsch [2015/10/27 15:44] (aktuell) kratsch |
||
---|---|---|---|

Zeile 6: | Zeile 6: | ||

|::: |::: | Email |kratsch@cs.uni-bonn.de|:::| | |::: |::: | Email |kratsch@cs.uni-bonn.de|:::| | ||

|Office Hours|by appointment |||| | |Office Hours|by appointment |||| | ||

- | |||

- | Until this webpage is fully set up please refer also to [[http://www.user.tu-berlin.de/stefan.kratsch/|my old homepage at TU Berlin]]. | ||

===== Research Interests ===== | ===== Research Interests ===== | ||

Zeile 17: | Zeile 15: | ||

* Computational complexity | * Computational complexity | ||

+ | ===== Current lectures ===== | ||

+ | |||

+ | * [[lehre:ws1516:advanced_algorithms|MA-INF 1104 - Advanced Algorithms]] | ||

+ | * [[lehre:ws1516:seminar_parameterized_complexity|MA-INF 1212 - Seminar Parameterized Complexity]] | ||

+ | * [[lehre:ws1516:lab_parameterized_complexity|MA-INF 1317 - Lab Parameterized Complexity]] | ||

===== Upcoming lectures ===== | ===== Upcoming lectures ===== | ||

- | |||

- | **SS 2015 Seminar on Parameterized Complexity ** | ||

- | * We will have the first meeting in the second week of the lecture period on Monday April 13 at 14:30-16:00 in room S.08 of the LBH building. | ||

- | * During this first and maybe a second meeting each participant will receive a paper about which he/she will give a talk at the end of the term. | ||

- | * We will probably have a few longer meetings at the end of the term when the talks are given. | ||

- | * Time slots after the initial meetings and before the talks will be used to discuss the paper/slides in preparation. | ||

- | * It will be possible to follow enough of the lecture "Parameterized Complexity" before giving a talk. Thus it is feasible to attend both seminar and lecture even if the topic is new to you. | ||

- | |||

- | ** SS 2015 Parameterized Complexity ** | ||

- | |||

- | * 4h of lecture and 2h of exercises per week, lecture is given in English, oral exam at end of term | ||

- | * Parameterized complexity takes an alternative, more fine-grained perspective on NP-hard/complete problems: | ||

- | - Example: It is significantly easier to determine whether a graph has a vertex cover of size at most k (a set of vertices touching all edges) than to tell whether it has an independent set of size at least k (a set of vertices that are mutually non-adjacent) | ||

- | - This is in contrast to the theory of NP-completeness which posits that Vertex Cover and Independent Set are equivalent under polynomial-time reductions. | ||

- | - The crux in this difference lies in insisting on a small value of the solution size k. Such //parameters// can strongly impact the time and space needed to solve hard problems. | ||

- | * The lecture introduces a diverse toolbox of algorithmic techniques with which a variety of problems can be tackled. | ||

- | * We will also discuss tools for establishing that certain parameterized algorithms are likely to be optimal in runtime. | ||

- | |||

- | **WS 2015/16: Advanced Algorithms (tentative)** | ||

- | * 4h of lecture and 2h of exercises per week, lecture is given in English, oral exam at end of term | ||

- | * The lecture attempts to give an overview over a wide range of algorithmic topics beyond the scope of the bachelor algorithmic lectures. | ||

- | * Nevertheless, some important topics will be briefly recapped to ease the start into this and maybe further algorithmic lectures in the computer science master. | ||

- | * Topics (tentative): | ||

- | - Flows, matchings, and linear programs | ||

- | - Approximation algorithms | ||

- | - Exact exponential-time algorithms | ||

- | - Online algorithms | ||

- | - Smoothed complexity analysis | ||

- | - more to come! | ||

**SS 2016: Computational Complexity (tentative)** | **SS 2016: Computational Complexity (tentative)** | ||

Zeile 60: | Zeile 34: | ||

- Randomized computation | - Randomized computation | ||

- As time permits: Interactive proofs, Cryptography, PCP theorem and hardness of approximation | - As time permits: Interactive proofs, Cryptography, PCP theorem and hardness of approximation | ||

+ | |||

+ | **SS 2016 Parameterized Complexity (tentative)** | ||

+ | |||

+ | * 4h of lecture and 2h of exercises per week, lecture is given in English, oral exam at end of term | ||

+ | * Parameterized complexity takes an alternative, more fine-grained perspective on NP-hard/complete problems: | ||

+ | - Example: It is significantly easier to determine whether a graph has a vertex cover of size at most k (a set of vertices touching all edges) than to tell whether it has an independent set of size at least k (a set of vertices that are mutually non-adjacent) | ||

+ | - This is in contrast to the theory of NP-completeness which posits that Vertex Cover and Independent Set are equivalent under polynomial-time reductions. | ||

+ | - The crux in this difference lies in insisting on a small value of the solution size k. Such //parameters// can strongly impact the time and space needed to solve hard problems. | ||

+ | * The lecture introduces a diverse toolbox of algorithmic techniques with which a variety of problems can be tackled. | ||

+ | * We will also discuss tools for establishing that certain parameterized algorithms are likely to be optimal in runtime. | ||

===== Brief Curriculum Vitae ===== | ===== Brief Curriculum Vitae ===== | ||

Zeile 67: | Zeile 51: | ||

|September 2012 - October 2012|Postdoc at Max-Planck-Institute for Informatics| | |September 2012 - October 2012|Postdoc at Max-Planck-Institute for Informatics| | ||

|September 2010 - October 2012|Postdoc at Utrecht University working with Hans L. Bodlaender| | |September 2010 - October 2012|Postdoc at Utrecht University working with Hans L. Bodlaender| | ||

- | |March 2008 - August 2012|PhD student at Max-Planck-Institute for Informatics in Saarbrücken supervised by Kurt Mehlhorn| | + | |March 2008 - August 2010|PhD student at Max-Planck-Institute for Informatics in Saarbrücken supervised by Kurt Mehlhorn| |

|October 2002 - February 2008|Studies in Computer Science at Friedrich-Schiller University in Jena| | |October 2002 - February 2008|Studies in Computer Science at Friedrich-Schiller University in Jena| | ||

===== Scientific activities ===== | ===== Scientific activities ===== | ||

- | === Program committee participation === | + | === Program/Steering committee participation === |

== Current: == | == Current: == | ||

- | * PC member of [[http://algo2015.upatras.gr/ipec/|IPEC 2015]] | + | * Member of IPEC steering committee from 2016 to 2019 |

== Previous: == | == Previous: == | ||

- | * PC member of [[http://www.inf.u-szeged.hu/mfcs2014/|MFCS 2014]], [[http://stacs2014.sciencesconf.org/|STACS 2014]], [[http://www.csis.hku.hk/isaac2013/|ISAAC 2013]], [[http://www.fsttcs.org/|FSTTCS 2012]], and [[http://ipec2012.isoftcloud.gr/|IPEC 2012]] | + | * PC member of [[http://algo2015.upatras.gr/ipec/|IPEC 2015]], [[http://www.inf.u-szeged.hu/mfcs2014/|MFCS 2014]], [[http://stacs2014.sciencesconf.org/|STACS 2014]], [[http://www.csis.hku.hk/isaac2013/|ISAAC 2013]], [[http://www.fsttcs.org/|FSTTCS 2012]], and [[http://ipec2012.isoftcloud.gr/|IPEC 2012]] |

===== Publications ===== | ===== Publications ===== | ||

An up to date list of my publications can be found at [[http://dblp.org/search/index.php#query=author:stefan_kratsch:&qp=H1.89:W1.1:F1.4:F2.4:F3.4:F4.4|dblp.org]]. | An up to date list of my publications can be found at [[http://dblp.org/search/index.php#query=author:stefan_kratsch:&qp=H1.89:W1.1:F1.4:F2.4:F3.4:F4.4|dblp.org]]. |

en/staff/stefankratsch.txt · Zuletzt geändert: 2015/10/27 15:44 von kratsch