12 Search Results for "Ikenmeyer, Christian"

Document
DOI: 10.4230/LIPIcs.STACS.2024.30
Fixed-Parameter Debordering of Waring Rank

Authors: Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
Border complexity measures are defined via limits (or topological closures), so that any function which can approximated arbitrarily closely by low complexity functions itself has low border complexity. Debordering is the task of proving an upper bound on some non-border complexity measure in terms of a border complexity measure, thus getting rid of limits. Debordering is at the heart of understanding the difference between Valiant’s determinant vs permanent conjecture, and Mulmuley and Sohoni’s variation which uses border determinantal complexity. The debordering of matrix multiplication tensors by Bini played a pivotal role in the development of efficient matrix multiplication algorithms. Consequently, debordering finds applications in both establishing computational complexity lower bounds and facilitating algorithm design. Currently, very few debordering results are known. In this work, we study the question of debordering the border Waring rank of polynomials. Waring and border Waring rank are very well studied measures in the context of invariant theory, algebraic geometry, and matrix multiplication algorithms. For the first time, we obtain a Waring rank upper bound that is exponential in the border Waring rank and only linear in the degree. All previous known results were exponential in the degree. For polynomials with constant border Waring rank, our results imply an upper bound on the Waring rank linear in degree, which previously was only known for polynomials with border Waring rank at most 5.
Cite as

Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov. Fixed-Parameter Debordering of Waring Rank. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.STACS.2024.30,
  author =	{Dutta, Pranjal and Gesmundo, Fulvio and Ikenmeyer, Christian and Jindal, Gorav and Lysikov, Vladimir},
  title =	{{Fixed-Parameter Debordering of Waring Rank}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.30},
  URN =		{urn:nbn:de:0030-drops-197403},
  doi =		{10.4230/LIPIcs.STACS.2024.30},
  annote =	{Keywords: border complexity, Waring rank, debordering, apolarity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.31
On the Power of Border Width-2 ABPs over Fields of Characteristic 2

Authors: Pranjal Dutta, Christian Ikenmeyer, Balagopal Komarath, Harshil Mittal, Saraswati Girish Nanoti, and Dhara Thakkar

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
The celebrated result by Ben-Or and Cleve [SICOMP92] showed that algebraic formulas are polynomially equivalent to width-3 algebraic branching programs (ABP) for computing polynomials. i.e., VF = VBP₃. Further, there are simple polynomials, such as ∑_{i = 1}⁸ x_i y_i, that cannot be computed by width-2 ABPs [Allender and Wang, CC16]. Bringmann, Ikenmeyer and Zuiddam, [JACM18], on the other hand, studied these questions in the setting of approximate (i.e., border complexity) computation, and showed the universality of border width-2 ABPs, over fields of characteristic ≠ 2. In particular, they showed that polynomials that can be approximated by formulas can also be approximated (with only a polynomial blowup in size) by width-2 ABPs, i.e., VF ̅ = VBP₂ ̅. The power of border width-2 algebraic branching programs when the characteristic of the field is 2 was left open. In this paper, we show that width-2 ABPs can approximate every polynomial irrespective of the field characteristic. We show that any polynomial f with 𝓁 monomials and with at most t odd-power indeterminates per monomial can be approximated by 𝒪(𝓁⋅ (deg(f)+2^t))-size width-2 ABPs. Since 𝓁 and t are finite, this proves universality of border width-2 ABPs. For univariate polynomials, we improve this upper-bound from O(deg(f)²) to O(deg(f)). Moreover, we show that, if a polynomial f can be approximated by small formulas, then the polynomial f^d, for some small power d, can be approximated by small width-2 ABPs. Therefore, even over fields of characteristic two, border width-2 ABPs are a reasonably powerful computational model. Our construction works over any field.
Cite as

Pranjal Dutta, Christian Ikenmeyer, Balagopal Komarath, Harshil Mittal, Saraswati Girish Nanoti, and Dhara Thakkar. On the Power of Border Width-2 ABPs over Fields of Characteristic 2. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.STACS.2024.31,
  author =	{Dutta, Pranjal and Ikenmeyer, Christian and Komarath, Balagopal and Mittal, Harshil and Nanoti, Saraswati Girish and Thakkar, Dhara},
  title =	{{On the Power of Border Width-2 ABPs over Fields of Characteristic 2}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{31:1--31:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.31},
  URN =		{urn:nbn:de:0030-drops-197419},
  doi =		{10.4230/LIPIcs.STACS.2024.31},
  annote =	{Keywords: Algebraic branching programs, border complexity, characteristic 2}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.43
Homogeneous Algebraic Complexity Theory and Algebraic Formulas

Authors: Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We study algebraic complexity classes and their complete polynomials under homogeneous linear projections, not just under the usual affine linear projections that were originally introduced by Valiant in 1979. These reductions are weaker yet more natural from a geometric complexity theory (GCT) standpoint, because the corresponding orbit closure formulations do not require the padding of polynomials. We give the first complete polynomials for VF, the class of sequences of polynomials that admit small algebraic formulas, under homogeneous linear projections: The sum of the entries of the non-commutative elementary symmetric polynomial in 3 by 3 matrices of homogeneous linear forms. Even simpler variants of the elementary symmetric polynomial are hard for the topological closure of a large subclass of VF: the sum of the entries of the non-commutative elementary symmetric polynomial in 2 by 2 matrices of homogeneous linear forms, and homogeneous variants of the continuant polynomial (Bringmann, Ikenmeyer, Zuiddam, JACM '18). This requires a careful study of circuits with arity-3 product gates.
Cite as

Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, and Vladimir Lysikov. Homogeneous Algebraic Complexity Theory and Algebraic Formulas. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 43:1-43:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dutta_et_al:LIPIcs.ITCS.2024.43,
  author =	{Dutta, Pranjal and Gesmundo, Fulvio and Ikenmeyer, Christian and Jindal, Gorav and Lysikov, Vladimir},
  title =	{{Homogeneous Algebraic Complexity Theory and Algebraic Formulas}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{43:1--43:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.43},
  URN =		{urn:nbn:de:0030-drops-195713},
  doi =		{10.4230/LIPIcs.ITCS.2024.43},
  annote =	{Keywords: Homogeneous polynomials, Waring rank, Arithmetic formulas, Border complexity, Geometric Complexity theory, Symmetric polynomials}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.74
Karchmer-Wigderson Games for Hazard-Free Computation

Authors: Christian Ikenmeyer, Balagopal Komarath, and Nitin Saurabh

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog of the classical Boolean Karchmer-Wigderson game. Therefore, it acts as a bridge between the existing monotone and general games. Using this game, we prove hazard-free formula size and depth lower bounds that are provably stronger than those possible by the standard technique of transferring results from monotone complexity in a black-box fashion. For the multiplexer function we give (1) a hazard-free formula of optimal size and (2) an improved low-depth hazard-free formula of almost optimal size and (3) a hazard-free formula with alternation depth 2 that has optimal depth. We then use our optimal constructions to obtain an improved universal worst-case hazard-free formula size upper bound. We see our results as a step towards establishing hazard-free computation as an independent missing link between Boolean complexity and monotone complexity.
Cite as

Christian Ikenmeyer, Balagopal Komarath, and Nitin Saurabh. Karchmer-Wigderson Games for Hazard-Free Computation. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 74:1-74:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ikenmeyer_et_al:LIPIcs.ITCS.2023.74,
  author =	{Ikenmeyer, Christian and Komarath, Balagopal and Saurabh, Nitin},
  title =	{{Karchmer-Wigderson Games for Hazard-Free Computation}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{74:1--74:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.74},
  URN =		{urn:nbn:de:0030-drops-175775},
  doi =		{10.4230/LIPIcs.ITCS.2023.74},
  annote =	{Keywords: Hazard-free computation, monotone computation, Karchmer-Wigderson games, communication complexity, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.20
Degree-Restricted Strength Decompositions and Algebraic Branching Programs

Authors: Fulvio Gesmundo, Purnata Ghosal, Christian Ikenmeyer, and Vladimir Lysikov

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

Abstract
We analyze Kumar’s recent quadratic algebraic branching program size lower bound proof method (CCC 2017) for the power sum polynomial. We present a refinement of this method that gives better bounds in some cases. The lower bound relies on Noether-Lefschetz type conditions on the hypersurface defined by the homogeneous polynomial. In the explicit example that we provide, the lower bound is proved resorting to classical intersection theory. Furthermore, we use similar methods to improve the known lower bound methods for slice rank of polynomials. We consider a sequence of polynomials that have been studied before by Shioda and show that for these polynomials the improved lower bound matches the known upper bound.
Cite as

Fulvio Gesmundo, Purnata Ghosal, Christian Ikenmeyer, and Vladimir Lysikov. Degree-Restricted Strength Decompositions and Algebraic Branching Programs. 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. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gesmundo_et_al:LIPIcs.FSTTCS.2022.20,
  author =	{Gesmundo, Fulvio and Ghosal, Purnata and Ikenmeyer, Christian and Lysikov, Vladimir},
  title =	{{Degree-Restricted Strength Decompositions and Algebraic Branching Programs}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{20:1--20:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.20},
  URN =		{urn:nbn:de:0030-drops-174127},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.20},
  annote =	{Keywords: Lower bounds, Slice rank, Strength of polynomials, Algebraic branching programs}
}
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-dev.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.2020.72
Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests

Authors: Janaky Murthy, Vineet Nair, and Chandan Saha

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Equivalence testing for a polynomial family {g_m}_{m ∈ ℕ} over a field 𝔽 is the following problem: Given black-box access to an n-variate polynomial f({𝐱}), where n is the number of variables in g_m for some m ∈ ℕ, check if there exists an A ∈ GL(n,𝔽) such that f({𝐱}) = g_m(A{𝐱}). If yes, then output such an A. The complexity of equivalence testing has been studied for a number of important polynomial families, including the determinant (Det) and the family of iterated matrix multiplication polynomials. Two popular variants of the iterated matrix multiplication polynomial are: IMM_{w,d} (the (1,1) entry of the product of d many w× w symbolic matrices) and Tr-IMM_{w,d} (the trace of the product of d many w× w symbolic matrices). The families - Det, IMM and Tr-IMM - are VBP-complete under p-projections, and so, in this sense, they have the same complexity. But, do they have the same equivalence testing complexity? We show that the answer is "yes" for Det and Tr-IMM (modulo the use of randomness). The above result may appear a bit surprising as the complexity of equivalence testing for IMM and that for Det are quite different over ℚ: a randomized poly-time equivalence testing for IMM over ℚ is known [Neeraj Kayal et al., 2019], whereas [Ankit Garg et al., 2019] showed that equivalence testing for Det over ℚ is integer factoring hard (under randomized reductions and assuming GRH). To our knowledge, the complexity of equivalence testing for Tr-IMM was not known before this work. We show that, despite the syntactic similarity between IMM and Tr-IMM, equivalence testing for Tr-IMM and that for Det are randomized poly-time Turing reducible to each other over any field of characteristic zero or sufficiently large. The result is obtained by connecting the two problems via another well-studied problem in computer algebra, namely the full matrix algebra isomorphism problem (FMAI). In particular, we prove the following: 1) Testing equivalence of polynomials to Tr-IMM_{w,d}, for d ≥ 3 and w ≥ 2, is randomized polynomial-time Turing reducible to testing equivalence of polynomials to Det_w, the determinant of the w × w matrix of formal variables. (Here, d need not be a constant.) 2) FMAI is randomized polynomial-time Turing reducible to equivalence testing (in fact, to tensor isomorphism testing) for the family of matrix multiplication tensors {Tr-IMM_{w,3}}_{w ∈ ℕ}. These results, in conjunction with the randomized poly-time reduction (shown in [Ankit Garg et al., 2019]) from determinant equivalence testing to FMAI, imply that the four problems - FMAI, equivalence testing for Tr-IMM and for Det, and the 3-tensor isomorphism problem for the family of matrix multiplication tensors - are randomized poly-time equivalent under Turing reductions.
Cite as

Janaky Murthy, Vineet Nair, and Chandan Saha. Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 72:1-72:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{murthy_et_al:LIPIcs.MFCS.2020.72,
  author =	{Murthy, Janaky and Nair, Vineet and Saha, Chandan},
  title =	{{Randomized Polynomial-Time Equivalence Between Determinant and Trace-IMM Equivalence Tests}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{72:1--72:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.72},
  URN =		{urn:nbn:de:0030-drops-127419},
  doi =		{10.4230/LIPIcs.MFCS.2020.72},
  annote =	{Keywords: equivalence testing, determinant, trace of the matrix product, full-matrix algebra isomorphism}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.12
Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings

Authors: Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Oliveira, Michael Walter, and Avi Wigderson

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
We consider the problem of computing succinct encodings of lists of generators for invariant rings for group actions. Mulmuley conjectured that there are always polynomial sized such encodings for invariant rings of SL_n(ℂ)-representations. We provide simple examples that disprove this conjecture (under standard complexity assumptions). We develop a general framework, denoted algebraic circuit search problems, that captures many important problems in algebraic complexity and computational invariant theory. This framework encompasses various proof systems in proof complexity and some of the central problems in invariant theory as exposed by the Geometric Complexity Theory (GCT) program, including the aforementioned problem of computing succinct encodings for generators for invariant rings.
Cite as

Ankit Garg, Christian Ikenmeyer, Visu Makam, Rafael Oliveira, Michael Walter, and Avi Wigderson. Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{garg_et_al:LIPIcs.CCC.2020.12,
  author =	{Garg, Ankit and Ikenmeyer, Christian and Makam, Visu and Oliveira, Rafael and Walter, Michael and Wigderson, Avi},
  title =	{{Search Problems in Algebraic Complexity, GCT, and Hardness of Generators for Invariant Rings}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.12},
  URN =		{urn:nbn:de:0030-drops-125645},
  doi =		{10.4230/LIPIcs.CCC.2020.12},
  annote =	{Keywords: generators for invariant rings, succinct encodings}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.21
Algebraic Branching Programs, Border Complexity, and Tangent Spaces

Authors: Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most k is Zariski-closed, an important property in geometric complexity theory. It follows that approximations cannot help to reduce the required ABP width. It was mentioned by Forbes that this result would probably break when going from single-(source,sink) ABPs to trace ABPs. We prove that this is correct. Moreover, we study the commutative monotone setting and prove a result similar to Nisan, but concerning the analytic closure. We observe the same behavior here: The set of polynomials with ABP width complexity at most k is closed for single-(source,sink) ABPs and not closed for trace ABPs. The proofs reveal an intriguing connection between tangent spaces and the vector space of flows on the ABP. We close with additional observations on VQP and the closure of VNP which allows us to establish a separation between the two classes.
Cite as

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, and Nitin Saurabh. Algebraic Branching Programs, Border Complexity, and Tangent Spaces. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.CCC.2020.21,
  author =	{Bl\"{a}ser, Markus and Ikenmeyer, Christian and Mahajan, Meena and Pandey, Anurag and Saurabh, Nitin},
  title =	{{Algebraic Branching Programs, Border Complexity, and Tangent Spaces}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{21:1--21:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.21},
  URN =		{urn:nbn:de:0030-drops-125733},
  doi =		{10.4230/LIPIcs.CCC.2020.21},
  annote =	{Keywords: Algebraic Branching Programs, Border Complexity, Tangent Spaces, Lower Bounds, Geometric Complexity Theory, Flows, VQP, VNP}
}
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-dev.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
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-dev.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}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.20
On Algebraic Branching Programs of Small Width

Authors: Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the class of polynomials that can be approximated arbitrarily closely by polynomials in VP_e. We describe VP_e-bar with a strikingly simple complete polynomial (in characteristic different from 2) whose recursive definition is similar to the Fibonacci numbers. Further understanding this polynomial seems to be a promising route to new formula lower bounds. Our methods are rooted in the study of ABPs of small constant width. In 1992 Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction lead to the aforementioned characterization of VP_e-bar. As a natural continuation of this work we prove that the class VNP can be described as the class of families that admit a hypercube summation of polynomially bounded dimension over a product of polynomially many affine linear forms. This gives the first separations of algebraic complexity classes from their nondeterministic analogs.
Cite as

Karl Bringmann, Christian Ikenmeyer, and Jeroen Zuiddam. On Algebraic Branching Programs of Small Width. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 20:1-20:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.CCC.2017.20,
  author =	{Bringmann, Karl and Ikenmeyer, Christian and Zuiddam, Jeroen},
  title =	{{On Algebraic Branching Programs of Small Width}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{20:1--20:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.20},
  URN =		{urn:nbn:de:0030-drops-75217},
  doi =		{10.4230/LIPIcs.CCC.2017.20},
  annote =	{Keywords: algebraic branching programs, algebraic complexity theory, border complexity, formula size, iterated matrix multiplication}
}
  • Refine by Author
  • 10 Ikenmeyer, Christian
  • 3 Dutta, Pranjal
  • 3 Gesmundo, Fulvio
  • 3 Lysikov, Vladimir
  • 2 Bläser, Markus
  • Show More...

  • Refine by Classification
  • 9 Theory of computation → Algebraic complexity theory
  • 1 Computing methodologies → Algebraic algorithms
  • 1 Hardware → Combinational circuits
  • 1 Mathematics of computing → Mathematical software
  • 1 Theory of computation → Circuit complexity
  • Show More...

  • Refine by Keyword
  • 4 Waring rank
  • 3 border complexity
  • 2 Algebraic branching programs
  • 2 Algebraic complexity theory
  • 2 geometric complexity theory
  • Show More...

  • Refine by Type
  • 12 document

  • Refine by Publication Year
  • 3 2020
  • 3 2024
  • 2 2019
  • 1 2017
  • 1 2021
  • Show More...

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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact