21 Search Results for "Curticapean, Radu"

Document
DOI: 10.4230/LIPIcs.CCC.2024.31
Low-Depth Algebraic Circuit Lower Bounds over Any Field

Authors: Michael A. Forbes

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
The recent breakthrough of Limaye, Srinivasan and Tavenas [Limaye et al., 2022] (LST) gave the first super-polynomial lower bounds against low-depth algebraic circuits, for any field of zero (or sufficiently large) characteristic. It was an open question to extend this result to small-characteristic ([Limaye et al., 2022; Govindasamy et al., 2022; Fournier et al., 2023]), which in particular is relevant for an approach to prove superpolynomial AC⁰[p]-Frege lower bounds ([Govindasamy et al., 2022]). In this work, we prove super-polynomial algebraic circuit lower bounds against low-depth algebraic circuits over any field, with the same parameters as LST (or even matching the improved parameters of Bhargav, Dutta, and Saxena [Bhargav et al., 2022]). We give two proofs. The first is logical, showing that even though the proof of LST naively fails in small characteristic, the proof is sufficiently algebraic that generic transfer results imply the result over characteristic zero implies the result over all fields. Motivated by this indirect proof, we then proceed to give a second constructive proof, replacing the field-dependent set-multilinearization result of LST with a set-multilinearization that works over any field, by using the Binet-Minc identity [Minc, 1979].
Cite as

