11 papers
Reconstructing Historical Manuscripts through MSI: The Potential of Contrast in Assessing Image Quality and Legibility
Anna Breger
Digital restoration of historical manuscript images aims to improve readability while preserving the authenticity of cultural heritage documents. However, evaluating quality of res…
Counting Small Induced Subgraphs: Hardness of Symmetry-Based Properties
Radu Curticapean, Mingjun Liu
Jerrum and Meeks (TOCT, JCSS 2015) introduced the counting problems for fixed graph properties : Given an input graph and , count the …
Planar Perfect Matching Counting is as Hard as Determinants
Radu Curticapean, Jiaheng Wang
In the 1960s, Fisher, Kasteleyn and Temperley designed an ingenious algorithm for computing the partition function of the dimer model, or equivalently, for counting perfect matchin…
Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?
Cornelius Brand, Radu Curticapean, Petteri Kaski +4
The complexity of bilinear maps (equivalently, of -mode tensors) has been studied extensively, most notably in the context of matrix multiplication. While circuit complexity and…
Counting Small Induced Subgraphs: Hardness via Fourier Analysis
Radu Curticapean, Daniel Neuen
For a fixed graph property and integer , consider the problem of counting the induced -vertex subgraphs satisfying in an input graph . This problem can be…
Which graph motif parameters count?
Markus Bläser, Radu Curticapean, Julian Dörfler +1
For a fixed graph H, the function #IndSub(H,*) maps graphs G to the count of induced H-copies in G; this function obviously "counts something" in that it has a combinatorial interp…