I018 Communication and Communication Complexity

Faculty of Informatics
Autumn 2000
Extent and Intensity
2/0. 2 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Ivana Černá, CSc. (lecturer)
Guaranteed by
prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Ivana Černá, CSc.
Prerequisites
I005 Formal Languages and Automata I
Before enrolling this course the students should go through I005 Formal Languages and Automata I. I012 Complexity is recommended.
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
Syllabus
  • Computers can be described as a series of communication processes on many levels. Communication complexity is the mathematical theory of such communication processes. It is also often used as an abstract model of other aspects of computation. This lecture begins with simple models of communication and leads up to state-of-the-art theoretical results and aplications.
  • PART ONE: Two party communication complexity. Basic protocol models. Lower bounds (Fooling set method, Rank method, Tiling method, comparison of methods). One-way communication complexity.
  • PART TWO: Other models of communication. Nondeterministic and randomized communications. The communication complexity of relations. Multiparty communications. Variable partition models.
  • PART THREE: Applications. Networks, communication and VLSI. Decision trees and data structures. Boolean circuit depth. Time and space. Further topics.
Literature
  • Hromkovič Juraj. Communication complexity and parallel computing. Springer, 1997. ISBN 3-540-57459.
  • KUSHILEVITZ, Eyal and Noam NISAN. Communication complexity. Cambridge: Cambridge University Press, 1997, xiii, 189. ISBN 0521560675. info
Assessment methods (in Czech)
Během semestru studenti samostatně řeší zadané problémy. Řešení jsou základem pro určení závěrečného hodnocení.
Language of instruction
Czech
Further Comments
The course is taught once in two years.
The course is taught: every week.
Teacher's information
http://www.fi.muni.cz/usr/cerna/i018.html
The course is also listed under the following terms Spring 1996, Spring 1997, Spring 1999.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2000/I018