Michael A. Forbes. Low-Depth Algebraic Circuit Lower Bounds over Any Field. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{forbes:LIPIcs.CCC.2024.31,
  author =	{Forbes, Michael A.},
  title =	{{Low-Depth Algebraic Circuit Lower Bounds over Any Field}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.31},
  URN =		{urn:nbn:de:0030-drops-204271},
  doi =		{10.4230/LIPIcs.CCC.2024.31},
  annote =	{Keywords: algebraic circuits, lower bounds, low-depth circuits, positive characteristic}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.29
A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width

Authors: Narek Bojikian and Stefan Kratsch

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Given a graph G = (V,E), a set T ⊆ V, and an integer b, the Steiner Tree problem asks whether G has a connected subgraph H with at most b vertices that spans all of T. This work presents a 3^k⋅ n^𝒪(1) time one-sided Monte-Carlo algorithm for solving Steiner Tree when additionally a clique-expression of width k is provided. Known lower bounds for less expressive parameters imply that this dependence on the clique-width of G is optimal assuming the Strong Exponential-Time Hypothesis (SETH). Indeed our work establishes that the parameter dependence of Steiner Tree is the same for any graph parameter between cutwidth and clique-width, assuming SETH. Our work contributes to the program of determining the exact parameterized complexity of fundamental hard problems relative to structural graph parameters such as treewidth, which was initiated by Lokshtanov et al. [SODA 2011 & TALG 2018] and which by now has seen a plethora of results. Since the cut-and-count framework of Cygan et al. [FOCS 2011 & TALG 2022], connectivity problems have played a key role in this program as they pose many challenges for developing tight upper and lower bounds. Recently, Hegerfeld and Kratsch [ESA 2023] gave the first application of the cut-and-count technique to problems parameterized by clique-width and obtained tight bounds for Connected Dominating Set and Connected Vertex Cover, leaving open the complexity of other benchmark connectivity problems such as Steiner Tree and Feedback Vertex Set. Our algorithm for Steiner Tree does not follow the cut-and-count technique and instead works with the connectivity patterns of partial solutions. As a first technical contribution we identify a special family of so-called complete patterns that has strong (existential) representation properties, and using these at least one solution will be preserved. Furthermore, there is a family of 3^k basis patterns that (parity) represents the complete patterns, i.e., it has the same number of solutions modulo two. Our main technical contribution, a new technique called "isolating a representative," allows us to leverage both forms of representation (existential and parity). Both complete patterns and isolation of a representative will likely be applicable to other (connectivity) problems.
Cite as

Narek Bojikian and Stefan Kratsch. A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bojikian_et_al:LIPIcs.ICALP.2024.29,
  author =	{Bojikian, Narek and Kratsch, Stefan},
  title =	{{A Tight Monte-Carlo Algorithm for Steiner Tree Parameterized by Clique-Width}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{29:1--29:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.29},
  URN =		{urn:nbn:de:0030-drops-201728},
  doi =		{10.4230/LIPIcs.ICALP.2024.29},
  annote =	{Keywords: Parameterized complexity, Steiner tree, clique-width}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.34
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness

Authors: Barış Can Esmer, Jacob Focke, Dániel Marx, and Paweł Rzążewski

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
It is known for many algorithmic problems that if a tree decomposition of width t is given in the input, then the problem can be solved with exponential dependence on t. A line of research initiated by Lokshtanov, Marx, and Saurabh [SODA 2011] produced lower bounds showing that in many cases known algorithms already achieve the best possible exponential dependence on t, assuming the Strong Exponential-Time Hypothesis (SETH). The main message of this paper is showing that the same lower bounds can already be obtained in a much more restricted setting: informally, a graph consisting of a block of t vertices connected to components of constant size already has the same hardness as a general tree decomposition of width t. Formally, a (σ,δ)-hub is a set Q of vertices such that every component of Q has size at most σ and is adjacent to at most δ vertices of Q. We explore if the known tight lower bounds parameterized by the width of the given tree decomposition remain valid if we parameterize by the size of the given hub. - For every ε > 0, there are σ,δ > 0 such that Independent Set (equivalently Vertex Cover) cannot be solved in time (2-ε)^p⋅ n, even if a (σ, δ)-hub of size p is given in the input, assuming the SETH. This matches the earlier tight lower bounds parameterized by width of the tree decomposition. Similar tight bounds are obtained for Odd Cycle Transversal, Max Cut, q-Coloring, and edge/vertex deletions versions of q-Coloring. - For every ε > 0, there are σ,δ > 0 such that △-Partition cannot be solved in time (2-ε)^p ⋅ n, even if a (σ, δ)-hub of size p is given in the input, assuming the Set Cover Conjecture (SCC). In fact, we prove that this statement is equivalent to the SCC, thus it is unlikely that this could be proved assuming the SETH. - For Dominating Set, we can prove a non-tight lower bound ruling out (2-ε)^p ⋅ n^𝒪(1) algorithms, assuming either the SETH or the SCC, but this does not match the 3^p⋅ n^{𝒪(1)} upper bound. Thus our results reveal that, for many problems, the research on lower bounds on the dependence on tree width was never really about tree decompositions, but the real source of hardness comes from a much simpler structure. Additionally, we study if the same lower bounds can be obtained if σ and δ are fixed universal constants (not depending on ε). We show that lower bounds of this form are possible for Max Cut and the edge-deletion version of q-Coloring, under the Max 3-Sat Hypothesis (M3SH). However, no such lower bounds are possible for Independent Set, Odd Cycle Transversal, and the vertex-deletion version of q-Coloring: better than brute force algorithms are possible for every fixed (σ,δ).
Cite as

Barış Can Esmer, Jacob Focke, Dániel Marx, and Paweł Rzążewski. Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{canesmer_et_al:LIPIcs.ICALP.2024.34,
  author =	{Can Esmer, Bar{\i}\c{s} and Focke, Jacob and Marx, D\'{a}niel and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.34},
  URN =		{urn:nbn:de:0030-drops-201772},
  doi =		{10.4230/LIPIcs.ICALP.2024.34},
  annote =	{Keywords: Parameterized Complexity, Tight Bounds, Hub, Treewidth, Strong Exponential Time Hypothesis, Vertex Coloring, Vertex Deletion, Edge Deletion, Triangle Packing, Triangle Partition, Set Cover Hypothesis, Dominating Set}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.77
Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters

Authors: Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk, and Paweł Rzążewski

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
A homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H). In the graph homomorphism problem, denoted by Hom(H), the graph H is fixed and we need to determine if there exists a homomorphism from an instance graph G to H. We study the complexity of the problem parameterized by the cutwidth of G, i.e., we assume that G is given along with a linear ordering v_1,…,v_n of V(G) such that, for each i ∈ {1,…,n-1}, the number of edges with one endpoint in {v_1,…,v_i} and the other in {v_{i+1},…,v_n} is at most k. We aim, for each H, for algorithms for Hom(H) running in time c_H^k n^𝒪(1) and matching lower bounds that exclude c_H^{k⋅o(1)} n^𝒪(1) or c_H^{k(1-Ω(1))} n^𝒪(1) time algorithms under the (Strong) Exponential Time Hypothesis. In the paper we introduce a new parameter that we call mimsup(H). Our main contribution is strong evidence of a close connection between c_H and mimsup(H): - an information-theoretic argument that the number of states needed in a natural dynamic programming algorithm is at most mimsup(H)^k, - lower bounds that show that for almost all graphs H indeed we have c_H ≥ mimsup(H), assuming the (Strong) Exponential-Time Hypothesis, and - an algorithm with running time exp(𝒪(mimsup(H)⋅k log k)) n^𝒪(1). In the last result we do not need to assume that H is a fixed graph. Thus, as a consequence, we obtain that the problem of deciding whether G admits a homomorphism to H is fixed-parameter tractable, when parameterized by cutwidth of G and mimsup(H). The parameter mimsup(H) can be thought of as the p-th root of the maximum induced matching number in the graph obtained by multiplying p copies of H via a certain graph product, where p tends to infinity. It can also be defined as an asymptotic rank parameter of the adjacency matrix of H. Such parameters play a central role in, among others, algebraic complexity theory and additive combinatorics. Our results tightly link the parameterized complexity of a problem to such an asymptotic matrix parameter for the first time.
Cite as

Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk, and Paweł Rzążewski. Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 77:1-77:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{groenland_et_al:LIPIcs.ICALP.2024.77,
  author =	{Groenland, Carla and Mannens, Isja and Nederlof, Jesper and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Towards Tight Bounds for the Graph Homomorphism Problem Parameterized by Cutwidth via Asymptotic Matrix Parameters}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{77:1--77:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.77},
  URN =		{urn:nbn:de:0030-drops-202208},
  doi =		{10.4230/LIPIcs.ICALP.2024.77},
  annote =	{Keywords: graph homomorphism, cutwidth, asymptotic matrix parameters}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.114
Delineating Half-Integrality of the Erdős-Pósa Property for Minors: The Case of Surfaces

Authors: Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, and Sebastian Wiederrecht

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In 1986 Robertson and Seymour proved a generalization of the seminal result of Erdős and Pósa on the duality of packing and covering cycles: A graph has the Erdős-Pósa property for minors if and only if it is planar. In particular, for every non-planar graph H they gave examples showing that the Erdős-Pósa property does not hold for H. Recently, Liu confirmed a conjecture of Thomas and showed that every graph has the half-integral Erdős-Pósa property for minors. Liu’s proof is non-constructive and to this date, with the exception of a small number of examples, no constructive proof is known. In this paper, we initiate the delineation of the half-integrality of the Erdős-Pósa property for minors. We conjecture that for every graph H, there exists a unique (up to a suitable equivalence relation on graph parameters) graph parameter EP_H such that H has the Erdős-Pósa property in a minor-closed graph class 𝒢 if and only if sup{EP_H(G) ∣ G ∈ 𝒢} is finite. We prove this conjecture for the class ℋ of Kuratowski-connected shallow-vortex minors by showing that, for every non-planar H ∈ ℋ, the parameter EP_H(G) is precisely the maximum order of a Robertson-Seymour counterexample to the Erdős-Pósa property of H which can be found as a minor in G. Our results are constructive and imply, for the first time, parameterized algorithms that find either a packing, or a cover, or one of the Robertson-Seymour counterexamples, certifying the existence of a half-integral packing for the graphs in ℋ.
Cite as

Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos, and Sebastian Wiederrecht. Delineating Half-Integrality of the Erdős-Pósa Property for Minors: The Case of Surfaces. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 114:1-114:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{paul_et_al:LIPIcs.ICALP.2024.114,
  author =	{Paul, Christophe and Protopapas, Evangelos and Thilikos, Dimitrios M. and Wiederrecht, Sebastian},
  title =	{{Delineating Half-Integrality of the Erd\H{o}s-P\'{o}sa Property for Minors: The Case of Surfaces}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{114:1--114:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.114},
  URN =		{urn:nbn:de:0030-drops-202576},
  doi =		{10.4230/LIPIcs.ICALP.2024.114},
  annote =	{Keywords: Erd\H{o}s-P\'{o}sa property, Erd\H{o}s-P\'{o}sa pair, Graph parameters, Graph minors, Universal obstruction, Surface containment}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.68
Parameterised and Fine-Grained Subgraph Counting, Modulo 2

Authors: Leslie Ann Goldberg and Marc Roth

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Given a class of graphs ℋ, the problem ⊕Sub(ℋ) is defined as follows. The input is a graph H ∈ ℋ together with an arbitrary graph G. The problem is to compute, modulo 2, the number of subgraphs of G that are isomorphic to H. The goal of this research is to determine for which classes ℋ the problem ⊕Sub(ℋ) is fixed-parameter tractable (FPT), i.e., solvable in time f(|H|)⋅|G|^O(1). Curticapean, Dell, and Husfeldt (ESA 2021) conjectured that ⊕Sub(ℋ) is FPT if and only if the class of allowed patterns ℋ is matching splittable, which means that for some fixed B, every H ∈ ℋ can be turned into a matching (a graph in which every vertex has degree at most 1) by removing at most B vertices. Assuming the randomised Exponential Time Hypothesis, we prove their conjecture for (I) all hereditary pattern classes ℋ, and (II) all tree pattern classes, i.e., all classes ℋ such that every H ∈ ℋ is a tree. We also establish almost tight fine-grained upper and lower bounds for the case of hereditary patterns (I).
Cite as

Leslie Ann Goldberg and Marc Roth. Parameterised and Fine-Grained Subgraph Counting, Modulo 2. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 68:1-68:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.ICALP.2023.68,
  author =	{Goldberg, Leslie Ann and Roth, Marc},
  title =	{{Parameterised and Fine-Grained Subgraph Counting, Modulo 2}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{68:1--68:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel 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.2023.68},
  URN =		{urn:nbn:de:0030-drops-181200},
  doi =		{10.4230/LIPIcs.ICALP.2023.68},
  annote =	{Keywords: modular counting, parameterised complexity, fine-grained complexity, subgraph counting}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.16
On the VNP-Hardness of Some Monomial Symmetric Polynomials

Authors: Radu Curticapean, Nutan Limaye, and Srikanth Srinivasan

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
A polynomial P ∈ 𝔽[x_1,…,x_n] is said to be symmetric if it is invariant under any permutation of its input variables. The study of symmetric polynomials is a classical topic in mathematics, specifically in algebraic combinatorics and representation theory. More recently, they have been studied in several works in computer science, especially in algebraic complexity theory. In this paper, we prove the computational hardness of one of the most basic kinds of symmetric polynomials: the monomial symmetric polynomials, which are obtained by summing all distinct permutations of a single monomial. This family of symmetric functions is a natural basis for the space of symmetric polynomials (over any field), and generalizes many well-studied families such as the elementary symmetric polynomials and the power-sum symmetric polynomials. We show that certain families of monomial symmetric polynomials are VNP-complete with respect to oracle reductions. This stands in stark contrast to the case of elementary and power symmetric polynomials, both of which have constant-depth circuits of polynomial size.
Cite as

Radu Curticapean, Nutan Limaye, and Srikanth Srinivasan. On the VNP-Hardness of Some Monomial Symmetric Polynomials. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{curticapean_et_al:LIPIcs.FSTTCS.2022.16,
  author =	{Curticapean, Radu and Limaye, Nutan and Srinivasan, Srikanth},
  title =	{{On the VNP-Hardness of Some Monomial Symmetric Polynomials}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.16},
  URN =		{urn:nbn:de:0030-drops-174081},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.16},
  annote =	{Keywords: algebraic complexity, symmetric polynomial, permanent, Sidon set}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.38
Determinants from Homomorphisms

Authors: Radu Curticapean

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
We give a new combinatorial explanation for well-known relations between determinants and traces of matrix powers. Such relations can be used to obtain polynomial-time and poly-logarithmic space algorithms for the determinant. Our new explanation avoids linear-algebraic arguments and instead exploits a classical connection between subgraph and homomorphism counts.
Cite as

Radu Curticapean. Determinants from Homomorphisms. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 38:1-38:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{curticapean:LIPIcs.ESA.2022.38,
  author =	{Curticapean, Radu},
  title =	{{Determinants from Homomorphisms}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{38:1--38:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.38},
  URN =		{urn:nbn:de:0030-drops-169767},
  doi =		{10.4230/LIPIcs.ESA.2022.38},
  annote =	{Keywords: determinant, homomorphisms, matrix trace, Newton identities}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.34
Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths

Authors: Radu Curticapean, Holger Dell, and Thore Husfeldt

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
We systematically investigate the complexity of counting subgraph patterns modulo fixed integers. For example, it is known that the parity of the number of k-matchings can be determined in polynomial time by a simple reduction to the determinant. We generalize this to an n^{f(t,s)}-time algorithm to compute modulo 2^t the number of subgraph occurrences of patterns that are s vertices away from being matchings. This shows that the known polynomial-time cases of subgraph detection (Jansen and Marx, SODA 2015) carry over into the setting of counting modulo 2^t. Complementing our algorithm, we also give a simple and self-contained proof that counting k-matchings modulo odd integers q is {Mod}_q W[1]-complete and prove that counting k-paths modulo 2 is ⊕W[1]-complete, answering an open question by Björklund, Dell, and Husfeldt (ICALP 2015).
Cite as

Radu Curticapean, Holger Dell, and Thore Husfeldt. Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{curticapean_et_al:LIPIcs.ESA.2021.34,
  author =	{Curticapean, Radu and Dell, Holger and Husfeldt, Thore},
  title =	{{Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.34},
  URN =		{urn:nbn:de:0030-drops-146154},
  doi =		{10.4230/LIPIcs.ESA.2021.34},
  annote =	{Keywords: Counting complexity, matchings, paths, subgraphs, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.84
Parameterized (Modular) Counting and Cayley Graph Expanders

Authors: Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, and Alina Vdovina

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We study the problem #EdgeSub(Φ) of counting k-edge subgraphs satisfying a given graph property Φ in a large host graph G. Building upon the breakthrough result of Curticapean, Dell and Marx (STOC 17), we express the number of such subgraphs as a finite linear combination of graph homomorphism counts and derive the complexity of computing this number by studying its coefficients. Our approach relies on novel constructions of low-degree Cayley graph expanders of p-groups, which might be of independent interest. The properties of those expanders allow us to analyse the coefficients in the aforementioned linear combinations over the field 𝔽_p which gives us significantly more control over the cancellation behaviour of the coefficients. Our main result is an exhaustive and fine-grained complexity classification of #EdgeSub(Φ) for minor-closed properties Φ, closing the missing gap in previous work by Roth, Schmitt and Wellnitz (ICALP 21). Additionally, we observe that our methods also apply to modular counting. Among others, we obtain novel intractability results for the problems of counting k-forests and matroid bases modulo a prime p. Furthermore, from an algorithmic point of view, we construct algorithms for the problems of counting k-paths and k-cycles modulo 2 that outperform the best known algorithms for their non-modular counterparts. In the course of our investigations we also provide an exhaustive parameterized complexity classification for the problem of counting graph homomorphisms modulo a prime p.
Cite as

Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, and Alina Vdovina. Parameterized (Modular) Counting and Cayley Graph Expanders. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 84:1-84:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{peyerimhoff_et_al:LIPIcs.MFCS.2021.84,
  author =	{Peyerimhoff, Norbert and Roth, Marc and Schmitt, Johannes and Stix, Jakob and Vdovina, Alina},
  title =	{{Parameterized (Modular) Counting and Cayley Graph Expanders}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{84:1--84:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.84},
  URN =		{urn:nbn:de:0030-drops-145246},
  doi =		{10.4230/LIPIcs.MFCS.2021.84},
  annote =	{Keywords: Cayley graphs, counting complexity, expander graphs, fine-grained complexity, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.8
Parameterized Streaming Algorithms for Min-Ones d-SAT

Authors: Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, and Saket Saurabh

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has a satisfying assignment which sets at most k variables to 1. In the parameterized streaming model, input is provided as a stream, just as in the usual streaming model. A key difference is that the bound on the read-write memory available to the algorithm is O(f(k) log n) (f: N -> N, a computable function) as opposed to the O(log n) bound of the usual streaming model. The other important difference is that the number of passes the algorithm makes over its input must be a (preferably small) function of k. We design a (k + 1)-pass parameterized streaming algorithm that solves Min-Ones d-SAT (d >= 2) using space O((kd^(ck) + k^d)log n) (c > 0, a constant) and a (d + 1)^k-pass algorithm that uses space O(k log n). We also design a streaming kernelization for Min-Ones 2-SAT that makes (k + 2) passes and uses space O(k^6 log n) to produce a kernel with O(k^6) clauses. To complement these positive results, we show that any k-pass algorithm for or Min-Ones d-SAT (d >= 2) requires space Omega(max{n^(1/k) / 2^k, log(n / k)}) on instances (F, k). This is achieved via a reduction from the streaming problem POT Pointer Chasing (Guha and McGregor [ICALP 2008]), which might be of independent interest. Given this, our (k + 1)-pass parameterized streaming algorithm is the best possible, inasmuch as the number of passes is concerned. In contrast to the results of Fafianie and Kratsch [MFCS 2014] and Chitnis et al. [SODA 2015], who independently showed that there are 1-pass parameterized streaming algorithms for Vertex Cover (a restriction of Min-Ones 2-SAT), we show using lower bounds from Communication Complexity that for any d >= 1, a 1-pass streaming algorithm for Min-Ones d-SAT requires space Omega(n). This excludes the possibility of a 1-pass parameterized streaming algorithm for the problem. Additionally, we show that any p-pass algorithm for the problem requires space Omega(n/p).
Cite as

Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, and Saket Saurabh. Parameterized Streaming Algorithms for Min-Ones d-SAT. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.FSTTCS.2019.8,
  author =	{Agrawal, Akanksha and Biswas, Arindam and Bonnet, \'{E}douard and Brettell, Nick and Curticapean, Radu and Marx, D\'{a}niel and Miltzow, Tillmann and Raman, Venkatesh and Saurabh, Saket},
  title =	{{Parameterized Streaming Algorithms for Min-Ones d-SAT}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.8},
  URN =		{urn:nbn:de:0030-drops-115708},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.8},
  annote =	{Keywords: min, ones, sat, d-sat, parameterized, kernelization, streaming, space, efficient, algorithm, parameter}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.3
Parameterized Valiant’s Classes

Authors: Markus Bläser and Christian Engels

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
We define a theory of parameterized algebraic complexity classes in analogy to parameterized Boolean counting classes. We define the classes VFPT and VW[t], which mirror the Boolean counting classes #FPT and #W[t], and define appropriate reductions and completeness notions. Our main contribution is the VW[1]-completeness proof of the parameterized clique family. This proof is far more complicated than in the Boolean world. It requires some new concepts like composition theorems for bounded exponential sums and Boolean-arithmetic formulas. In addition, we also look at two polynomials linked to the permanent with vastly different parameterized complexity.
Cite as

Markus Bläser and Christian Engels. Parameterized Valiant’s Classes. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.IPEC.2019.3,
  author =	{Bl\"{a}ser, Markus and Engels, Christian},
  title =	{{Parameterized Valiant’s Classes}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.3},
  URN =		{urn:nbn:de:0030-drops-114648},
  doi =		{10.4230/LIPIcs.IPEC.2019.3},
  annote =	{Keywords: Algebraic complexity theory, parameterized complexity theory, Valiant’s classes}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.25
Patching Colors with Tensors

Authors: Cornelius Brand

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We describe a generic way of exponentially speeding up algorithms which rely on Color-Coding by using the recently introduced technique of Extensor-Coding (Brand, Dell and Husfeldt, STOC 2018). To demonstrate the usefulness of this "patching" of Color-Coding algorithms, we apply it ad hoc to the exponential-space algorithms given in Gutin et al. (Journal Comp. Sys. Sci. 2018) and obtain the fastest known deterministic algorithms for, among others, the k-internal out-branching and k-internal spanning tree problems. To realize these technical advances, we make qualitative progress in a special case of the detection of multilinear monomials in multivariate polynomials: We give the first deterministic fixed-parameter tractable algorithm for the k-multilinear detection problem on a class of arithmetic circuits that may involve cancellations, as long as the computed polynomial is promised to satisfy a certain natural condition. Furthermore, we explore the limitations of using this very approach to speed up algorithms by determining exactly the dimension of a crucial subalgebra of extensors that arises naturally in the instantiation of the technique: It is equal to F_{2k+1}, the kth odd term in the Fibonacci sequence. To determine this dimension, we use tools from the theory of Gröbner bases, and the studied algebraic object may be of independent interest. We note that the asymptotic bound of F_{2k+1} ~~ phi^(2k) = O(2.619^k) curiously coincides with the running time bound on one of the fastest algorithms for the k-path problem based on representative sets due to Fomin et al. (JACM 2016). Here, phi is the golden ratio.
Cite as

Cornelius Brand. Patching Colors with Tensors. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{brand:LIPIcs.ESA.2019.25,
  author =	{Brand, Cornelius},
  title =	{{Patching Colors with Tensors}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{25:1--25:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.25},
  URN =		{urn:nbn:de:0030-drops-111467},
  doi =		{10.4230/LIPIcs.ESA.2019.25},
  annote =	{Keywords: Color-Coding, Extensor-Coding, internal out-branching, colorful problems, algebraic algorithms, multilinear detection, deterministic algorithms, exterior algebra}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.26
Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness

Authors: Julian Dörfler, Marc Roth, Johannes Schmitt, and Philip Wellnitz

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
We study the problem #IndSub(Phi) of counting all induced subgraphs of size k in a graph G that satisfy the property Phi. This problem was introduced by Jerrum and Meeks and shown to be #W[1]-hard when parameterized by k for some families of properties Phi including, among others, connectivity [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Very recently [IPEC 18], two of the authors introduced a novel technique for the complexity analysis of #IndSub(Phi), inspired by the "topological approach to evasiveness" of Kahn, Saks and Sturtevant [FOCS 83] and the framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], allowing them to prove hardness of a wide range of properties Phi. In this work, we refine this technique for graph properties that are non-trivial on edge-transitive graphs with a prime power number of edges. In particular, we fully classify the case of monotone bipartite graph properties: It is shown that, given any graph property Phi that is closed under the removal of vertices and edges, and that is non-trivial for bipartite graphs, the problem #IndSub(Phi) is #W[1]-hard and cannot be solved in time f(k)* n^{o(k)} for any computable function f, unless the Exponential Time Hypothesis fails. This holds true even if the input graph is restricted to be bipartite and counting is done modulo a fixed prime. A similar result is shown for properties that are closed under the removal of edges only.
Cite as

Julian Dörfler, Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting Induced Subgraphs: An Algebraic Approach to #W[1]-hardness. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dorfler_et_al:LIPIcs.MFCS.2019.26,
  author =	{D\"{o}rfler, Julian and Roth, Marc and Schmitt, Johannes and Wellnitz, Philip},
  title =	{{Counting Induced Subgraphs: An Algebraic Approach to #W\lbrack1\rbrack-hardness}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.26},
  URN =		{urn:nbn:de:0030-drops-109703},
  doi =		{10.4230/LIPIcs.MFCS.2019.26},
  annote =	{Keywords: counting complexity, edge-transitive graphs, graph homomorphisms, induced subgraphs, parameterized complexity}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2019.113
Counting Answers to Existential Questions (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors: Holger Dell, Marc Roth, and Philip Wellnitz

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Conjunctive queries select and are expected to return certain tuples from a relational database. We study the potentially easier problem of counting all selected tuples, rather than enumerating them. In particular, we are interested in the problem’s parameterized and data complexity, where the query is considered to be small or even fixed, and the database is considered to be large. We identify two structural parameters for conjunctive queries that capture their inherent complexity: The dominating star size and the linked matching number. If the dominating star size of a conjunctive query is large, then we show that counting solution tuples to the query is at least as hard as counting dominating sets, which yields a fine-grained complexity lower bound under the Strong Exponential Time Hypothesis (SETH) as well as a #W[2]-hardness result in parameterized complexity. Moreover, if the linked matching number of a conjunctive query is large, then we show that the structure of the query is so rich that arbitrary queries up to a certain size can be encoded into it; in the language of parameterized complexity, this essentially establishes a #A[2]-completeness result. Using ideas stemming from Lovász (1967), we lift complexity results from the class of conjunctive queries to arbitrary existential or universal formulas that might contain inequalities and negations on constraints over the free variables. As a consequence, we obtain a complexity classification that refines and generalizes previous results of Chen, Durand, and Mengel (ToCS 2015; ICDT 2015; PODS 2016) for conjunctive queries and of Curticapean and Marx (FOCS 2014) for the subgraph counting problem. Our proof also relies on graph minors, and we show a strengthening of the Excluded-Grid-Theorem which might be of independent interest: If the linked matching number (and thus the treewidth) is large, then not only can we find a large grid somewhere in the graph, but we can find a large grid whose diagonal has disjoint paths leading into an assumed node-well-linked set.
Cite as

Holger Dell, Marc Roth, and Philip Wellnitz. Counting Answers to Existential Questions (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 113:1-113:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dell_et_al:LIPIcs.ICALP.2019.113,
  author =	{Dell, Holger and Roth, Marc and Wellnitz, Philip},
  title =	{{Counting Answers to Existential Questions}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{113:1--113:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.113},
  URN =		{urn:nbn:de:0030-drops-106894},
  doi =		{10.4230/LIPIcs.ICALP.2019.113},
  annote =	{Keywords: Conjunctive queries, graph homomorphisms, counting complexity, parameterized complexity, fine-grained complexity}
}
  • Refine by Author
  • 10 Curticapean, Radu
  • 5 Dell, Holger
  • 5 Roth, Marc
  • 2 Fomin, Fedor V.
  • 2 Goldberg, Leslie Ann
  • Show More...

  • Refine by Classification
  • 7 Theory of computation → Parameterized complexity and exact algorithms
  • 6 Theory of computation → Problems, reductions and completeness
  • 4 Mathematics of computing → Graph theory
  • 3 Mathematics of computing → Combinatorics
  • 3 Theory of computation → Algebraic complexity theory
  • Show More...

  • Refine by Keyword
  • 7 counting complexity
  • 7 parameterized complexity
  • 3 fine-grained complexity
  • 3 matchings
  • 2 graph homomorphisms
  • Show More...

  • Refine by Type
  • 21 document

  • Refine by Publication Year
  • 6 2019
  • 5 2024
  • 2 2016
  • 2 2017
  • 2 2021
  • Show More...

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact