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-053 | 23rd April 2025
Amir Shpilka

On Approximate Symmetric Polynomials and Tightness of Homogenization Results

Motivated by questions concerning the multilinear and homogeneous complexity of the elementary symmetric polynomials, we prove the following results:

We first show that by making small modifications to the nonzero coefficients of the degree-$K$, $N$-variate elementary symmetric polynomial $\sigma_{N,K}$, one obtains a polynomial that can be computed by a monotone ... more >>>


TR25-052 | 21st April 2025
Zeyu Guo, Siki Wang

Deterministic Depth-4 PIT and Normalization

Revisions: 2

In this paper, we initiate the study of deterministic PIT for $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ circuits over fields of any characteristic, where $k$ and $\delta$ are bounded. Our main result is a deterministic polynomial-time black-box PIT algorithm for $\Sigma^{[3]}\Pi\Sigma\Pi^{[\delta]}$ circuits, under the additional condition that one of the summands at the top $\Sigma$ ... more >>>


TR25-051 | 21st April 2025
Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta

Rank Bounds and PIT for $\Sigma^3 \Pi \Sigma \Pi^d$ circuits via a non-linear Edelstein-Kelly theorem

Revisions: 1

We prove a non-linear Edelstein-Kelly theorem for polynomials of constant degree, fully settling a stronger form of Conjecture 30 in Gupta (2014), and generalizing the main result of Peleg and Shpilka (STOC 2021) from quadratic polynomials to polynomials of any constant degree.

As a consequence of our result, we obtain ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint