Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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