Must One Learn the Channel to Communicate at Capacity?
summary
Asks how large input/output alphabets can grow with blocklength n before universal codes that don’t know the channel stop achieving capacity. Proves a training-then-communicate scheme succeeds when the product of alphabet sizes grows sublinearly in n, and gives three impossibility results using a minimax mixture construction and entropy decompositions: a two-input versus n^beta outputs example, a square matrix with ~sqrt(n) learnable rows, and the rule alpha+beta>1 impossible. Shows knowing the channel drastically helps — either alphabet can grow as exp(sqrt(n)) and still work.
AI-written summary · about
chapters (7)
- 0:00Intro
- 0:51The Capacity Theorem
- 2:54Channel Coding as Minimax
- 11:59Learning the Channel
- 14:58Impossibility Result #3
- 22:49Maximin Formulation
- 24:29Must One Learn the Channel?
related talks
40mTutorial on Capacity in Coding for Interactive Communication (Part 2 of 2)
34mPolar Codes over q-ary Alphabets and Polynomially Fast Convergence to Shannon Capacity
01h 14mPolar Codes III
32mDeterministic Rateless Codes for BSC
33mDeletion Codes in the High-noise and High-rate Regimes
01h 01mTrue Complexity of Multilinear Systems
32mReed-Muller and Other Subcodes of the Sierpinski Matrix
32mA Finite Alternation Result for Reversible Boolean Circuits