📖
Information Theory and its applications in theory of computation
Venkatesan Guruswami and Mahdi Cheraghchi

Information Theory and its applications in theory of computation

Information Theory Verification Pending

Overview & Synopsis

This note covers the following topics, Entropy, Krafts inequality, Source coding theorem, conditional entropy, mutual information, KLdivergence and connections, KLdivergence and Chernoff bounds, Data processing and Fanos inequalities, Asymptotic Equipartition Property, Universal source coding, LempelZiv algorithm and proof of its optimality, Source coding via typical sets and universality, joint typicality and joint AEP, discrete channels and channel capacity, Proof of Noisy channel coding theorem, Constructing capacityachieving codes via concatenation, Polarization, Arikans recursive construction of a polarizing invertible transformation, Polar codes construction, Bregmans theorem, Shearers Lemma and applications, Source coding and Graph entropy, Monotone formula lower bounds via graph entropy, Optimal set Disjointness lower bound and applications, Compression of arbitrary communication protocols, Parallel repetition of 2prover 1round games.

Indexed from repository: FreeBookCentre (freebookcentre.net)

Document Information

Document Title Information Theory and its applications in theory of computation
Author / Organization Venkatesan Guruswami and Mahdi Cheraghchi
Categories Information Theory
Resource Verification Listed PDF (Verification Pending)
Original Host Website FreeBookCentre (freebookcentre.net)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-309213
Original Source Link Visit Source Page on freebookcentre.net »