Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR25-008 | 9th February 2025
Shubhangi Saraf, Devansh Shringi

Reconstruction of Depth $3$ Arithmetic Circuits with Top Fan-in $3$

In this paper, we give the first subexponential (and in fact quasi-polynomial time) reconstruction algorithm for depth 3 circuits of top fan-in 3 ($\Sigma\Pi\Sigma(3)$ circuits) over the fields $\mathbb{R}$ and $\mathbb C$. Concretely, we show that given blackbox access to an $n$-variate polynomial $f$ computed by a $\Sigma\Pi\Sigma(3)$ circuit of ... more >>>


TR25-007 | 5th February 2025
Amir Shpilka

Improved Debordering of Waring Rank

We prove that if a degree-$d$ homogeneous polynomial $f$ has border Waring rank $\underline{\mathrm{WR}}({f}) = r$, then its Waring rank is bounded by
\[
{\mathrm{WR}}({f}) \leq d \cdot r^{O(\sqrt{r})}.
\]
This result significantly improves upon the recent bound ${\mathrm{WR}}({f}) \leq d \cdot 4^r$ established in [Dutta, Gesmundo, Ikenmeyer, Jindal, ... more >>>


TR25-006 | 4th February 2025
Subhash Khot, Kunal Mittal

Biased Linearity Testing in the 1% Regime

We study linearity testing over the $p$-biased hypercube $(\{0,1\}^n, \mu_p^{\otimes n})$ in the 1% regime. For a distribution $\nu$ supported over $\{x\in \{0,1\}^k:\sum_{i=1}^k x_i=0 \text{ (mod 2)} \}$, with marginal distribution $\mu_p$ in each coordinate, the corresponding $k$-query linearity test $\text{Lin}(\nu)$ proceeds as follows: Given query access to a function ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint