Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > EQUIVALENCE TESTING:
Reports tagged with equivalence testing:
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 >>>

TR18-029 | 9th February 2018
Neeraj Kayal, vineet nair, Chandan Saha

#### Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs

Revisions: 2

Let us call a matrix $X$ as a linear matrix if its entries are affine forms, i.e. degree one polynomials. What is a minimal-sized representation of a given matrix $F$ as a product of linear matrices? Finding such a minimal representation is closely related to finding an optimal way to ... more >>>

TR20-091 | 14th June 2020
Janaky Murthy, vineet nair, Chandan Saha

#### Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests

Equivalence testing for a polynomial family $\{g_m\}_{m \in \mathbb{N}}$ over a field F is the following problem: Given black-box access to an $n$-variate polynomial $f(\mathbb{x})$, where $n$ is the number of variables in $g_m$ for some $m \in \mathbb{N}$, check if there exists an $A \in \text{GL}(n,\text{F})$ such that \$f(\mathbb{x}) ... more >>>

ISSN 1433-8092 | Imprint