Radu Curticapean

activity

20132026

most citedHomomorphisms Are a Good Basis for Counting Small Subgraphs

81 citations · 134 across the 18 of their papers we have counts for

collaborators

Showing 2024Show all

3 papers · 1 filter

cs.DS2024

Can You Link Up With Treewidth?

Radu Curticapean, Simon Döring, Daniel Neuen +1

In a fundamental paper in parameterized complexity theory, Marx [ToC '10] constructed $k$ -vertex graphs $H$ of maximum degree $3$ such that $n^{o (k / l o g k)}$ time algorithms for d…

cs.CC2024

Counting Small Induced Subgraphs: Hardness via Fourier Analysis

Radu Curticapean, Daniel Neuen

For a fixed graph property $Φ$ and integer $k \geq 1$ , consider the problem of counting the induced $k$ -vertex subgraphs satisfying $Φ$ in an input graph $G$ . This problem can be s…

cs.DS2024★ 1 cited

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

Andreas Björklund, Radu Curticapean, Thore Husfeldt +2

In this paper we further explore the recently discovered connection by Björklund and Kaski [STOC 2024] and Pratt [STOC 2024] between the asymptotic rank conjecture of Strassen [Pro…