- 2021 Autumn/Monsoon (Aug - Dec)
The last two decades have made tremendous progress in one shot information theory where an information resource like a communication channel can be used only once. This is in sharp contrast to the traditional setting of using an information resource many times independently, otherwise known as the asymptotic iid setting. Motivations for the one shot setting arise from several areas like cryptography, computational complexity etc., besides a deeper study of information theory itself. When properly analysed, one shot information theory leads to advances even in traditional settings like second order rates for finite block lengths, sharper converses etc. This course will survey a few topics in one shot classical as well as quantum information theory. No prior background in quantum computation or information will be assumed. It will be highly advantageous to have completed a standard course in classical information theory and a basic course in linear algebra. Good mathematical maturity is the only real prerequisite though.
1. Review of Shannon's noiseless and noisy coding theorems in classical asymptotic iid setting; Shannon entropy; relative entropy; data processing.
2. The same theorems in classical one shot setting; smooth hypothesis testing and smooth max relative entropies.
3. Motivations for one shot setting; extractors in cryptography; direct sum problem in communication complexity.
4. Packing and covering paradigms in information theory; multiple access channel, point to point wiretap channel, multiple access wiretap channel, roles of the one shot smooth relative entropies, unions and intersections.
5. Going from one shot to asymptotic iid setting; asymptotic equipartition and second order analysis.
6. Introduction to quantum information by demonstrating parallels and differences with classical information; density matrices, quantum operations.
7. The quantum analogues of smooth relative entropies and data processing inequalities.
8. Noiseless and noisy coding theorems in one shot quantum setting using the quantum smooth relative entropies.
9. Quantum asymptotic equipartition theorem.
10. Typical subspaces in quantum asymptotic iid setting, union and intersection bottlenecks and the simultaneous smoothing conjecture.