The Computational Complexity of Estimating Convergence Time

on YouTube ↗43m

" summary

Constructs Markov chains whose states are Turing‑machine configurations (edges given by a circuit) and tunes an edge weight W so that yes‑instances mix in poly time while no‑instances need time Θ(W), proving the general testing problem PSPACE-hard. With a known tmax the reduction uses the Boolean hypercube with self‑loop weights n versus n^d to separate cases and yields coNP-hardness. With a fixed start state a product chain encoding two circuits’ output distributions gives SZK-hardness, so no efficient diagnostic exists for these formulations.

AI-written summary · about

" chapters (17)

1. 0:00Introduction
2. 0:28Motivation
3. 2:29Visual Diagnostics
4. 5:18Statistical Diagnostics
5. 7:07Markov Chain
6. 9:25Three Versions
7. 11:57Results
8. 13:33Computation Graph
9. 14:42Special Nodes
10. 17:16Upper Bounds
11. 19:09Lower Bounds
12. 22:10Unsatisfiable
13. 24:59Hardness
14. 28:17Zero Knowledge
15. 29:52Statistical Zero Knowledge
16. 33:30Constructing a Markov Chain
17. 37:41Conclusion