Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Radu Curticapean

I was a PhD student in the computational complexity group at Saarland University and defended my thesis in 2015. Currently, I am a post-doc at the Institute for Computer Science and Control of the Hungarian Academy of Sciences, also known as MTA SZTAKI, where I'm part of the PARAMTIGHT group. For two semesters, I also was a fellow at the Simons Institute in Berkeley.

My main research area is counting complexity. I am also interested in parameterized complexity theory (especially for counting problems), lower bounds under the different exponential-time hypotheses, graph minor theory and, to a lesser extent, in smoothed analysis.

Contact Information

Address: Universität des Saarlandes
Campus Geb E1 3
Postfach 42 (Bläser)
66123 Saarbrücken
Office: Building E1.3 423
Phone: +49 681 302-5585
Email: [my last name] at


Homomorphisms Are a Good Basis for Counting Small Subgraphs
Radu Curticapean, Holger Dell, Dániel Marx
49th Annual ACM Symposium on the Theory of Computing (STOC 2017). To appear.
Counting Matchings with k Unmatched Vertices in Planar Graphs
Radu Curticapean
24th European Symposium on Algorithms (ESA 2016)
Parity Separation: A Scientifically Proven Method for Permanent Weight Loss
Radu Curticapean
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Tight Conditional Lower Bounds for Counting Perfect Matchings on Graphs of Bounded Treewidth and Cliquewidth
Radu Curticapean, Dániel Marx
27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)
Parameterizing the Permanent: Genus, Apices, Minors, Evaluation mod 2^k
Radu Curticapean, Mingji Xia
56th Annual Symposium on Foundations of Computer Science (FOCS 2015)
Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity.
Radu Curticapean
42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015)
Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts
Radu Curticapean, Dániel Marx
55th Annual Symposium on Foundations of Computer Science (FOCS 2014)
A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems.
Radu Curticapean, Marvin Künnemann
21st European Symposium on Algorithms (ESA 2013)
Counting Matchings of Size k is #W[1]-hard.
Radu Curticapean
40th International Colloquium on Automata, Languages and Programming (ICALP 2013)
Weighted Counting of k-Matchings is #W[1]-hard
Markus Bläser, Radu Curticapean
7th International Symposium on Parameterized and Exact Computation (IPEC 2012)
Counting Crossing Free Structures
Victor Alvarez, Karl Bringmann, Radu Curticapean, Saurabh Ray
Symposuim on Computational Geometry 2012 (SoCG 2012)
The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree
Markus Bläser, Radu Curticapean
36th International Symposium on Mathematical Foundations of Computer Science (MFCS 2011)

Teaching Support

Links you might find useful