Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RECONSTRUCTION:
Reports tagged with reconstruction:
TR10-067 | 14th April 2010
Sourav Chakraborty, Eldar Fischer, Arie Matsliah

Query Complexity Lower Bounds for Reconstruction of Codes

We investigate the problem of {\em local reconstruction}, as defined by Saks and Seshadhri (2008), in the context of error correcting codes.

The first problem we address is that of {\em message reconstruction}, where given oracle access to a corrupted encoding $w \in \zo^n$ of some message $x \in \zo^k$ ... more >>>


TR11-061 | 18th April 2011
Neeraj Kayal

Affine projections of polynomials

Revisions: 1

An $m$-variate polynomial $f$ is said to be an affine projection of some $n$-variate polynomial $g$ if there exists an $n \times m$ matrix $A$ and an $n$-dimensional vector $b$ such that $f(x) = g(A x + b)$. In other words, if $f$ can be obtained by replacing each variable ... more >>>


TR11-153 | 13th November 2011
Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam

Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2

We present a randomized algorithm for reconstructing multilinear depth-4 arithmetic circuits with fan-in 2 at the top + gate. The algorithm is given blackbox access to a multilinear polynomial f in F[x_1,..,x_n] computable by a multilinear Sum-Product-Sum-Product(SPSP) circuit of size s and outputs an equivalent multilinear SPSP circuit, runs ... more >>>


TR12-033 | 5th April 2012
Ankit Gupta, Neeraj Kayal, Youming Qiao

Random Arithmetic Formulas can be Reconstructed Efficiently

Informally stated, we present here a randomized algorithm that given blackbox access to the polynomial $f$ computed by an unknown/hidden arithmetic formula $\phi$ reconstructs, on the average, an equivalent or smaller formula $\hat{\phi}$ in time polynomial in the size of its output $\hat{\phi}$.

Specifically, we consider arithmetic formulas wherein the ... more >>>


TR15-150 | 13th September 2015
Gaurav Sinha

Reconstruction of $\Sigma\Pi\Sigma(2)$ Circuits over Reals

Revisions: 3

Reconstruction of arithmertic circuits has been heavily studied in the past few years and has connections to proving lower bounds and deterministic identity testing. In this paper we present a polynomial time randomized algorithm for reconstructing $\Sigma\Pi\Sigma(2)$ circuits over $\R$, i.e. depth$-3$ circuits with fan-in $2$ at the top addition ... more >>>


TR19-104 | 6th August 2019
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Reconstruction of Depth-$4$ Multilinear Circuits

We present a deterministic algorithm for reconstructing multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuits, i.e. multilinear depth-$4$ circuits with fan-in $k$ at the top $+$ gate. For any fixed $k$, given black-box access to a polynomial $f \in \mathbb{F}[x_{1},x_{2},\ldots ,x_{n}]$ computable by a multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuit of size $s$, the algorithm runs in time ... more >>>


TR20-045 | 15th April 2020
Ankit Garg, Neeraj Kayal, Chandan Saha

Learning sums of powers of low-degree polynomials in the non-degenerate case

Revisions: 1

We develop algorithms for writing a polynomial as sums of powers of low degree polynomials. Consider an $n$-variate degree-$d$ polynomial $f$ which can be written as
$$f = c_1Q_1^{m} + \ldots + c_s Q_s^{m},$$
where each $c_i\in \mathbb{F}^{\times}$, $Q_i$ is a homogeneous polynomial of degree $t$, and $t m = ... more >>>


TR20-125 | 17th August 2020
Gaurav Sinha

Efficient reconstruction of depth three circuits with top fan-in two

Revisions: 2

In this paper we develop efficient randomized algorithms to solve the black-box reconstruction problem for polynomials(over finite fields) computable by depth three arithmetic circuits with alternating addition/multiplication gates, such that top(output) gate is an addition gate with in-degree $2$. Such circuits naturally compute polynomials of the form $G\times(T_1 + T_2)$, ... more >>>


TR21-155 | 13th November 2021
Vishwas Bhargava, Ankit Garg, Neeraj Kayal, Chandan Saha

Learning generalized depth-three arithmetic circuits in the non-degenerate case

Revisions: 1

Consider a homogeneous degree $d$ polynomial $f = T_1 + \cdots + T_s$, $T_i = g_i(\ell_{i,1}, \ldots, \ell_{i, m})$ where $g_i$'s are homogeneous $m$-variate degree $d$ polynomials and $\ell_{i,j}$'s are linear polynomials in $n$ variables. We design a (randomized) learning algorithm that given black-box access to $f$, computes black-boxes for ... more >>>


TR22-125 | 9th September 2022
Shir Peleg, Amir Shpilka, Ben Lee Volk

Tensor Reconstruction Beyond Constant Rank

We give reconstruction algorithms for subclasses of depth-$3$ arithmetic circuits. In particular, we obtain the first efficient algorithm for finding tensor rank, and an optimal tensor decomposition as a sum of rank-one tensors, when given black-box access to a tensor of super-constant rank. Specifically, we obtain the following results:

1. ... more >>>


TR23-032 | 24th March 2023
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Linear Independence, Alternants and Applications


We develop a new technique for analyzing linear independence of multivariate polynomials. One of our main technical contributions is a \emph{Small Witness for Linear Independence} (SWLI) lemma which states the following.
If the polynomials $f_1,f_2, \ldots, f_k \in \F[X]$ over $X=\{x_1, \ldots, x_n\}$ are $\F$-linearly independent then there exists ... more >>>


TR24-123 | 22nd July 2024
Vishwas Bhargava, Devansh Shringi

Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition

We present a deterministic $2^{k^{\mathcal{O}(1)}} \text{poly}(n,d)$ time algorithm for decomposing $d$-dimensional, width-$n$ tensors of rank at most $k$ over $\mathbb{R}$ and $\mathbb{C}$. This improves upon the previous randomized algorithm of Peleg, Shpilka, and Volk (ITCS '24) that takes $2^{k^{k^{\mathcal{O}(k)}}} \text{poly}(n,d)$ time and the deterministic $n^{k^k}$ time algorithms of Bhargava, Saraf, ... more >>>




ISSN 1433-8092 | Imprint