Hoppa till huvudinnehållet
Till KTH:s startsida Till KTH:s startsida

FDD3502 Kommunikationskomplexitet 6,0 hp

Administrera Om kursen

Området för kommunikationskomplexitetsstudier mäter kommunikation som en beräkningsresurs --- en matematisk abstraktion som överensstämmer med alla problem med kommunikationsflaskhalsen. Den grundläggande modellen för kommunikationskomplexitet handlar om två parter, nämligen Alice och Bob. Deras uppgift är att beräkna en funktion på inmatning som fördelas mellan dem. För att göra så kommunicerar de mellan varandra på en uppsättning regler som de enas om tidigare och vad vi mäter är antalet bitar som de behöver kommunicera för att beräkna funktionen. Detta problem och många av dess varianter uppträder ofta i praktiken i många dimensioner och i olika abstraktionsnivåer --- i nätverksprotokoll där målet är att minimera kommunikationen (och därmed fel i kommunikationen) mellan två nätverksnav i VLSI kretsdesign där målet är att minimera den energi som används och att packa effektivt genom att minska antalet ledningar som krävs, även i datastruktur, kretskomplexitet, auktioner och en mängd andra intressanta studieområden. I den här kursen diskuteras de klassiska resultaten i kommunikationskomplexet och täcker även den senaste utvecklingen och viktiga öppna problem. Vi kommer att diskutera olika modeller av kommunikationskomplexitet --- deterministisk, nondeterministisk, asymmetrisk, randomiserad och multiparty --- och deras interrelation. Vi kommer mest att vara intresserade av att visa kombinatoriska, algebraiska och informationsteoretiska tekniker för att visa kommunikationskomplexitet lägre gränser, dvs för att visa att vissa funktioner inte kan beräknas utan mycket kommunikation oavsett hur kommunikationsalgoritmen är.

Kursomgångar saknas för aktuella eller kommande terminer.
Rubriker med innehåll från kursplan FDD3502 (VT 2019–) är markerade med en asterisk ( )

Innehåll och lärandemål

Kursinnehåll

1. Introduktion till kommunikationskomplexitet, protokollpartition och tiling, clique vs oberoende uppsättning.

2. Fooling set och rektangel storlek bunden, rangbunden, jämförelse av två tekniker, icke-determinism.

3. P = NP ∩ coNP, Separation av P och NP ∩ coNP, UP, Decision tree och sammansatta funktioner.

4. Simuleringsteorier.

5. Randomisering: Nollfel, ensidigt fel, EQ-funktion och separationer, Private coin vs public coin.

6. Protokoll för GT_n och DISJ_nk, Distributional komplexitet, Yao's minimax-princip.

7. Skillnad: Nedre gräns för IP_n, GT_n; Disjointness under produktdistribution.

8. Korruption bunden, Razborovs hårda distribution för DISJ_n, Index-funktionen.

9. Informationsteoriprimer, Indexfunktion lägre bunden, Informationskomplexitet.

10. Direkt summa av informationskomplexitet, Nedre gräns för DISJn.

11. Asymmetrisk kommunikationskomplexitet, Richness-metod, Index-funktion och skev DISJ, Application in data-structure.

12. Bevissystem, Bevisskomplexitet och kommunikationskomplexitet, (Kritisk) blockkänslighet.

13. Kommunikationskomplexitet av lyft sökproblem.

Lärandemål

Efter avslutad kurs ska studenten kunna

1. Definiera och motivera grundläggande begrepp i kommunikationskomplexitetsteori och förklara hur dessa begrepp är relaterade till varandra.

2. Beskriva den viktigaste forskningen och några toppmoderna resultat i modern kommunikationskomplexitetsteori.

3. Använda standardverktyg och tekniker i kommunikationskomplexitet för att bevisa teorem och självständigt lösa problem som kan användas för dessa metoder.

4. Presentera nuvarande komplexitets-teoretiska argument med matematisk stringens muntligt och skriftligt.

5. Läsa och förstå en forskningsartikel i kommunikationskomplexitet och visa denna förståelse genom att ge en muntlig presentation av papperet.

Kurslitteratur och förberedelser

Särskild behörighet

Ingen information tillagd

Rekommenderade förkunskaper

 Beräkningskomplexitet, sannolikhet, design och analys av algoritmen

