Internal Compression of Protocols to Entropy
summary
Claims an interactive compression method that matches external entropy up to a constant (empirically about 1.82), and an internal compression that replaces the previous O(H_int · log CC) bound with roughly O(H_int · log log CC) at the cost of allowing small error. Construction is a deterministic protocol using the meaningful vertex idea plus fast search subroutines (Feige–et al. first-difference variant and Braverman–Rao style sampling). External simulation is zero-error and tight; internal simulation is randomized and practical with the stated bounds.
AI-written summary · about
chapters (13)
- 0:00Intro
- 1:07A conversation that is easy to compress
- 2:11What does "compression" mean?
- 2:55Information complexities: external and internal information
- 4:10Information complexities: external and internal entropies
- 5:07Information versus entropy
- 8:31Internal simulation
- 9:50Lower bounds
- 10:41External compression: Upper bounds
- 13:08Internal compression: Upper bounds
- 14:09External simulation (Dietzfelbinger-Wunderlich)
- 16:54An external compression: Summary
- 17:25Internal compression - meaningful vertices
related talks
01h 04mInformation Theory in Computational Complexity I
01h 09mInformation Theory in Computational Complexity IV
01h 00mAverage-case Complexity for Polynomials, and All That
56mEntropy, Capacity, and Counting
59mInformational and computational aspects of holography
51mAllender's Conjecture and its Impacts on Meta-Complexity
53mA Commentary on the Collision of Worlds
01h 01mThe Gospel According to TCS