Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

Radu Curticapean

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. Previously, I was a PhD student in the computational complexity group at Saarland University and defended my thesis in 2015. After that, I also spent two semesters 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: MTA SZTAKI
Lágymányosi u. 11.
H-1111 Budapest
Hungary
Email: [my first name].[my last name] at gmail dot com

Selected Publications

For a full list, please consider my DBLP page.

 [P6]
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.
 [P5]
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)
 [P4]
Parameterizing the Permanent: Genus, Apices, Minors, Evaluation mod 2^k
Radu Curticapean, Mingji Xia
56th Annual Symposium on Foundations of Computer Science (FOCS 2015)
 [P3]
Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity.
Radu Curticapean
42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015)
 [P2]
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)
 [P1]
Counting Matchings of Size k is #W[1]-hard.
Radu Curticapean
40th International Colloquium on Automata, Languages and Programming (ICALP 2013)

Teaching Support

Links you might find useful