Vladimir Lysikov

Dr. Vladimir Lysikov Postdoctoral Researcher

E-Mail: vladimir.lysikov@rub.de Office: MC 1.86

Research interests

I am interested in algebraic and geometric methods in theoretical computer science. My work is mostly focused on applications of representation theory and algebraic geometry to the study of tensors and relations between them. Tensors provide a unified language for the description of various objects. For example, reductions between multilinear problems in algebraic complexity, SLOCC entanglement transformations between multipartite states in quantum information theory, and some relations between multipartite hypergraphs in combinatorics can be described using the same mathematical constructions involving tensors.

Publications

Papers

• Barriers for rectangular matrix multiplication
  M. Christandl, F. Le Gall, V. Lysikov, J. Zuiddam
  computational complexity 34:4 (2025)

• The resource theory of tensor networks
  M. Christandl, V. Lysikov, V. Steffan, A. H. Werner, F. Witteveen
  Quantum 8, 1560 (2024)
  Presented at QIP 2024

• Quantum max-flow in the bridge graph
  F. Gesmundo, V. Lysikov, V. Steffan
  Transformation Groups, advance online publication (2024)
  Presented at QIP 2023

• Fixed-parameter debordering of Waring rank
  P. Dutta, F. Gesmundo, C. Ikenmeyer, G. Jindal, V. Lysikov
  STACS 2024, 30:1–30:15

• Partial Degeneration of Tensors
  M. Christandl, F. Gesmundo, V. Lysikov, V. Steffan
  SIAM Journal on Matrix Analysis and Applications 45(1), 771–800 (2024)

• Persistent Tensors and Multiqudit Entanglement Transformation
  M. Gharahi, V. Lysikov
  Quantum 8, 1238 (2024)

• Homogeneous Algebraic Complexity Theory and Algebraic Formulas
  P. Dutta, F. Gesmundo, C. Ikenmeyer, G. Jindal, V. Lysikov
  ITCS 2024, 43:1–43:23

• Weighted slice rank and a minimax correspondence to Strassen’s spectra
  M. Christandl, V. Lysikov, J. Zuiddam
  Journal de Mathématiques Pures et Appliquées 172, 299–329 (2023)

• Degree-Restricted Strength Decompositions and Algebraic Branching Programs
  F. Gesmundo, P. Ghosal, C. Ikenmeyer, V. Lysikov
  FSTTCS 2022, 20:1–20:15

• On the Orbit Closure Containment Problem and Slice Rank of Tensors
  M. Bläser, C. Ikenmeyer, V. Lysikov, A. Pandey, F.-O. Schreyer
  SODA 2021, 2565–2584

• Slice Rank of Block Tensors and Irreversibility of Structure Tensors of Algebras
  M. Bläser, V. Lysikov
  MFCS 2020, 17:1–17:15

• Strassen’s 2×2 matrix multiplication algorithm: a conceptual perspective
  C. Ikenmeyer, V. Lysikov
  Annali dell’Università di Ferrara. Sezione VII: Scienze mathematiche 65(2), 241–248 (2019)

• On the complexity of hazard-free circuits
  C. Ikenmeyer, B. Komarath, C. Lenzen, V. Lysikov, A. Mokhov, K. Sreenivasaiah
  J. ACM 66(4) 25 (2019)
  Conference version: STOC 2018, 878–889

• On Symmetries of Tensor Decompositions for the Commutator of 2×2 Matrices
  V. Lysikov, B. V. Chokaev
  Computational Mathematics and Modeling 30(1), 48–54 (2019)

• Generalized matrix completion and algebraic natural proofs
  M. Bläser, C. Ikenmeyer, G. Jindal, V. Lysikov
  STOC 2018, 1193–1206

• On Degeneration of Tensors and Algebras
  M. Bläser, V. Lysikov
  MFCS 2016, 19:1–19:11

• On bilinear algorithms over fields of different characteristics
  V. Lysikov
  Moscow University Computational Mathematics and Cybernetics 37(4), 189–194 (2013)

• On the algebras of almost minimal rank
  V. Lysikov
  Discrete Mathematics and Applications 22(5–6), 493–510 (2012)

Preprints

• Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness
  V. Lysikov, M. Walter
  arXiv preprint 2411.04639

• Algebraic metacomplexity and representation theory
  M. van den Berg, P. Dutta, F. Gesmundo, C. Ikenmeyer, V. Lysikov
  arXiv preprint 2411.03444

• De-bordering and Geometric Complexity Theory for Waring rank and related models
  P. Dutta, F. Gesmundo, C. Ikenmeyer, G. Jindal, V. Lysikov
  arXiv preprint 2211.07055v2
  Parts published in Homogeneous Algebraic Complexity Theory and Algebraic Formulas and Fixed-parameter debordering of Waring rank

• Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
  M. Bläser, C. Ikenmeyer, V. Lysikov, A. Pandey, F.-O. Schreyer
  arXiv preprint 1911.02534, parts published in On the Orbit Closure Containment Problem and Slice Rank of Tensors

• On bilinear algorithms for multiplication in quaternion algebras
  V. Lysikov
  arXiv preprint 1206.5501, translation of a Russian abstract

Theses

• Некоторые вопросы теории сложности билинейных отображений
  [Some problems in the complexity theory of bilinear maps]
  В. В. Лысиков [V. Lysikov]
  Диссертация к.ф.-м.н., МГУ, 2014 [Doctoral thesis, Moscow State University, 2014]
  In Russian

• Порождение двоичных последовательностей с помощью регистров сдвига малой степени
  [Generation of binary sequences with feedback shift registers of low degree]
  В. В. Лысиков [V. Lysikov]
  Дипломная работа, МГУ, 2010 [Diploma thesis, Moscow State University, 2010]
  In Russian

Abstracts (not published elsewhere)

• О билинейных отображениях малого ранга [On bilinear maps of low rank]
  В. В. Лысиков [V. Lysikov]
  Проблемы теоретической кибернетики: Материалы XVII международной конференции, ISBN 978-5-9222-0861-1, 179–182 (2014)
  In Russian

• О билинейных алгоритмах умножения обобщенных кватернионов
  [On bilinear algorithms for multiplication in quaternion algebras]
  В. В. Лысиков [V. Lysikov]
  Материалы XI международного семинара «Дискретная математика и ее приложения», 141–143 (2012)
  In Russian, translation available at arXiv:1206.5501

• О множестве всех оптимальных алгоритмов для одного класса билинейных отображений
  [On the set of optimal algorithms for a class of bilinear maps]
  В. В. Лысиков [V. Lysikov]
  Материалы VIII молодежной научной школы по дискретной математике и ее приложениям, Т. 2, 4–8 (2011)
  In Russian

← Back