5 Search Results for "Rahul, Chengot Sankaramenon"

Document
DOI: 10.4230/LIPIcs.ICDT.2026.11
Factorised Representations of Join Queries: Tight Bounds and a New Dichotomy

Authors: Christoph Berkholz and Harry Vinall-Smeeth

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract
A common theme in factorised databases and knowledge compilation is the representation of solution sets in a useful yet succinct data structure. In this paper, we study the representation of the result of join queries (or, equivalently, the set of homomorphisms between two relational structures). We focus on the very general format of {∪,×}-circuits - also known as d-representations or DNNF circuits - and aim to find the limits of this approach. In prior work, it has been shown that there always exists a {∪,×}-circuit of size N^O(subw) representing the query result, where N is the size of the database and subw the submodular width of the query. If the arity of all relations is bounded by a constant, then subw is linear in the treewidth tw of the query. In this setting, the authors of this paper proved a lower bound of N^Ω(tw^ε) on the circuit size (ICALP 2023), where ε > 0 depends on the excluded grid theorem. Our first main contribution is to improve this lower bound to N^Ω(tw), which is tight up to a constant factor in the exponent. Our second contribution is a N^Ω(subw^{1/4}) lower bound on the circuit size for join queries over relations of unbounded arity. Both lower bounds are unconditional lower bounds on the circuit size for well-chosen database instances. Their proofs use a combination of structural (hyper)graph theory with communication complexity in a simple yet novel way. While the second lower bound is asymptotically equivalent to Marx’s conditional bound on the decision complexity (JACM 2013), our N^Θ(tw) bound in the bounded arity setting is tight, while the best conditional bound on the decision complexity is N^Ω(tw/log tw). Note that removing this logarithmic factor in the decision setting is a major open problem.
Cite as

Christoph Berkholz and Harry Vinall-Smeeth. Factorised Representations of Join Queries: Tight Bounds and a New Dichotomy. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{berkholz_et_al:LIPIcs.ICDT.2026.11,
  author =	{Berkholz, Christoph and Vinall-Smeeth, Harry},
  title =	{{Factorised Representations of Join Queries: Tight Bounds and a New Dichotomy}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.11},
  URN =		{urn:nbn:de:0030-drops-256255},
  doi =		{10.4230/LIPIcs.ICDT.2026.11},
  annote =	{Keywords: join queries, homomorphisms, factorised databases, succinct representation, knowledge compilation, lower bounds}
}
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.MFCS.2025.19
Monotone Bounded-Depth Complexity of Homomorphism Polynomials

Authors: C.S. Bhargav, Shiteng Chen, Radu Curticapean, and Prateek Dwivedi

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

Abstract
For every fixed graph H, it is known that homomorphism counts from H and colorful H-subgraph counts can be determined in O(n^{t+1}) time on n-vertex input graphs G, where t is the treewidth of H. On the other hand, a running time of n^{o(t / log t)} would refute the exponential-time hypothesis. Komarath, Pandey, and Rahul (Algorithmica, 2023) studied algebraic variants of these counting problems, i.e., homomorphism and subgraph polynomials for fixed graphs H. These polynomials are weighted sums over the objects counted above, where each object is weighted by the product of variables corresponding to edges contained in the object. As shown by Komarath et al., the monotone circuit complexity of the homomorphism polynomial for H is Θ(n^{tw(H)+1}). In this paper, we characterize the power of monotone bounded-depth circuits for homomorphism and colorful subgraph polynomials. This leads us to discover a natural hierarchy of graph parameters tw_Δ(H), for fixed Δ ∈ ℕ, which capture the width of tree-decompositions for H when the underlying tree is required to have depth at most Δ. We prove that monotone circuits of product-depth Δ computing the homomorphism polynomial for H require size Θ(n^{tw_Δ(H^{†})+1}), where H^{†} is the graph obtained from H by removing all degree-1 vertices. This allows us to derive an optimal depth hierarchy theorem for monotone bounded-depth circuits through graph-theoretic arguments.
Cite as

C.S. Bhargav, Shiteng Chen, Radu Curticapean, and Prateek Dwivedi. Monotone Bounded-Depth Complexity of Homomorphism Polynomials. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhargav_et_al:LIPIcs.MFCS.2025.19,
  author =	{Bhargav, C.S. and Chen, Shiteng and Curticapean, Radu and Dwivedi, Prateek},
  title =	{{Monotone Bounded-Depth Complexity of Homomorphism Polynomials}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{19:1--19: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.19},
  URN =		{urn:nbn:de:0030-drops-241269},
  doi =		{10.4230/LIPIcs.MFCS.2025.19},
  annote =	{Keywords: algebraic complexity, homomorphisms, monotone circuit complexity, bounded-depth circuits, treewidth, pathwidth}
}
Document
DOI: 10.4230/LIPIcs.CSL.2025.6
Equi-Rank Homomorphism Preservation Theorem on Finite Structures

