scientific article; zbMATH DE number 7561749

DOI10.4230/LIPICS.CCC.2020.21MaRDI QIDQ5092471zbMATH OpenFDO

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

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/2003.04834

zbMATH Keywords

algebraic branching programsborder complexityflowsgeometric complexity theorylower boundstangent spacesVNPVQP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• A lower bound for the determinantal complexity of a hypersurface
• A quadratic lower bound for homogeneous algebraic branching programs
• An overview of mathematical issues arising in the geometric complexity theory approach to \(\mathbf{VP}\neq\mathbf{VNP}\)
• Boundaries of VP and VNP
• Characterizing Valiant's algebraic complexity classes
• Completeness and reduction in algebraic complexity theory
• Computing Algebraic Formulas Using a Constant Number of Registers
• Correction to: ``The complexity of factors of multivariate polynomials
• Geometric aspects of iterated matrix multiplication
• Geometric complexity theory and matrix powering
• Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties
• Geometric complexity theory. I: An approach to the P vs. NP and related problems
• Geometric complexity theory: an introduction for geometers
• Graph theory
• scientific article; zbMATH DE number 3555467 (Why is no real title available?)
• scientific article; zbMATH DE number 7650312 (Why is no real title available?)
• Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs
• Lower bounds for polynomials with algebraic coefficients
• On Algebraic Branching Programs of Small Width
• On the power of algebraic branching programs of width two
• Polynomials with Rational Coefficients Which are Hard to Compute
• Reconstruction of full rank algebraic branching programs
• Relations between exact and approximate bilinear algorithms. Applications
• Separating monotone VP and VNP
• Tensor-rank and lower bounds for arithmetic formulas
• The boundary of the orbit of the 3-by-3 determinant polynomial
• The complexity of factors of multivariate polynomials

Cited in

(4)

• Algorithmic aspects of branched coverings I/V. Van Kampen's theorem for bisets
• On Algebraic Branching Programs of Small Width
• On the closures of monotone algebraic classes and variants of the determinant
• On the closures of monotone algebraic classes and variants of the determinant

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092471)