Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

Computational Complexity - Research Seminar

Time: Every other Thursday, 4pm (sharp)
Location:Room 107, Building E1.3
[mailinglist for talk announcements]

Upcoming Talks

Previous Talks

Summer Term 2017

03.03.2017 Cornelius Brand The nondeterministic strong exponential time hypothesis

Summer Term 2014

01.10.2014 Marc Roth Complexity of Counting Problems on Line Graphs

Winter Term 2013/2014

26.03.2014 Abdullah Heyari A Smoothed Analytic Approach to the Integer Factoring Problem
20.01.2014 Stefan Klos Smoothed Analyse einer Heuristik für das dreidimensionale Zuordnungsproblem
05.11.2013 Bodo Manthey
(University of Twente)
Probabilistic Analysis of Power Assignments
04.11.2013 Alexey Pospelov
(Yandex, Russland)
Multiplication of polynomials

Winter Term 2012/2013

25.02.2013 Balagopal Komarath Pebbling Entropy and Branching Programs Size Lower Bounds
25.10.2012 Reinhard Weyand Implementation of exact algorithms for the cover polynomial

Summer Term 2012

28.09.2012 Marvin Künnemann A Quantization Framework for Smoothed Analysis on Euclidean Optimization Problems

Winter Term 2011/2012

04.04.2012 Radu Curticapean Parameterized counting complexity
08.03.2012 Tobias Mömke
(KTH Stockholm)
Approximationg Graphic TSP by Matchings

Summer Term 2011

15.09.2011 Prof. A. Voronenko
(Moscow State University)
Complexity of read-once functions
08.09.2011 M. Grohe
(Humboldt University Berlin)
From Local to Global Structure Theorems
13.07.2011 B. Chokaev
(Moscow State University)
Bilinear versus Multiplicative Complexity
09.05.2011 Christian Engels Random Metrics

Winter Term 2010/2011

05.04.2011 Radu Curticapean Short proofs for unsatisfiability of dense random 3CNF formulas
15.03.2011 Maurice Jansen Deterministic Black-Box Identity Testing Ordered Algebraic Branching Programs
28.01.2011 Alexey Pospelov Fast Fourier transforms: An overview
02.01.2011 Alexey Pospelov Fast Fourier transforms: Exhaustive performance in restricted conditions
12.10.2010 Radu Curticapean Holographic Algorithms

Summer Term 2010

30.09.2010 Radu Curticapean Counting Perfect Matchings in Planar Graphs
27.09.2010 Stefan Schuh Experimental Validation of Yao's Conjecture
27.08.2010 Yaser Fazlollahi Smoothed Analysis of Euclidean Matching Algorithms
19.08.2010 J.A. Makowsky
(Haifa, Israel)
Logical interpretations of combinatorial functions
16.07.2010 Alexey Pospelov Faster Polynomial Multiplication and Limitations
14.07.2010 Alexey Pospelov Fast Polynomial Multiplication
28.04.2010 Raghavendra Rao Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in
16.04.2010 Christian Engels Polynomial Identity Testing

Winter Term 2009/2010

19.03.2010 Alexey Pospelov Bounds for bilinear complexity of noncommutative group algebras
29.10.2009 Oliver Putz Exact algorithms for TSP

Summer Term 2009

09.07.2009 Alexey Pospelov Multiplicative Complexity of Group Algebras
02.07.2009 Bodo Manthey Multi-Criteria TSP: Min and Max Combined
18.06.2009 Mahmoud Fouz Item Pricing with Partial Orders
08.06.2009 Kai Plociennik
(TU Chemnitz)
A Probabilistic PTAS for Shortest Common Superstring
28.05.2009 Bodo Manthey k-Means has Polynomial Smoothed Complexity

Winter Term 2008/2009

