A certain level of mathematical maturity, as obtained during a
undergraduate university mathematics programme or completing an
advanced algorithms course. 

• identificere, modellere og analysere kommunikationsproblemer i
  informationsteknologiske systemer
  
  
• forbedre kommunikationskritiske dele af systemer hjælp af
  algoritmiske teknikker, fx randomisering
  
  
• ræsonere omkring optimaliteten af eksisterende løsninger
  
  
• redegøre for anvendelsen af kommunikationskompleksitet i andre
  datalogiske modeller som fx datastrukturer eller boolske kredse
  
  
• anvende grundlæggende teknikker og begreber fra den teoretiske
  datalogi, specielt kompleksitetsteori og tilfældighed
  

After the course the student will be able to

• identify, model and analyze communication problems in IT systems
  
  
• improve communication critical parts of systems using algorithmic techniques, e.g. randomization.
  
• reason about optimality of existing systems
  
  
• explain the use of communication complexity in other models within computer science, e.g. datastructures or boolean circuits.
  
  
• apply basic techniques from theoretical computer science, in particular complexity theory and randomness
  
  

Mange informationsteknologiske fænomener kan opfattes som en række af
kommunikationer: paralleldatamater, Internettet, distribuerede
systemer, osv. Ydermere er kommunikation (fremfor udregning) ofte
flaskehalsen i et beregningsproblem. For eksempel har moderne
maskinarkitekturer ekstremt hurtige processorer, som udfører
beregningsopgaver i processorens lokale hukommelse (cache) meget
hurtigere, end de nødvendige data har kunnet flyttes fra og til den
eksterne hukommelse. Konsekvensen er at studere disse problemer i en
model, hvor beregning er gratis, men kommunikation er en resurse.

Kommunikationskompleksitet er en ligefrem og underholdene matematisk
teori for sådanne beregningsprocesser, som samtidig er både elegant og
kraftig. Det er en af de få kompleksitetsteorier, som faktisk har held
med at analysere sine problemer uden at appellere til ubeviste og
vanskelige antagelser som P != NP. Derfor kan
kommunikationskompleksitet også betragtes som en stimulerende
introduktion til teoretisk datalogi.

Anvendelser for kommunikationsmodeller findes i netværk, parallelle
algoritmer, VLSI-kredse og datastrukturer. Det sidste har forelæserens
specielle opmærksomhed.

Dette er et grundlæggende kursus for
studenter og forkskere i teoretisk datalogi, tilfældighed, kredse,
netværk og informationsteori.

Emner:

• 
  Toparts-kompleksitet med og uden fast opdeling.
  
• Flerparts-kompleksitet. Nondeterminisme.
• Randomisering.
  
• Forderlingskompleksitet.
  
• Min-max-princippet.
  
• Afrandomisering.
  
• Runder.
• Assymetrisk
  kompleksitet.
• Relationer.
  
• Nedre grænser: kombinatoriske rektangler,
  matrixrang, ramseyteori, diskrepans.
  
• Anvendelser: netværk,
  vlsi-kredse, beslutningstræer, boolske kredse, statiske og dynamiske
  datastrukturer, turingmaskiner.
  

Course home page: www.cs.lth.se/~thore/cc.

Many aspects of the internal and external workings of computers can be
viewed as a series of communication processes: parallel computers, the
Internet, distributed systems, etc. Moreover, communication (rather
than computation) is often the crux of a computational problem. For
example, modern computers have extrememly fast processors that solve
computational tasks in the processor's cache very quickly, the hard
part of the problem is memory access -- reading and writing large
blocks of information. These problems are best studied in a model
where computation is for free, but communication is a ressource.

Communication complexity is a very straightforward and entertaining,
but elegant and rich mathematical theory of such communication
processes. It is one of the few complexity theories in computer
science that are successful in analysing the complexity of the
problems it studies -- without relying on widely accepted but unproven
(and probably very hard) assumptions like P != NP -- and thus
provides a stimulating introduction to theoretical computer science.

Applications of communication models include computer networks,
parallel algorithms, VLSI circuits, and data structures. The latter
application will have the lecturer's special attention.

This is an
essential course for graduate students and researchers in theoretical
computer science, randomness, circuits, networks and information
theory.


 

3 timers forelæsning om ugen (kl. 10-13), hvoraf en del er reserveret til
gennemgang af regnede øvelsesopgaver. 

Godkendt / ikke-godkendt med intern censur på baggrund af obligatoriske
afleveringsopgaver.

• Eyal Kushilevitz, Noam Nisan: Communication Complexity. Cambridge
  University Press 1997, ISBN 0521560675


• Yderligere forelæsningsnoter om asymmetrisk
  kommunikationskompleksitet og datastrukturer