139 citations · 168 across the 18 of their papers we have counts for
18 papers
Explicit non-free tensors
Maxim van den Berg, Matthias Christandl, Vladimir Lysikov +3
Free tensors are tensors which, after a change of bases, have free support: any two distinct elements of its support differ in at least two coordinates. They play a distinguished r…
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…
The resource theory of tensor networks
Matthias Christandl, Vladimir Lysikov, Vincent Steffan +2
Tensor networks provide succinct representations of quantum many-body states and are an important computational tool for strongly correlated quantum systems. Their expressive and c…
Partial Degeneration of Tensors
Matthias Christandl, Fulvio Gesmundo, Vladimir Lysikov +1
Tensors are often studied by introducing preorders such as restriction and degeneration: the former describes transformations of the tensors by local linear maps on its tensor fact…
Quantum max-flow in the bridge graph
Fulvio Gesmundo, Vladimir Lysikov, Vincent Steffan
The quantum max-flow is a linear algebraic version of the classical max-flow of a graph, used in quantum many-body physics to quantify the maximal possible entanglement between two…
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…
Persistent Tensors and Multiqudit Entanglement Transformation
Masoud Gharahi, Vladimir Lysikov
We construct a lower bound of the tensor rank for a new class of tensors, which we call persistent tensors. We present three specific families of persistent tensors, of which the l…
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…
Strassen's 2x2 matrix multiplication algorithm: A conceptual perspective
Christian Ikenmeyer, Vladimir Lysikov
The main purpose of this paper is pedagogical. Despite its importance, all proofs of the correctness of Strassen's famous 1969 algorithm to multiply two 2x2 matrices with only seve…
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…