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

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 >>> TR24-073 | 11th April 2024 Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay #### Trading Determinism for Noncommutativity in Edmonds' Problem Let$X=X_1\sqcup X_2\sqcup\ldots\sqcup X_k$be a partitioned set of variables such that the variables in each part$X_i$are noncommuting but for any$i\neq j$, the variables$x \in X_i$commute with the variables$x' \in X_j$. Given as input a square matrix$T$whose entries are linear forms over ... more >>> TR24-104 | 12th June 2024 Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha #### NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials An$s$-sparse polynomial has at most$s$monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial$f$is equivalent to (i.e., in the orbit of) some$s$-sparse polynomial. In other words, given$f \in \mathbb{F}[\mathbf{x}]$and$s \in \mathbb{N}\$, ETsparse ... more >>>

ISSN 1433-8092 | Imprint