Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-FeedNext next

TR25-160 | 24th October 2025
Yaroslav Alekseev, Nikita Gaevoy

Intersection Theorems: A Potential Approach to Proof Complexity Lower Bounds

Recently, Göös et al. (2024) showed that Res ? uSA = RevRes in the following sense: if a formula $\varphi$ has refutations of size at most $s$ and width/degree at most $w$ in both Res and uSA, then there is a refutation for $\varphi$ of size at most $poly(s·2^w)$ in ... more >>>


TR25-159 | 21st October 2025
Bonnie Berger, Rohan Goyal, Matthew M. Hong, Yael Tauman Kalai

Efficiently Batching Unambiguous Interactive Proofs

We show that if a language $\mathcal{L}$ admits a public-coin unambiguous interactive proof (UIP) with round complexity $\ell$, where $a$ bits are communicated per round, then the \emph{batch language} $\mathcal{L}^{\otimes k}$, i.e. the set of $k$-tuples of statements all belonging to $\mathcal{L}$, has an unambiguous interactive proof with round complexity ... more >>>


TR25-158 | 7th October 2025
Fernando Jeronimo, Nikhil Shagrithaya

Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes

We present a general framework for derandomizing random linear codes with respect to a broad class of permutation-invariant properties, known as local properties, which encompass several standard notions such as distance, list-decoding, list-recovery, and perfect hashing. Our approach extends the classical Alon-Edmonds-Luby (AEL) construction through a modified formalism of local ... more >>>



Next next


ISSN 1433-8092 | Imprint