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-093 | 14th July 2025
Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan

Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications

We consider random walks on "balanced multislices"
of any "grid" that respects the "symmetries" of the grid, and show that a broad class of such walks are good spectral expanders. (A grid is a set of points of the form $\mathcal{S}^n$ for finite $\mathcal{S}$, and a balanced multi-slice is the ... more >>>


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



previous PreviousNext next


ISSN 1433-8092 | Imprint