Link zu dieser Vergleichsansicht

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

Benutzer-Werkzeuge