19.02.2009 Mahmoud Fouz Non-Single Minded Envy Free Profit Maximization
29.01.2009 Christian Hoffmann A Point-to-point Reduction for the Chromatic Polynomial Revisited
22.01.2009 Bodo Manthey On Approximating Multi-Criteria TSP
11.12.2008 Markus Bläser Median Find, Part 2 - Upper Bounds
04.12.2008 Markus Bläser Median Find, Part 1 - Lower Bounds
20.11.2008 Manuel Noll Proof of a Running Time Bound for Simulating a Quantum Machine on a Classical one via Jones Polynomi
13.11.2008 Bodo Manthey Smoothed Analysis of Selection: Why Finding the Maximum is Harder Than Finding the Median
06.11.2008 Open Problem Session
30.10.2008 Christian Hoffmann Computing the Interlace Polynomial Using Tree Decompositions
06.10.2008 Heiko Röglin
(Boston University)
Congestion Games: Optimization in Competition

Summer Term 2008

05.09.2008 Xinhui Wang
(University of Twente)
Exact Algorithms for the Steiner Tree Problem
15.07.2008 Laurent Lyaudet
(Université d'Orléans)
Graph Covers and Algebraic Complexity
08.07.2008 Bodo Manthey Improved Smoothed Analysis of k-Means Clustering II
01.07.2008 Stefan Schuh Smoothed Bounds for the Height of Binary Search Trees Using Perturbed Indices
24.06.2008 Bodo Manthey Improved Smoothed Analysis of k-Means Clustering I
17.06.2008 Open Problem Session
10.06.2008 Christian Hoffmann Solving Hard Graph Problems Using Tree Decompositions
03.06.2008 Markus Bläser An Introduction to Geometric Complexity Theory II
27.05.2008 Markus Bläser An Introduction to Geometric Complexity Theory I
20.05.2008 Christian Engels A Probabilistic Analysis of Karp's Partitioning Scheme for the Traveling Salesman Problem
13.05.2008 Nima Zeini Smoothed Lower Bound for Quicksort using Median-of-Three under Additive Noise II
06.05.2008 Nima Zeini Smoothed Lower Bound for Quicksort using Median-of-Three under Additive Noise I
29.04.2008 Holger Dell
(HU Berlin)
Strongly Vertex-Exponential Lower Bounds for the 0,1-Permanent
22.04.2008 Bodo Manthey Smoothed Analysis of k-Means Clustering

Winter Term 2007/2008

19.02.2008 Christian Hoffmann On the Complexity of the Interlace Polynomial
31.01.2008 Christian Hoffmann Parallel Evaluation of the Interlace Polynomial on Trees
22.11.2007 Markus Bläser Asymptotically Optimal Hitting Sets Against Polynomials
08.11.2007 Christian Hoffmann The "Local Trick" for Graph Polynomials

Summer Term 2007

19.09.2007 Bodo Manthey Smoothed Analysis of Binary Search Trees and Quicksort
19.07.2007 Oliver Putz Multi-Criteria Max-ATSP
13.06.2007 Mahmoud Fouz Approximability of the Geometric Cover Polynomial
23.05.2007 Christian Hoffmann Complexity of the Interlace Polynomial
16.05.2007 Markus Bläser Faster Integer Multiplication II
02.05.2007 Markus Bläser Faster Integer Multiplication (by Martin Fürer)
25.04.2007 Vitaly Osipov External Memory Algorithms
11.04.2007 Christian Hoffmann The Interlace Polynomial

Winter Term 2006/2007

19.02.2007 Janos Makowsky
(Technion)
Graph Polynomials and Complexity
30.11.2006 Markus Bläser Addition Chains

Summer Term 2006

05.07.2006 Vitaly Osipov Polynomial Time Randomized Parallel Approximation Algorithm for Finding Heavy Planar Subgraphs
28.06.2006 Holger Dell The Tutte Polynomial and Its Complexity
14.06.2006 Bodo Manthey Approximation Algorithms for Restricted Cycle Covers Based on Cycle Decompositions
31.05.2006 Bodo Manthey Approximability of Minimum AND-Circuits
24.05.2006 René Beier
(MPI Informatik)
Improving the Separation Lemma
10.05.2006 Markus Bläser The Isolation Lemma—A result that I did not teach in the complexity lecture but should have
03.05.2006 Bodo Manthey Approximating Multi-Criteria Travelling Salesman Problems