Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Circuit reconstruction:
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-191 | 10th November 2018
Neeraj Kayal, Chandan Saha

Reconstruction of non-degenerate homogeneous depth three circuits

A homogeneous depth three circuit $C$ computes a polynomial
$$f = T_1 + T_2 + ... + T_s ,$$ where each $T_i$ is a product of $d$ linear forms in $n$ variables over some underlying field $\mathbb{F}$. Given black-box access to $f$, can we efficiently reconstruct (i.e. proper learn) a ... more >>>

TR21-045 | 22nd March 2021
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits

We give new and efficient black-box reconstruction algorithms for some classes of depth-$3$ arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a {\it constant-rank} tensor. ... more >>>

ISSN 1433-8092 | Imprint