Authors: Benjamin Rossman

Published in: LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Abstract
The Homomorphism Preservation Theorem (HPT) of classical model theory states that a first-order sentence is preserved under homomorphisms if, and only if, it is equivalent to an existential-positive sentence. This theorem remains valid when restricted to finite structures, as demonstrated by the author in [Rossman, 2008; Rossman, 2017] via distinct model-theoretic and circuit-complexity based proofs. In this paper, we present a third (and significantly simpler) proof of the finitary HPT based on a generalized Cai-Fürer-Immerman construction. This method establishes a tight correspondence between syntactic parameters of a homomorphism-preserved sentence (quantifier rank, variable width, alternation height) and structural parameters of its minimal models (tree-width, tree-depth, decomposition height). Consequently, we prove a conjectured "equi-rank" version of the finitary HPT. In contrast, previous versions of the finitary HPT possess additional properties, but incur blow-ups in the quantifier rank of the equivalent existential-positive sentence.
Cite as

Benjamin Rossman. Equi-Rank Homomorphism Preservation Theorem on Finite Structures. In 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 326, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rossman:LIPIcs.CSL.2025.6,
  author =	{Rossman, Benjamin},
  title =	{{Equi-Rank Homomorphism Preservation Theorem on Finite Structures}},
  booktitle =	{33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-362-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{326},
  editor =	{Endrullis, J\"{o}rg and Schmitz, Sylvain},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.6},
  URN =		{urn:nbn:de:0030-drops-227634},
  doi =		{10.4230/LIPIcs.CSL.2025.6},
  annote =	{Keywords: finite model theory, preservation theorems, quantifier rank}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.83
Monotone Arithmetic Complexity of Graph Homomorphism Polynomials

Authors: Balagopal Komarath, Anurag Pandey, and Chengot Sankaramenon Rahul

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
We study homomorphism polynomials, which are polynomials that enumerate all homomorphisms from a pattern graph H to n-vertex graphs. These polynomials have received a lot of attention recently for their crucial role in several new algorithms for counting and detecting graph patterns, and also for obtaining natural polynomial families which are complete for algebraic complexity classes VBP, VP, and VNP. We discover that, in the monotone setting, the formula complexity, the ABP complexity, and the circuit complexity of such polynomial families are exactly characterized by the treedepth, the pathwidth, and the treewidth of the pattern graph respectively. Furthermore, we establish a single, unified framework, using our characterization, to collect several known results that were obtained independently via different methods. For instance, we attain superpolynomial separations between circuits, ABPs, and formulas in the monotone setting, where the polynomial families separating the classes all correspond to well-studied combinatorial problems. Moreover, our proofs rediscover fine-grained separations between these models for constant-degree polynomials.
Cite as

Balagopal Komarath, Anurag Pandey, and Chengot Sankaramenon Rahul. Monotone Arithmetic Complexity of Graph Homomorphism Polynomials. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 83:1-83:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{komarath_et_al:LIPIcs.ICALP.2022.83,
  author =	{Komarath, Balagopal and Pandey, Anurag and Rahul, Chengot Sankaramenon},
  title =	{{Monotone Arithmetic Complexity of Graph Homomorphism Polynomials}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{83:1--83:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.83},
  URN =		{urn:nbn:de:0030-drops-164245},
  doi =		{10.4230/LIPIcs.ICALP.2022.83},
  annote =	{Keywords: Homomorphism polynomials, Monotone complexity, Algebraic complexity, Graph algorithms, Fine-grained complexity, Fixed-parameter algorithms and complexity, Treewidth, Pathwidth, Treedepth, Graph homomorphisms, Algebraic circuits, Algebraic branching programs, Algebraic formulas}
}
  • Refine by Type
  • 5 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 2 2025
  • 1 2022

  • Refine by Author
  • 1 Berkholz, Christoph
  • 1 Bhargav, C.S.
  • 1 Chen, Shiteng
  • 1 Curticapean, Radu
  • 1 Dawar, Anuj
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Algebraic complexity theory
  • 2 Theory of computation → Circuit complexity
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Computational complexity and cryptography
  • Show More...

  • Refine by Keyword
  • 2 algebraic complexity
  • 2 finite model theory
  • 2 homomorphisms
  • 2 treewidth
  • 1 Algebraic branching programs
  • 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