Utrustning

Personlig dator.

Kurslitteratur

1. [Bra17]Mark Braverman. Interactive Information Complexity. SIAM Review, 59(4):803-846, 2017.  

2. [BFS86]László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory (preliminary version). In Proc. 27th IEEE Symp. on Foundations of Comp. Science (FOCS), pages 337-347, 1986.  

3. [BJKS04]Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Computer and System Sciences, 68(4):702-732, June 2004. (Preliminary Version in 43rd FOCS, 2002).  

4. [BR11]Mark Braverman and Anup Rao. Towards coding for maximum errors in interactive communication. In STOC, pages 159-166, 2011.  

5. [BW16]Mark Braverman and Omri Weinstein. A Discrepancy Lower Bound for Information Complexity. Algorithmica, 76(3):846-864, 2016.  

6. [CP10]Arkadev Chattopadhyay and Toniann Pitassi. The story of set disjointness. SIGACT News, 41(3):59-85, 2010. 

7. [CKLM17]Arkadev Chattopadhyay, Michal Koucký, Bruno Loff and Sagnik Mukhopadhyay. Simulation Theorems via Pseudorandom Properties. CoRR.abs/1704.06807, 2017. [ ArXiv ]

8. [DHS96]Martin Dietzfelbinger, Juraj Hromkovic, and Georg Schnitger. A Comparison of Two Lower-Bound Methods for Communication Complexity. Theor. Comput. Sci., 168(1):39-51, 1996.  

9. [GPW15] Mika Göös, Toniann Pitassi and Thomas Watson. Deterministic Communication vs. Partition Number. Proceedings of 56th FOCS, 1077-1088, 2015.  

10. [GW16] Mika Göös and Thomas Watson. Communication Complexity of Set-Disjointness for All Probabilities. Theory of Computing, 12(1):1-23, 2016.  

11. [HN12] Trinh Huynh and Jakob Nordström. On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity. Proceedings of the 44th STOC, 233-248, 2012.  

12. [HW07] Johan Håstad and Avi Wigderson. The Randomized Communication Complexity of Set Disjointness. Theory of Computing, 3(1):211-219, 2007.  

13. [JKS03] T. S. Jayram, Ravi Kumar, and D. Sivakumar. Two applications of information complexity. In Proc. 35th ACM Symp. on Theory of Computing (STOC), pages 673-682, 2003. [ bib | DOI ]

14. [Juk11] Stasys Jukna. Extremal Combinatorics - With Applications in Computer Science. Springer, 2011.  

15. [Juk12] Stasys Jukna. Boolean Function Complexity - Advances and Frontiers. Springer, 2012.  

16. [KN97] Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1997.  

17. [MNWS98] Peter Bro Miltersen, Noam Nisan, Shmuel Safra and Avi Wigderson On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci., 57(1): 37-49, 1998.  

18. [RY18] Anup Rao and Amir Yehudayoff. Communication Complexity (Early Draft). 

Examination och slutförande

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

Betygsskala

P, F

Examination

  • EXA1 - Tentamen, 6,0 hp, betygsskala: P, F

Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

Varje student som krediterar kursen ska

1. gå på lektioner,

2. lösa (3) problemuppsättningar, och

3. ge en teknisk muntlig presentation av ett papper.

Övriga krav för slutbetyg

För att klara kursen ska en student

1. lösa alla problemuppsättningar med minst 60% av möjliga poäng i alla, och

2. ge en tillfredsställande teknisk muntlig presentation av ett papper.

Möjlighet till komplettering

Ingen information tillagd

Möjlighet till plussning

Ingen information tillagd

Examinator

Profile picture Danupon Na Nongkai

Etiskt förhållningssätt

  • Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
  • Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
  • Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.

Ytterligare information

Kursrum i Canvas

Registrerade studenter hittar information för genomförande av kursen i kursrummet i Canvas. En länk till kursrummet finns under fliken Studier i Personliga menyn vid kursstart.

Ges av

EECS/Teoretisk datalogi

Huvudområde

Denna kurs tillhör inget huvudområde.

Utbildningsnivå

Forskarnivå

Påbyggnad

Ingen information tillagd

Forskarkurs

Forskarkurser på EECS/Teoretisk datalogi