Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Algebraic Branching Program:
TR09-026 | 17th February 2009
Vikraman Arvind, Pushkar Joglekar

Arithmetic Circuit Size, Identity Testing, and Finite Automata

Let $\F\{x_1,x_2,\cdots,x_n\}$ be the noncommutative polynomial
ring over a field $\F$, where the $x_i$'s are free noncommuting
formal variables. Given a finite automaton $\A$ with the $x_i$'s as
alphabet, we can define polynomials $\f( mod A)$ and $\f(div A)$
obtained by natural operations that we ... more >>>

TR17-021 | 11th February 2017
Neeraj Kayal, Vineet Nair, Chandan Saha, S├ębastien Tavenas

Reconstruction of full rank Algebraic Branching Programs

An algebraic branching program (ABP) A can be modelled as a product expression $X_1\cdot X_2\cdot \dots \cdot X_d$, where $X_1$ and $X_d$ are $1 \times w$ and $w \times 1$ matrices respectively, and every other $X_k$ is a $w \times w$ matrix; the entries of these matrices are linear forms ... more >>>

TR17-034 | 21st February 2017
Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam

On algebraic branching programs of small width

Revisions: 1

In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the ... more >>>

TR23-025 | 10th March 2023
Vikraman Arvind, Pushkar Joglekar

Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization

Based on a theorem of Bergman we show that multivariate noncommutative polynomial factorization is deterministic polynomial-time reducible to the factorization of bivariate noncommutative polynomials. More precisely, we show the following:

(1) In the white-box setting, given an n-variate noncommutative polynomial f in F over a field F (either a ... more >>>

ISSN 1433-8092 | Imprint