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-092 | 12th July 2025
Shuichi Hirahara, Mikito Nanashima

Complexity-Theoretic Inductive Inference

Inductive inference, introduced by Solomonoff (Information and Control, 1964), is a foundational concept in knowledge acquisition, formulated as the task of extrapolating a sequence of symbols. In his seminal work, Solomonoff established a fundamental theorem for recursion-theoretic universal inductive inference, applicable to sequences generated by all Turing machines, based on ... more >>>


TR25-091 | 7th July 2025
Tamer Mour, Alon Rosen, Ron Rothblum

Tree PCPs

Probabilistically checkable proofs (PCPs) allow encoding a computation so that it can be quickly verified by only reading a few symbols. Inspired by tree codes (Schulman, STOC'93), we propose tree PCPs; these are PCPs that evolve as the computation progresses so that a proof for time $t$ is obtained by ... more >>>


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 >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint