Search Results

Documents authored by Dörfler, Julian

Document
DOI: 10.4230/LIPIcs.MFCS.2025.23
Which Graph Motif Parameters Count?

Authors: Markus Bläser, Radu Curticapean, Julian Dörfler, and Christian Ikenmeyer

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

Abstract
For a fixed graph H, the function #Ind(H → ⋆) maps graphs G to the count of induced H-copies in G; this function obviously "counts something" in that it has a combinatorial interpretation. Linear combinations of such functions are called graph motif parameters and have recently received significant attention in counting complexity after a seminal paper by Curticapean, Dell and Marx (STOC'17). We show that, among linear combinations of functions #Ind(H → ⋆) involving only graphs H without isolated vertices, precisely those with positive integer coefficients maintain a combinatorial interpretation. It is important to note that graph motif parameters can be nonnegative for all inputs G, even when some coefficients are negative. Formally, we show that evaluating any graph motif parameter with a negative coefficient is impossible in an oracle variant of #P, where an implicit graph is accessed by oracle queries. Our proof follows the classification of the relativizing closure properties of #P by Hertrampf, Vollmer, and Wagner (SCT'95) and the framework developed by Ikenmeyer and Pak (STOC'22), but our application of the required Ramsey theorem turns out to be more subtle, as graphs do not have the required Ramsey property. Our techniques generalize from graphs to relational structures, including colored graphs. Vastly generalizing this, we introduce motif parameters over categories that count occurrences of sub-objects in the category. We then prove a general dichotomy theorem that characterizes which such parameters have a combinatorial interpretation. Using known results in Ramsey theory for categories, we obtain a dichotomy for motif parameters of finite vector spaces as well as parameter sets.
Cite as

Markus Bläser, Radu Curticapean, Julian Dörfler, and Christian Ikenmeyer. Which Graph Motif Parameters Count?. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.MFCS.2025.23,
  author =	{Bl\"{a}ser, Markus and Curticapean, Radu and D\"{o}rfler, Julian and Ikenmeyer, Christian},
  title =	{{Which Graph Motif Parameters Count?}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{23:1--23: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.23},
  URN =		{urn:nbn:de:0030-drops-241307},
  doi =		{10.4230/LIPIcs.MFCS.2025.23},
  annote =	{Keywords: Graph motif parameters, Combinatorics, Combinatorial Interpretability}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.144
Probabilistic and Causal Satisfiability: Constraining the Model

Authors: Markus Bläser, Julian Dörfler, Maciej Liśkiewicz, and Benito van der Zander

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

Abstract
We study the complexity of satisfiability problems in probabilistic and causal reasoning. Given random variables X₁, X₂,… over finite domains, the basic terms are probabilities of propositional formulas over atomic events X_i = x_i, such as ℙ(X₁ = x₁) or ℙ(X₁ = x₁ ∨ X₂ = x₂). The basic terms can be combined using addition (yielding linear terms) or multiplication (polynomial terms). The probabilistic satisfiability problem asks whether a joint probability distribution satisfies a Boolean combination of (in)equalities over such terms. Fagin et al. [Fagin et al., 1990] showed that for basic and linear terms, this problem is NP-complete, making it no harder than Boolean satisfiability, while Mossé et al. [Mossé et al., 2022] proved that for polynomial terms, it is complete for the existential theory of the reals. Pearl’s Causal Hierarchy (PCH) extends the probabilistic setting with interventional and counterfactual reasoning, enriching the expressiveness of the languages. However, Mossé et al. [Mossé et al., 2022] found that the complexity of satisfiability remains unchanged. Van der Zander et al. [van der Zander et al., 2023] showed that introducing a marginalization operator to languages induces a significant increase in complexity. We extend this line of work by adding two new dimensions to the problem by constraining the models. First, we fix the graph structure of the underlying structural causal model, motivated by settings like Pearl’s do-calculus, and give a nearly complete landscape across different arithmetics and PCH levels. Second, we study small models. While earlier work showed that satisfiable instances admit polynomial-size models, this is no longer guaranteed with compact marginalization. We characterize the complexities of satisfiability under small-model constraints across different settings.
Cite as

Markus Bläser, Julian Dörfler, Maciej Liśkiewicz, and Benito van der Zander. Probabilistic and Causal Satisfiability: Constraining the Model. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 144:1-144:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.ICALP.2025.144,
  author =	{Bl\"{a}ser, Markus and D\"{o}rfler, Julian and Li\'{s}kiewicz, Maciej and van der Zander, Benito},
  title =	{{Probabilistic and Causal Satisfiability: Constraining the Model}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{144:1--144: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.144},
  URN =		{urn:nbn:de:0030-drops-235214},
  doi =		{10.4230/LIPIcs.ICALP.2025.144},
  annote =	{Keywords: Existential theory of the real numbers, Computational complexity, Probabilistic logic, Structural Causal Models}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2024.13
PosSLP and Sum of Squares

Authors: Markus Bläser, Julian Dörfler, and Gorav Jindal

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract
The problem PosSLP is the problem of determining whether a given straight-line program (SLP) computes a positive integer. PosSLP was introduced by Allender et al. to study the complexity of numerical analysis (Allender et al., 2009). PosSLP can also be reformulated as the problem of deciding whether the integer computed by a given SLP can be expressed as the sum of squares of four integers, based on the well-known result by Lagrange in 1770, which demonstrated that every natural number can be represented as the sum of four non-negative integer squares. In this paper, we explore several natural extensions of this problem by investigating whether the positive integer computed by a given SLP can be written as the sum of squares of two or three integers. We delve into the complexity of these variations and demonstrate relations between the complexity of the original PosSLP problem and the complexity of these related problems. Additionally, we introduce a new intriguing problem called Div2SLP and illustrate how Div2SLP is connected to DegSLP and the problem of whether an SLP computes an integer expressible as the sum of three squares. By comprehending the connections between these problems, our results offer a deeper understanding of decision problems associated with SLPs and open avenues for further exciting research.
Cite as

Markus Bläser, Julian Dörfler, and Gorav Jindal. PosSLP and Sum of Squares. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.FSTTCS.2024.13,
  author =	{Bl\"{a}ser, Markus and D\"{o}rfler, Julian and Jindal, Gorav},
  title =	{{PosSLP and Sum of Squares}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.13},
  URN =		{urn:nbn:de:0030-drops-222028},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.13},
  annote =	{Keywords: PosSLP, Straight-line program, Polynomial identity testing, Sum of squares}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.13
The Existential Theory of the Reals with Summation Operators

Authors: Markus Bläser, Julian Dörfler, Maciej Liśkiewicz, and Benito van der Zander

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
To characterize the computational complexity of satisfiability problems for probabilistic and causal reasoning within Pearl’s Causal Hierarchy, van der Zander, Bläser, and Liśkiewicz [IJCAI 2023] introduce a new natural class, named succ-∃ℝ. This class can be viewed as a succinct variant of the well-studied class ∃ℝ based on the Existential Theory of the Reals (ETR). Analogously to ∃ℝ, succ-∃ℝ is an intermediate class between NEXP and EXPSPACE, the exponential versions of NP and PSPACE. The main contributions of this work are threefold. Firstly, we characterize the class succ-∃ℝ in terms of nondeterministic real Random-Access Machines (RAMs) and develop structural complexity theoretic results for real RAMs, including translation and hierarchy theorems. Notably, we demonstrate the separation of ∃ℝ and succ-∃ℝ. Secondly, we examine the complexity of model checking and satisfiability of fragments of existential second-order logic and probabilistic independence logic. We show succ-∃ℝ-completeness of several of these problems, for which the best-known complexity lower and upper bounds were previously NEXP-hardness and EXPSPACE, respectively. Thirdly, while succ-∃ℝ is characterized in terms of ordinary (non-succinct) ETR instances enriched by exponential sums and a mechanism to index exponentially many variables, in this paper, we prove that when only exponential sums are added, the corresponding class ∃ℝ^Σ is contained in PSPACE. We conjecture that this inclusion is strict, as this class is equivalent to adding a VNP-oracle to a polynomial time nondeterministic real RAM. Conversely, the addition of exponential products to ETR, yields PSPACE. Furthermore, we study the satisfiability problem for probabilistic reasoning, with the additional requirement of a small model, and prove that this problem is complete for ∃ℝ^Σ.
Cite as

Markus Bläser, Julian Dörfler, Maciej Liśkiewicz, and Benito van der Zander. The Existential Theory of the Reals with Summation Operators. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.ISAAC.2024.13,
  author =	{Bl\"{a}ser, Markus and D\"{o}rfler, Julian and Li\'{s}kiewicz, Maciej and van der Zander, Benito},
  title =	{{The Existential Theory of the Reals with Summation Operators}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.13},
  URN =		{urn:nbn:de:0030-drops-221407},
  doi =		{10.4230/LIPIcs.ISAAC.2024.13},
  annote =	{Keywords: Existential theory of the real numbers, Computational complexity, Probabilistic logic, Models of computation, Existential second order logic}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.134
Functional Closure Properties of Finite ℕ-Weighted Automata

Authors: Julian Dörfler and Christian Ikenmeyer

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

Abstract
We determine all functional closure properties of finite ℕ-weighted automata, even all multivariate ones, and in particular all multivariate polynomials. We also determine all univariate closure properties in the promise setting, and all multivariate closure properties under certain assumptions on the promise, in particular we determine all multivariate closure properties where the output vector lies on a monotone algebraic graph variety.
Cite as

Julian Dörfler and Christian Ikenmeyer. Functional Closure Properties of Finite ℕ-Weighted Automata. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 134:1-134:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dorfler_et_al:LIPIcs.ICALP.2024.134,
  author =	{D\"{o}rfler, Julian and Ikenmeyer, Christian},
  title =	{{Functional Closure Properties of Finite \mathbb{N}-Weighted Automata}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{134:1--134: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.134},
  URN =		{urn:nbn:de:0030-drops-202777},
  doi =		{10.4230/LIPIcs.ICALP.2024.134},
  annote =	{Keywords: Finite automata, weighted automata, counting, closure properties, algebraic varieties}
}
Document
DOI: 10.4230/LIPIcs.CCC.2021.29
On the Complexity of Evaluating Highest Weight Vectors

Authors: Markus Bläser, Julian Dörfler, and Christian Ikenmeyer

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
Geometric complexity theory (GCT) is an approach towards separating algebraic complexity classes through algebraic geometry and representation theory. Originally Mulmuley and Sohoni proposed (SIAM J Comput 2001, 2008) to use occurrence obstructions to prove Valiant’s determinant vs permanent conjecture, but recently Bürgisser, Ikenmeyer, and Panova (Journal of the AMS 2019) proved this impossible. However, fundamental theorems of algebraic geometry and representation theory grant that every lower bound in GCT can be proved by the use of so-called highest weight vectors (HWVs). In the setting of interest in GCT (namely in the setting of polynomials) we prove the NP-hardness of the evaluation of HWVs in general, and we give efficient algorithms if the treewidth of the corresponding Young-tableau is small, where the point of evaluation is concisely encoded as a noncommutative algebraic branching program! In particular, this gives a large new class of separating functions that can be efficiently evaluated at points with low (border) Waring rank. As a structural side result we prove that border Waring rank is bounded from above by the ABP width complexity.
Cite as

Markus Bläser, Julian Dörfler, and Christian Ikenmeyer. On the Complexity of Evaluating Highest Weight Vectors. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 29:1-29:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.CCC.2021.29,
  author =	{Bl\"{a}ser, Markus and D\"{o}rfler, Julian and Ikenmeyer, Christian},
  title =	{{On the Complexity of Evaluating Highest Weight Vectors}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{29:1--29:36},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.29},
  URN =		{urn:nbn:de:0030-drops-143036},
  doi =		{10.4230/LIPIcs.CCC.2021.29},
  annote =	{Keywords: Algebraic complexity theory, geometric complexity theory, algebraic branching program, Waring rank, border Waring rank, representation theory, highest weight vector, treewidth}
}
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 A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.51
On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions

Authors: Julian Dörfler, Christian Ikenmeyer, and Greta Panova

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

Abstract
Geometric Complexity Theory as initiated by Mulmuley and Sohoni in two papers (SIAM J Comput 2001, 2008) aims to separate algebraic complexity classes via representation theoretic multiplicities in coordinate rings of specific group varieties. We provide the first toy setting in which a separation can be achieved for a family of polynomials via these multiplicities. Mulmuley and Sohoni’s papers also conjecture that the vanishing behavior of multiplicities would be sufficient to separate complexity classes (so-called occurrence obstructions). The existence of such strong occurrence obstructions has been recently disproven in 2016 in two successive papers, Ikenmeyer-Panova (Adv. Math.) and Bürgisser-Ikenmeyer-Panova (J. AMS). This raises the question whether separating group varieties via representation theoretic multiplicities is stronger than separating them via occurrences. We provide first finite settings where a separation via multiplicities can be achieved, while the separation via occurrences is provably impossible. These settings are surprisingly simple and natural: We study the variety of products of homogeneous linear forms (the so-called Chow variety) and the variety of polynomials of bounded border Waring rank (i.e. a higher secant variety of the Veronese variety). As a side result we prove a slight generalization of Hermite’s reciprocity theorem, which proves Foulkes' conjecture for a new infinite family of cases.
Cite as

Julian Dörfler, Christian Ikenmeyer, and Greta Panova. On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dorfler_et_al:LIPIcs.ICALP.2019.51,
  author =	{D\"{o}rfler, Julian and Ikenmeyer, Christian and Panova, Greta},
  title =	{{On Geometric Complexity Theory: Multiplicity Obstructions Are Stronger Than Occurrence Obstructions}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{51:1--51:14},
  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.51},
  URN =		{urn:nbn:de:0030-drops-106276},
  doi =		{10.4230/LIPIcs.ICALP.2019.51},
  annote =	{Keywords: Algebraic complexity theory, geometric complexity theory, Waring rank, plethysm coefficients, occurrence obstructions, multiplicity obstructions}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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