26 Search Results for "Fürer, Martin"

Document
DOI: 10.4230/LIPIcs.CSL.2026.36
A Game for Counting Logic Formula Size and an Application to Linear Orders

Authors: Grégoire Fournier and György Turán

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract
Ehrenfeucht-Fraïssé (EF) games are a basic tool in finite model theory for proving definability lower bounds, with many applications in complexity theory and related areas. They have been applied to study various logics, giving insights on quantifier rank and other logical complexity measures. In this paper, we present an EF game to capture formula size in counting logic with a bounded number of variables. The game combines games introduced previously for counting logic quantifier rank due to Immerman and Lander, and for first-order formula size due to Adler and Immerman, and Hella and Väänänen. The game is used to prove an extension of a formula size lower bound of Grohe and Schweikardt for distinguishing linear orders, from 3-variable first-order logic to 3-variable counting logic.
Cite as

Grégoire Fournier and György Turán. A Game for Counting Logic Formula Size and an Application to Linear Orders. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fournier_et_al:LIPIcs.CSL.2026.36,
  author =	{Fournier, Gr\'{e}goire and Tur\'{a}n, Gy\"{o}rgy},
  title =	{{A Game for Counting Logic Formula Size and an Application to Linear Orders}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{36:1--36:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.36},
  URN =		{urn:nbn:de:0030-drops-254612},
  doi =		{10.4230/LIPIcs.CSL.2026.36},
  annote =	{Keywords: Finite Model Theory, Logical Aspects of Computational Complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.46
Symmetric Algebraic Circuits and Homomorphism Polynomials

Authors: Anuj Dawar, Benedikt Pago, and Tim Seppelt

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The central open question of algebraic complexity is whether VP ≠ VNP, which is saying that the permanent cannot be represented by families of polynomial-size algebraic circuits. For symmetric algebraic circuits, this has been confirmed by Dawar and Wilsenach (2020), who showed exponential lower bounds on the size of symmetric circuits for the permanent. In this work, we set out to develop a more general symmetric algebraic complexity theory. Our main result is that a family of symmetric polynomials admits small symmetric circuits if and only if they can be written as a linear combination of homomorphism counting polynomials of graphs of bounded treewidth. We also establish a relationship between the symmetric complexity of subgraph counting polynomials and the vertex cover number of the pattern graph. As a concrete example, we examine the symmetric complexity of immanant families (a generalisation of the determinant and permanent) and show that a known conditional dichotomy due to Curticapean (2021) holds unconditionally in the symmetric setting.
Cite as

Anuj Dawar, Benedikt Pago, and Tim Seppelt. Symmetric Algebraic Circuits and Homomorphism Polynomials. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.ITCS.2026.46,
  author =	{Dawar, Anuj and Pago, Benedikt and Seppelt, Tim},
  title =	{{Symmetric Algebraic Circuits and Homomorphism Polynomials}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.46},
  URN =		{urn:nbn:de:0030-drops-253330},
  doi =		{10.4230/LIPIcs.ITCS.2026.46},
  annote =	{Keywords: algebraic complexity, finite model theory, symmetric circuits, homomorphism counting, graph homomorphism, treewidth, counting width, first-order logic with counting quantifiers}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.17
Treedepth Inapproximability and Exponential ETH Lower Bound

Authors: Édouard Bonnet, Daniel Neuen, and Marek Sokołowski

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Treedepth is a central parameter to algorithmic graph theory. The current state-of-the-art in computing and approximating treedepth consists of a 2^{O(k²)} n-time exact algorithm and a polynomial-time O(OPT log^{3/2} OPT)-approximation algorithm, where the former algorithm returns an elimination forest of height k (witnessing that treedepth is at most k) for the n-vertex input graph G, or correctly reports that G has treedepth larger than k, and OPT is the actual value of the treedepth. On the complexity side, exactly computing treedepth is NP-complete, but the known reductions do not rule out a polynomial-time approximation scheme (PTAS), and under the Exponential Time Hypothesis (ETH) only exclude a running time of 2^o(√n) for exact algorithms. We show that 1.0003-approximating Treedepth is NP-hard, and that exactly computing the treedepth of an n-vertex graph requires time 2^Ω(n), unless the ETH fails. We further derive that there exist absolute constants δ, c > 0 such that any (1+δ)-approximation algorithm requires time 2^Ω(n/log^c n). We do so via a simple direct reduction from Satisfiability to Treedepth, inspired by a reduction recently designed for Treewidth [STOC '25].
Cite as

Édouard Bonnet, Daniel Neuen, and Marek Sokołowski. Treedepth Inapproximability and Exponential ETH Lower Bound. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 17:1-17:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.IPEC.2025.17,
  author =	{Bonnet, \'{E}douard and Neuen, Daniel and Soko{\l}owski, Marek},
  title =	{{Treedepth Inapproximability and Exponential ETH Lower Bound}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{17:1--17:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.17},
  URN =		{urn:nbn:de:0030-drops-251494},
  doi =		{10.4230/LIPIcs.IPEC.2025.17},
  annote =	{Keywords: treedepth, lower bounds, approximation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.116
Fast Gaussian Elimination for Low Treewidth Matrices

Authors: Martin Fürer, Carlos Hoppen, and Vilmar Trevisan

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Let A = (a_{ij}) be an m× n matrix whose elements lie in an arbitrary field 𝔽, and let G be the bipartite graph with vertex set {v_1,…,v_m} ∪ {w_1,…,w_n} such that vertices v_i and w_j are adjacent if and only if a_{ij} ≠ 0. We introduce an algorithm that finds an m× n matrix U in row echelon form and a permutation matrix Q of order n, such that AQ is row equivalent to U. If a tree decomposition 𝒯 of G of width k and size O(k(m+n)) is part of the input, then Q and the columns of U that contain a pivot can be computed in time O(k²(m+n)). Among other things, this allows us to compute the rank and the determinant of A in time O(k²(m+n)). It also allows us to decide in time O(k²(m+n)) whether the linear system Ax = b has a solution and to compute a solution of the linear system in case it exists.
Cite as

Martin Fürer, Carlos Hoppen, and Vilmar Trevisan. Fast Gaussian Elimination for Low Treewidth Matrices. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 116:1-116:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{furer_et_al:LIPIcs.ESA.2025.116,
  author =	{F\"{u}rer, Martin and Hoppen, Carlos and Trevisan, Vilmar},
  title =	{{Fast Gaussian Elimination for Low Treewidth Matrices}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{116:1--116:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.116},
  URN =		{urn:nbn:de:0030-drops-245855},
  doi =		{10.4230/LIPIcs.ESA.2025.116},
  annote =	{Keywords: Gaussian elimination, FPT algorithms, treewidth}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.88
Color Refinement for Relational Structures

Authors: Benjamin Scheidt and Nicole Schweikardt

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Color Refinement, also known as Naive Vertex Classification, is a classical method to distinguish graphs by iteratively computing a coloring of their vertices. While it is traditionally used as an imperfect way to test for isomorphism, the algorithm has permeated many other, seemingly unrelated, areas of computer science. The method is algorithmically simple, and it has a well-understood distinguishing power: it has been logically characterized by Immerman and Lander (1990) and Cai, Fürer, Immerman (1992), who showed that it distinguishes precisely those graphs that can be distinguished by a sentence of first-order logic with counting quantifiers and only two variables. A combinatorial characterization was given by Dvořák (2010), who showed that it distinguishes precisely those graphs that differ in the number of homomorphisms from some tree. In this paper, we introduce Relational Color Refinement (RCR, for short), a generalization of the Color Refinement method from graphs to arbitrary relational structures, whose distinguishing power admits the equivalent combinatorial and logical characterizations as Color Refinement has on graphs: we show that RCR distinguishes precisely those structures that differ in the number of homomorphisms from an acyclic connected relational structure. Further, we show that RCR distinguishes precisely those structures that are distinguished by a sentence of the guarded fragment of first-order logic with counting quantifiers. Additionally, we show that for every fixed finite relational signature, RCR can be implemented to run on structures of that signature in time O(N⋅log N), where N denotes the number of tuples present in the structure.
Cite as

Benjamin Scheidt and Nicole Schweikardt. Color Refinement for Relational Structures. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 88:1-88:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{scheidt_et_al:LIPIcs.MFCS.2025.88,
  author =	{Scheidt, Benjamin and Schweikardt, Nicole},
  title =	{{Color Refinement for Relational Structures}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{88:1--88:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.88},
  URN =		{urn:nbn:de:0030-drops-241958},
  doi =		{10.4230/LIPIcs.MFCS.2025.88},
  annote =	{Keywords: color refinement, counting logics, homomorphism counts, homomorphism indistinguishability, guarded logics, pebble games, relational structures, alpha-acyclicity, join-trees}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.89
Homomorphism Indistinguishability and Game Comonads for Restricted Conjunction and Requantification

Authors: Georg Schindling

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
The notion of homomorphism indistinguishability offers a combinatorial framework for characterizing equivalence relations of graphs, in particular equivalences in counting logics within finite model theory. That is, for certain graph classes, two structures agree on all homomorphism counts from the class if and only if they satisfy the same sentences in a corresponding logic. This perspective often reveals connections between the combinatorial properties of graph classes and the syntactic structure of logical fragments. In this work, we extend this perspective to logics with restricted requantification, refining the stratification of logical resources in finite-variable counting logics. Specifically, we generalize Lovász-type theorems for these logics with either restricted conjunction or bounded quantifier-rank and present new combinatorial proofs of existing results. To this end, we introduce novel path and tree decompositions that incorporate the concept of reusability and develop characterizations based on pursuit-evasion games. Leveraging this framework, we establish that classes of bounded pathwidth and treewidth with reusability constraints are homomorphism distinguishing closed. Finally, we develop a comonadic perspective on requantification by constructing new comonads that encapsulate restricted-reusability pebble games. We show a tight correspondence between their coalgebras and path/tree decompositions, yielding categorical characterizations of reusability in graph decompositions. This unifies logical, combinatorial, and categorical perspectives on the notion of reusability.
Cite as

Georg Schindling. Homomorphism Indistinguishability and Game Comonads for Restricted Conjunction and Requantification. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 89:1-89:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schindling:LIPIcs.MFCS.2025.89,
  author =	{Schindling, Georg},
  title =	{{Homomorphism Indistinguishability and Game Comonads for Restricted Conjunction and Requantification}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{89:1--89:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.89},
  URN =		{urn:nbn:de:0030-drops-241962},
  doi =		{10.4230/LIPIcs.MFCS.2025.89},
  annote =	{Keywords: homomorphism indistinguishability, game comonads, finite variable counting logic, restricted conjunction, restricted requantification, tree decomposition, path decomposition}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.34
Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts

Authors: Balder ten Cate, Phokion G. Kolaitis, and Arnar Á. Kristjánsson

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
A query algorithm based on homomorphism counts is a procedure to decide membership for a class of finite relational structures using only homomorphism count queries. A left query algorithm can ask the number of homomorphisms from any structure to the input structure and a right query algorithm can ask the number of homomorphisms from the input structure to any other structure. We systematically compare the expressive power of different types of left or right query algorithms, including non-adaptive query algorithms, adaptive query algorithms that can ask a bounded number of queries, and adaptive query algorithms that can ask an unbounded number of queries. We also consider query algorithms where the homomorphism counting is done over the Boolean semiring 𝔹, meaning that only the existence of a homomorphism is recorded, not the precise number of them.
Cite as

Balder ten Cate, Phokion G. Kolaitis, and Arnar Á. Kristjánsson. Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 34:1-34:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{tencate_et_al:LIPIcs.MFCS.2025.34,
  author =	{ten Cate, Balder and Kolaitis, Phokion G. and Kristj\'{a}nsson, Arnar \'{A}.},
  title =	{{Adaptive Query Algorithms for Relational Structures Based on Homomorphism Counts}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{34:1--34:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.34},
  URN =		{urn:nbn:de:0030-drops-241413},
  doi =		{10.4230/LIPIcs.MFCS.2025.34},
  annote =	{Keywords: Query algorithms, homomorphisms, homomorphism counts, directed graphs, relational structures, Datalog, constraint satisfaction}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.40
Symmetric Proofs in the Ideal Proof System

Authors: Anuj Dawar, Erich Grädel, Leon Kullmann, and Benedikt Pago

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We consider the Ideal Proof System (IPS) introduced by Grochow and Pitassi and pose the question of which tautologies admit symmetric proofs, and of what complexity. The symmetry requirement in proofs is inspired by recent work establishing lower bounds in other symmetric models of computation. We link the existence of symmetric IPS proofs to the expressive power of logics such as fixed-point logic with counting and Choiceless Polynomial Time, specifically regarding the graph isomorphism problem. We identify relationships and tradeoffs between the symmetry of proofs and other parameters of IPS proofs such as size, degree and linearity. We study these on a number of standard families of tautologies from proof complexity and finite model theory such as the pigeonhole principle, the subset sum problem and the Cai-Fürer-Immerman graphs, exhibiting non-trivial upper bounds on the size of symmetric IPS proofs.
Cite as

Anuj Dawar, Erich Grädel, Leon Kullmann, and Benedikt Pago. Symmetric Proofs in the Ideal Proof System. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.MFCS.2025.40,
  author =	{Dawar, Anuj and Gr\"{a}del, Erich and Kullmann, Leon and Pago, Benedikt},
  title =	{{Symmetric Proofs in the Ideal Proof System}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.40},
  URN =		{urn:nbn:de:0030-drops-241477},
  doi =		{10.4230/LIPIcs.MFCS.2025.40},
  annote =	{Keywords: proof complexity, algebraic complexity, descriptive complexity, symmetric circuits, graph isomorphism}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.18
Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism

Authors: Christoph Berkholz, Moritz Lichter, and Harry Vinall-Smeeth

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We study the refutation complexity of graph isomorphism in the tree-like resolution calculus. Torán and Wörz [Jacobo Torán and Florian Wörz, 2023] showed that there is a resolution refutation of narrow width k for two graphs if and only if they can be distinguished in (k+1)-variable first-order logic (FO^{k+1}). While DAG-like narrow width k resolution refutations have size at most n^k, tree-like refutations may be much larger. We show that there are graphs of order n, whose isomorphism can be refuted in narrow width k but only in tree-like size 2^{Ω(n^{k/2})}. This is a supercritical trade-off where bounding one parameter (the narrow width) causes the other parameter (the size) to grow above its worst case. The size lower bound is super-exponential in the formula size and improves a related supercritical trade-off by Razborov [Alexander A. Razborov, 2016]. To prove our result, we develop a new variant of the k-pebble EF-game for FO^k to reason about tree-like refutation size in a similar way as the Prover-Delayer games in proof complexity. We analyze this game on the compressed CFI graphs introduced by Grohe, Lichter, Neuen, and Schweitzer [Martin Grohe et al., 2023]. Using a recent improved robust compressed CFI construction of de Rezende, Fleming, Janett, Nordström, and Pang [Susanna F. de Rezende et al., 2024], we obtain a similar bound for width k (instead of the stronger but less common narrow width) and make the result more robust.
Cite as

Christoph Berkholz, Moritz Lichter, and Harry Vinall-Smeeth. Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{berkholz_et_al:LIPIcs.MFCS.2025.18,
  author =	{Berkholz, Christoph and Lichter, Moritz and Vinall-Smeeth, Harry},
  title =	{{Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{18:1--18:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.18},
  URN =		{urn:nbn:de:0030-drops-241253},
  doi =		{10.4230/LIPIcs.MFCS.2025.18},
  annote =	{Keywords: Proof complexity, Resolution, Width, Tree-like size, Supercritical trade-off, Lower bound, Finite model theory, CFI graphs}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.131
Deterministic Complexity Analysis of Hermitian Eigenproblems

Authors: Aleksandros Sobczyk

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In this work we revisit the arithmetic and bit complexity of Hermitian eigenproblems. Recently, [BGVKS, FOCS 2020] proved that a (non-Hermitian) matrix A can be diagonalized with a randomized algorithm in O(n^{ω}log²(n/ε)) arithmetic operations, where ω≲ 2.371 is the square matrix multiplication exponent, and [Shah, SODA 2025] significantly improved the bit complexity for the Hermitian case. Our main goal is to obtain similar deterministic complexity bounds for various Hermitian eigenproblems. In the Real RAM model, we show that a Hermitian matrix can be diagonalized deterministically in O(n^{ω}log(n)+n²polylog(n/ε)) arithmetic operations, improving the classic deterministic Õ(n³) algorithms, and derandomizing the aforementioned state-of-the-art. The main technical step is a complete, detailed analysis of a well-known divide-and-conquer tridiagonal eigensolver of Gu and Eisenstat [GE95], when accelerated with the Fast Multipole Method, asserting that it can accurately diagonalize a symmetric tridiagonal matrix in nearly-O(n²) operations. In finite precision, we show that an algorithm by Schönhage [Sch72] to reduce a Hermitian matrix to tridiagonal form is stable in the floating point model, using O(log(n/ε)) bits of precision. This leads to a deterministic algorithm to compute all the eigenvalues of a Hermitian matrix in O(n^{ω}ℱ(log(n/ε)) + n²polylog(n/ε)) bit operations, where ℱ(b) ∈ Õ(b) is the bit complexity of a single floating point operation on b bits. This improves the best known Õ(n³) deterministic and O(n^{ω}log²(n/ε)ℱ(log(n/ε))) randomized complexities. We conclude with some other useful subroutines such as computing spectral gaps, condition numbers, and spectral projectors, and with some open problems.
Cite as

Aleksandros Sobczyk. Deterministic Complexity Analysis of Hermitian Eigenproblems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 131:1-131:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sobczyk:LIPIcs.ICALP.2025.131,
  author =	{Sobczyk, Aleksandros},
  title =	{{Deterministic Complexity Analysis of Hermitian Eigenproblems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{131:1--131:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.131},
  URN =		{urn:nbn:de:0030-drops-235081},
  doi =		{10.4230/LIPIcs.ICALP.2025.131},
  annote =	{Keywords: Hermitian eigenproblem, eigenvalues, SVD, tridiagonal reduction, matrix multiplication time, diagonalization, bit complexity}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.166
Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems

Authors: Moritz Lichter and Benedikt Pago

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We show that various recent algorithms for finite-domain constraint satisfaction problems (CSP), which are based on solving their affine integer relaxations, do not solve all tractable and not even all Maltsev CSPs. This rules them out as candidates for a universal polynomial-time CSP algorithm. The algorithms are ℤ-affine k-consistency, BLP+AIP, BA^{k}, and CLAP. We thereby answer a question by Brakensiek, Guruswami, Wrochna, and Živný [Joshua Brakensiek et al., 2020] whether a constant level of BA^{k}solves all tractable CSPs in the negative: Indeed, not even a sublinear level k suffices. We also refute a conjecture by Dalmau and Opršal [Víctor Dalmau and Jakub Opršal, 2024] (LICS 2024) that every CSP is either solved by ℤ-affine k-consistency or admits a Datalog reduction from 3-colorability. For the cohomological k-consistency algorithm, that is also based on affine relaxations, we show that it correctly solves our counterexample but fails on an NP-complete template.
Cite as

Moritz Lichter and Benedikt Pago. Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 166:1-166:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lichter_et_al:LIPIcs.ICALP.2025.166,
  author =	{Lichter, Moritz and Pago, Benedikt},
  title =	{{Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{166:1--166:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.166},
  URN =		{urn:nbn:de:0030-drops-235431},
  doi =		{10.4230/LIPIcs.ICALP.2025.166},
  annote =	{Keywords: constraint satisfaction, affine relaxation, promise CSPs, \mathbb{Z}-affine k-consistency, cohomological k-consistency algorithm, Tseitin, graph isomorphism}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.120
Treewidth Parameterized by Feedback Vertex Number

Authors: Hendrik Molter, Meirav Zehavi, and Amit Zivan

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We provide the first algorithm for computing an optimal tree decomposition for a given graph G that runs in single exponential time in the feedback vertex number of G, that is, in time 2^{𝒪(fvn(G))}⋅ n^{𝒪(1)}, where fvn(G) is the feedback vertex number of G and n is the number of vertices of G. On a classification level, this improves the previously known results by Chapelle et al. [Discrete Applied Mathematics '17] and Fomin et al. [Algorithmica '18], who independently showed that an optimal tree decomposition can be computed in single exponential time in the vertex cover number of G. One of the biggest open problems in the area of parameterized complexity is whether we can compute an optimal tree decomposition in single exponential time in the treewidth of the input graph. The currently best known algorithm by Korhonen and Lokshtanov [STOC '23] runs in 2^{𝒪(tw(G)²)}⋅ n⁴ time, where tw(G) is the treewidth of G. Our algorithm improves upon this result on graphs G where fvn(G) ∈ o(tw(G)²). On a different note, since fvn(G) is an upper bound on tw(G), our algorithm can also be seen either as an important step towards a positive resolution of the above-mentioned open problem, or, if its answer is negative, then a mark of the tractability border of single exponential time algorithms for the computation of treewidth.
Cite as

Hendrik Molter, Meirav Zehavi, and Amit Zivan. Treewidth Parameterized by Feedback Vertex Number. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 120:1-120:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{molter_et_al:LIPIcs.ICALP.2025.120,
  author =	{Molter, Hendrik and Zehavi, Meirav and Zivan, Amit},
  title =	{{Treewidth Parameterized by Feedback Vertex Number}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{120:1--120:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.120},
  URN =		{urn:nbn:de:0030-drops-234979},
  doi =		{10.4230/LIPIcs.ICALP.2025.120},
  annote =	{Keywords: Treewidth, Tree Decomposition, Exact Algorithms, Single Exponential Time, Feedback Vertex Number, Dynamic Programming}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.129
An Upper Bound on the Weisfeiler-Leman Dimension

Authors: Thomas Schneider and Pascal Schweitzer

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
The Weisfeiler-Leman (WL) algorithms form a family of incomplete approaches to the graph isomorphism problem. They recently found various applications in algorithmic group theory and machine learning. In fact, the algorithms form a parameterized family: for each k ∈ ℕ there is a corresponding k-dimensional algorithm WLk. The algorithms become increasingly powerful with increasing dimension, but at the same time the running time increases. The WL-dimension of a graph G is the smallest k ∈ ℕ for which WLk correctly decides isomorphism between G and every other graph. In some sense, the WL-dimension measures how difficult it is to test isomorphism of one graph to others using a fairly general class of combinatorial algorithms. Nowadays, it is a standard measure in descriptive complexity theory for the structural complexity of a graph. We prove that the WL-dimension of a graph on n vertices is at most 3/20 ⋅ n + o(n) = 0.15 ⋅ n + o(n). Reducing the question to coherent configurations, the proof develops various techniques to analyze their structure. This includes sufficient conditions under which a fiber can be restored uniquely up to isomorphism if it is removed, a recursive proof exploiting a degree reduction and treewidth bounds, as well as an exhaustive analysis of interspaces involving small fibers. As a base case, we also analyze the dimension of coherent configurations with small fiber size and thereby graphs with small color class size.
Cite as

Thomas Schneider and Pascal Schweitzer. An Upper Bound on the Weisfeiler-Leman Dimension. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 129:1-129:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schneider_et_al:LIPIcs.ICALP.2025.129,
  author =	{Schneider, Thomas and Schweitzer, Pascal},
  title =	{{An Upper Bound on the Weisfeiler-Leman Dimension}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{129:1--129:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.129},
  URN =		{urn:nbn:de:0030-drops-235065},
  doi =		{10.4230/LIPIcs.ICALP.2025.129},
  annote =	{Keywords: Weisfeiler-Leman dimension, descriptive complexity, coherent configurations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.17
Sparse Bounded Hop-Spanners for Geometric Intersection Graphs

Authors: Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, and Csaba D. Tóth

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We present new results on 2- and 3-hop spanners for geometric intersection graphs. These include improved upper and lower bounds for 2- and 3-hop spanners for many geometric intersection graphs in ℝ^d. For example, we show that the intersection graph of n balls in ℝ^d admits a 2-hop spanner of size O^*(n^{3/2 - 1/(2(2⌊d/2⌋ + 1))}) and the intersection graph of n fat axis-parallel boxes in ℝ^d admits a 2-hop spanner of size O(n log^{d+1}n). Furthermore, we show that the intersection graph of general semi-algebraic objects in ℝ^d admits a 3-hop spanner of size O^*(n^{3/2 - 1/(2(2D-1))}), where D is a parameter associated with the description complexity of the objects. For such families (or more specifically, for tetrahedra in ℝ³), we provide a lower bound of Ω(n^{4/3}). For 3-hop and axis-parallel boxes in ℝ^d, we provide the upper bound O(n log ^{d-1}n) and lower bound Ω(n ({log n}/{log log n})^{d-2}).
Cite as

Sujoy Bhore, Timothy M. Chan, Zhengcheng Huang, Shakhar Smorodinsky, and Csaba D. Tóth. Sparse Bounded Hop-Spanners for Geometric Intersection Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2025.17,
  author =	{Bhore, Sujoy and Chan, Timothy M. and Huang, Zhengcheng and Smorodinsky, Shakhar and T\'{o}th, Csaba D.},
  title =	{{Sparse Bounded Hop-Spanners for Geometric Intersection Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.17},
  URN =		{urn:nbn:de:0030-drops-231698},
  doi =		{10.4230/LIPIcs.SoCG.2025.17},
  annote =	{Keywords: Geometric Spanners, Geometric Intersection Graphs}
}
Document
DOI: 10.4230/LIPIcs.CPM.2025.29
Faster Approximate Elastic-Degenerate String Matching - Part B

Authors: Paweł Gawrychowski, Adam Górkiewicz, Pola Marciniak, Solon P. Pissis, and Karol Pokorski

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

Abstract
We revisit the complexity of approximate pattern matching in an elastic-degenerate string. Such a string is a sequence of n finite sets of strings of total length N, and compactly describes a collection of strings obtained by first choosing exactly one string in every set, and then concatenating them together. This is motivated by the need of storing a collection of highly similar DNA sequences. The basic algorithmic question on elastic-degenerate strings is pattern matching: given such an elastic-degenerate string and a standard pattern of length m, check if the pattern occurs in one of the strings in the described collection. Bernardini et al. [SICOMP 2022] showed how to leverage fast matrix multiplication to obtain an Õ(nm^{ω-1})+𝒪(N)-time complexity for this problem, where ω is the matrix multiplication exponent. However, from the point of view of possible applications, it is more desirable to work with approximate pattern matching, where we seek approximate occurrences of the pattern. This generalization has been considered in a few papers already, but the best result so far for occurrences with k mismatches, where k is a constant, is the Õ(nm²+N)-time algorithm presented in Part A [CPM 2025]. This brings the question whether increasing the dependency on m from m^{ω-1} to quadratic is necessary when moving from k = 0 to larger (but still constant) k. We design an Õ(nm^{1.5}+N)-time algorithm for pattern matching with k mismatches in an elastic-degenerate string, for any constant k. To obtain this time bound, we leverage the structural characterization of occurrences with k mismatches of Charalampopoulos, Kociumaka, and Wellnitz [FOCS 2020] together with fast Fourier transform. We need to work with multiple patterns at the same time, instead of a single pattern, which requires refining the original characterization. This might be of independent interest.
Cite as

Paweł Gawrychowski, Adam Górkiewicz, Pola Marciniak, Solon P. Pissis, and Karol Pokorski. Faster Approximate Elastic-Degenerate String Matching - Part B. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 29:1-29:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.CPM.2025.29,
  author =	{Gawrychowski, Pawe{\l} and G\'{o}rkiewicz, Adam and Marciniak, Pola and Pissis, Solon P. and Pokorski, Karol},
  title =	{{Faster Approximate Elastic-Degenerate String Matching - Part B}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{29:1--29:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.29},
  URN =		{urn:nbn:de:0030-drops-231236},
  doi =		{10.4230/LIPIcs.CPM.2025.29},
  annote =	{Keywords: ED string, approximate pattern matching, Hamming distance, k mismatches}
}
  • Refine by Type
  • 26 Document/PDF
  • 22 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 20 2025
  • 1 2024
  • 1 2023
  • 1 2020
  • Show More...

  • Refine by Author
  • 3 Fürer, Martin
  • 3 Lichter, Moritz
  • 3 Pago, Benedikt
  • 3 Schweitzer, Pascal
  • 2 Dawar, Anuj
  • Show More...

  • Refine by Series/Journal
  • 25 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 8 Theory of computation → Finite Model Theory
  • 6 Theory of computation → Complexity theory and logic
  • 4 Mathematics of computing → Graph theory
  • 4 Theory of computation → Problems, reductions and completeness
  • 3 Theory of computation → Parameterized complexity and exact algorithms
  • Show More...

  • Refine by Keyword
  • 3 clique-width
  • 2 Treewidth
  • 2 Weisfeiler-Leman algorithm
  • 2 algebraic complexity
  • 2 coherent configurations
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact