81 citations · 134 across the 18 of their papers we have counts for
7 papers · 1 filter
Faster Convolutions: Yates and Strassen Revisited
Cornelius Brand, Radu Curticapean, Baitian Li +1
Given two vectors over a finite domain and a function , the convolution problem asks to compute the vector whose…
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 -vertex graphs of maximum degree such that time algorithms for d…
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…
A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
Radu Curticapean, Nathan Lindzey, Jesper Nederlof
For even , the matchings connectivity matrix encodes which pairs of perfect matchings on vertices form a single cycle. Cygan et al. (STOC 2013) showed that th…
Homomorphisms Are a Good Basis for Counting Small Subgraphs
Radu Curticapean, Holger Dell, Dániel Marx
We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovász show that many in…
Finding Detours is Fixed-parameter Tractable
Ivona Bezáková, Radu Curticapean, Holger Dell +1
We consider the following natural "above guarantee" parameterization of the classical Longest Path problem: For given vertices s and t of a graph G, and an integer k, the problem L…
Counting perfect matchings in graphs that exclude a single-crossing minor
Radu Curticapean
A graph is single-crossing if it can be drawn in the plane with at most one crossing. For any single-crossing graph , we give an time algorithm for counting perfect…