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-090 | 10th July 2025
Noor Athamnah, Noga Ron-Zewi, Ron Rothblum

Linear Prover IOPs in Log Star Rounds

Interactive Oracle Proofs (IOPs) form the backbone of some of the most efficient general-purpose cryptographic proof-systems. In an IOP, the prover can interact with the verifier over multiple rounds, where in each round the prover sends a long message, from which the verifier only queries a few symbols.

State-of-the-art ... more >>>


TR25-089 | 10th July 2025
Valentine Kabanets, Antonina Kolokolova

Chain Rules for Time-Bounded Kolmogorov Complexity

Time-bounded conditional Kolmogorov complexity of a string $x$ given $y$, $K^t(x\mid y)$, is the length of a shortest program that, given $y$, prints $x$ within $t$ steps. The Chain Rule for conditional $K^t$ with error $e$ is the following hypothesis: there is a constant $c\in\mathbb{N}$ such that, for any strings ... more >>>


TR25-088 | 1st July 2025
Igor Balla, Lianna Hambardzumyan, Istvan Tomon

Factorization norms and an inverse theorem for MaxCut

We prove that Boolean matrices with bounded $\gamma_2$-norm or bounded normalized trace norm must contain a linear-sized all-ones or all-zeros submatrix, verifying a conjecture of Hambardzumyan, Hatami, and Hatami. We also present further structural results about Boolean matrices of bounded $\gamma_2$-norm and discuss applications in communication complexity, operator theory, spectral ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint