Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > EIGENVALUES AND RAPID MIXING:
Reports tagged with Eigenvalues and Rapid Mixing:
TR98-017 | 29th March 1998
Oded Goldreich, Madhu Sudan

Computational Indistinguishability: A Sample Hierarchy.


We consider the existence of pairs of probability ensembles which
may be efficiently distinguished given $k$ samples
but cannot be efficiently distinguished given $k'<k$ samples.
It is well known that in any such pair of ensembles it cannot be that
both are efficiently computable
(and that such phenomena ... 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 >>>




ISSN 1433-8092 | Imprint