On the power of border width-2 ABPs over fields of characteristic 2

DOI10.4230/LIPICS.STACS.2024.31MaRDI QIDQ6902693zbMATH OpenFDO

Authors Pranjal Dutta, Christian Ikenmeyer, Balagopal Komarath, Harshil Mittal, Saraswati Girish Nanoti, Dhara Thakkar

Publication date 10 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2024.31

zbMATH Keywords

algebraic branching programsborder complexitycharacteristic 2

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A note on VNP-completeness and border complexity
• A PSPACE construction of a hitting set for the closure of small algebraic circuits
• Algebraic complexity classes
• Computing Algebraic Formulas Using a Constant Number of Registers
• Factorization of polynomials given by arithmetic branching programs
• 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. V: Efficient algorithms for Noether normalization
• scientific article; zbMATH DE number 3461412 (Why is no real title available?)
• scientific article; zbMATH DE number 1332669 (Why is no real title available?)
• scientific article; zbMATH DE number 2151804 (Why is no real title available?)
• On Algebraic Branching Programs of Small Width
• On computing the determinant in small parallel time using a small number of processors
• On the power of algebraic branching programs of width two
• On the power of border of depth-3 arithmetic circuits
• The complexity of factors of multivariate polynomials

Cited in

(1)

• Geometric complexity theory for product-plus-power

This page was built for publication: On the power of border width-2 ABPs over fields of characteristic 2

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