139 citations · 168 across the 18 of their papers we have counts for
12 papers · 1 filter
The moment polytope of matrix multiplication is not maximal
Maxim van den Berg, Matthias Christandl, Vladimir Lysikov +3
Moment polytopes of tensors, the study of which is deeply rooted in invariant theory, representation theory and symplectic geometry, have found relevance in numerous places, from q…
Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness
Vladimir Lysikov, Michael Walter
Many natural computational problems in computer science, mathematics, physics, and other sciences amount to deciding if two objects are equivalent. Often this equivalence is define…
Fixed-parameter debordering of Waring rank
Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer +2
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…
Homogeneous Algebraic Complexity Theory and Algebraic Formulas
Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer +2
We study algebraic complexity classes and their complete polynomials under \emph{homogeneous linear} projections, not just under the usual affine linear projections that were origi…
Geometric complexity theory for product-plus-power
Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer +2
According to Kumar's recent surprising result (ToCT'20), a small border Waring rank implies that the polynomial can be approximated as a sum of a constant and a small product of li…
Degree-restricted strength decompositions and algebraic branching programs
Fulvio Gesmundo, Purnata Ghosal, Christian Ikenmeyer +1
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 g…
Weighted slice rank and a minimax correspondence to Strassen's spectra
Matthias Christandl, Vladimir Lysikov, Jeroen Zuiddam
Structural and computational understanding of tensors is the driving force behind faster matrix multiplication algorithms, the unraveling of quantum entanglement, and the breakthro…
Barriers for rectangular matrix multiplication
Matthias Christandl, François Le Gall, Vladimir Lysikov +1
We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular…
Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
Markus Bläser, Christian Ikenmeyer, Vladimir Lysikov +2
We study the variety membership testing problem in the case when the variety is given as an orbit closure and the ambient space is the set of all 3-tensors. The first variety that…
On the complexity of hazard-free circuits
Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen +3
The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows th…
On degeneration of tensors and algebras
Markus Bläser, Vladimir Lysikov
An important building block in all current asymptotically fast algorithms for matrix multiplication are tensors with low border rank, that is, tensors whose border rank is equal or…
On bilinear algorithms for multiplication in quaternion algebras
Vladimir Lysikov
We show that the bilinear complexity of multiplication in a non-split quaternion algebra over a field of characteristic distinct from 2 is 8. This question is motivated by the prob…