A note on VNP-completeness and border complexity
From MaRDI portal
Publication:2122788
DOI10.1016/j.ipl.2021.106243OpenAlexW4206402997MaRDI QIDQ2122788
Christian Ikenmeyer, Abhiroop Sanyal
Publication date: 7 April 2022
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2102.07173
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the power of algebraic branching programs of width two
- Comparing reductions to NP-complete sets
- Matrix multiplication via arithmetic progressions
- On the order of approximation in approximative triadic decompositions of tensors
- Relations between exact and approximate bilinear algorithms. Applications
- Some complete and intermediate polynomials in algebraic complexity theory
- On the relative power of reduction notions in arithmetic circuit complexity
- The complexity of factors of multivariate polynomials
- Geometric Complexity Theory I: An Approach to thePvs.NPand Related Problems
- New lower bounds for the border rank of matrix multiplication
- An Overview of Mathematical Issues Arising in the Geometric Complexity Theory Approach to $\mathbf{VP}\neq\mathbf{VNP}$
- Approximate Solutions for the Bilinear Form Computational Problem
- Partial and Total Matrix Multiplication
- Some Properties of Disjoint Sums of Tensors Related to Matrix Multiplication
- On the Asymptotic Complexity of Matrix Multiplication
- Computing Algebraic Formulas Using a Constant Number of Registers
- Boundaries of VP and VNP
- A $2{\mathbf{n}}^2-{\text{log}}_2({\mathbf{n}})-1$ lower bound for the border rank of matrix multiplication
- On Algebraic Branching Programs of Small Width
- Discovering the roots: uniform closure results for algebraic classes under factoring
- A PSPACE construction of a hitting set for the closure of small algebraic circuits
- The complexity theory companion
