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-130 | 2nd September 2025
Srinivasan Arunachalam, Davi Castro-Silva, Arkopal Dutt, Tom Gur

Algorithmic Polynomial Freiman-Ruzsa Theorems

We prove algorithmic versions of the polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao (Annals of Mathematics, 2025) in additive combinatorics. In particular, we give classical and quantum polynomial-time algorithms that, for $A \subseteq \mathbb{F}_2^n$ with doubling constant $K$, learn an explicit description of a subspace $V \subseteq \mathbb{F}_2^n$ ... more >>>


TR25-129 | 7th September 2025
Irit Dinur, Oded Goldreich

Expansion without Connectivity: A Property Testing Perspective

We consider the query complexity of testing whether a bounded-degree graph is expanding, regardless of whether or not it is connected.

Whereas prior work studied testing the property of being an expander (equiv., testing the set of expander graphs), here we study testing the set of graphs that consist of ... more >>>


TR25-128 | 5th September 2025
Ian Orzel

Computing the Elementary Symmetric Polynomials in Positive Characteristics

Revisions: 1

We first extend the results of CKSV22 by showing that the degree $d$ elementary symmetric polynomials in $n$ variables have formula lower bounds of $\Omega(d(n-d))$ over fields of positive characteristic.
Then, we show that the results of the universality of the symmetric model from Shp02 and the results about border ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint