4 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…
Weisfeiler-Leman Is Incomplete on Simple Spectrum Graphs, so Canonicalize Them
Snir Hordan, Nadav Dym, Tim Seppelt
Graphs with a simple spectrum admit cubic-time isomorphism testing, yet we prove that for every natural number , the -Weisfeiler-Leman (-WL) test cannot distinguish all no…
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…
Distinguishing Graphs by Counting Homomorphisms from Sparse Graphs
Daniel Neuen, Tim Seppelt
Lovász (1967) showed that two graphs and are isomorphic if, and only if, they are homomorphism indistinguishable over all graphs, i.e., and admit the same number o…