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-094 | 14th July 2025
Shuichi Hirahara, Rahul Ilango, Bruno Loff

Communication Complexity is NP-hard

In the paper where he first defined Communication Complexity, Yao asks: \emph{Is computing $CC(f)$ (the 2-way communication complexity of a given function $f$) NP-complete?} The problem of deciding whether $CC(f) \le k$, when given the communication matrix for $f$ and a number $k$, is easily seen to be in NP. ... more >>>


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



previous PreviousNext next


ISSN 1433-8092 | Imprint