IA170 Randomness and Communication

Faculty of Informatics
Autumn 2015
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
doc. RNDr. Jan Bouda, Ph.D. (lecturer)
Frédéric Dupont Dupuis, Ph.D. (seminar tutor)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: doc. RNDr. Jan Bouda, Ph.D.
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Tue 8:00–9:50 C511
  • Timetable of Seminar Groups:
IA170/01: each odd Tuesday 10:00–11:50 C416, J. Bouda
IA170/02: each even Tuesday 10:00–11:50 C416, J. Bouda
Prerequisites
Knowledge of basic discrete mathematics (e.g. as presented in the course IB000), basic knowledge of probability theory (e.g. IV111).
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Course objectives
At the end of the course student should have a sufficient knowledge and skills to independently study and solve problems in the areas of: randomness generation, randomness post processing, efficient usage of the real world randomness in information processing, efficient communication both with and without noise in the channel, efficient distributed function computation. He should acquire essential knowledge of information theory as well. Should be able to learn independently new problems requiring knowledge of information theory, randomness and communication complexity.
Syllabus
  • - Operational meaning of information and entropy. Shannon entropy, relative entropy, mutual information. Rényi entropy. Min- and Max- entropy.
  • - Shannon (asymptotic) channel capacity. Assisted channel capacity, channels with memory. Shannon’s forward and reverse channel capacity theorem. Shannon’s zero-error capacity, Lovasz‘s theta function.
  • - Perfect and weak randomness, applications. Measuring randomness. Randomness extraction, extractors, seeded extractors, independent-source extractors. Pseudorandom structures: k-wise independent random variables, expanders.
  • - Communication complexity. Communication-efficient distributed computation. Randomness and communication complexity.
Literature
    recommended literature
  • - KUSHILEVITZ, Eyal a Noam NISAN. Communication complexity. Cambridge: Cambridge University Press, c1997, xiii, 189 s. ISBN 0521560675
  • CSISZÁR, Imre and János KÖRNER. Information theory : coding theorems for discrete memoryless systems. 2nd ed. Cambridge: Cambridge University Press, 2011, xxi, 499. ISBN 9780521196819. info
  • STINSON, Douglas Robert. Cryptography : theory and practice. 3rd ed. Boca Raton: CRC Press, 2006, 593 s. ISBN 1584885084. info
  • COVER, T. M. and Joy A. THOMAS. Elements of information theory. 2nd ed. Hoboken, N.J.: Wiley-Interscience, 2006, xxiii, 748. ISBN 0471241954. info
  • MITZENMACHER, Michael and Eli UPFAL. Probability and computing : an introduction to randomized algorithms and probabilistic analysis. New York: Cambridge University Press, 2005, xvi, 352. ISBN 0521835402. info
Teaching methods
Theoretical lectures and practical examples in tutorials.
Assessment methods
Combination of a written test and an oral exam. Student successful in the written test has to pass an oral exam in order to achieve grade C or better.
Language of instruction
English
Further comments (probably available only in Czech)
Study Materials
The course is taught annually.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2015/IA170