課程資訊
 課程名稱 通訊複雜度概論Introduction to Communication Complexity 開課學期 105-2 授課對象 電機資訊學院  資訊工程學研究所 授課教師 陳偉松 課號 CSIE5118 課程識別碼 922EU4400 班次 學分 3.0 全/半年 半年 必/選修 選修 上課時間 星期一2,3,4(9:10~12:10) 上課地點 備註 本課程以英語授課。上課教室：資546。總人數上限：25人 Ceiba 課程網頁 http://ceiba.ntu.edu.tw/1052CSIE5118_ 課程簡介影片 核心能力關聯 核心能力與課程規劃關聯圖 課程大綱 為確保您我的權利,請尊重智慧財產權及不得非法影印 課程概述 The goal of this course is to get acquainted with some basic tools of communication complexity. The focus is the two-party model introduced by {\em Yao} in 1979. In the setting there are two players {\em Alice} and {\em Bob}. Each of them holds some data which are unknown to the other. Suppose they want to compute a function on the data found in both of them. Communication complexity deals with the fundamental question: How many times do Alice and Bob have to communicate with each other in order to compute the function? 課程目標 To be familiar with the notion of communication complexity and its application in other branches of computer science. 課程要求 Basic knowledge of discrete mathematics, probability theory 預期每週課後學習時數 Office Hours 另約時間 指定閱讀 Communication complexity, by Kushilevitz and Nisan. 參考書目 Communication complexity, by Kushilevitz and Nisan. 評量方式(僅供參考)
 課程進度
 週次 日期 單元主題 Week 1 2/20 Lesson 1: Preliminaries Week 2 2/27 No lesson due to peace memorial holiday Week 3 3/06 Lesson 2: Communication protocols Week 4 3/13 Lesson 3: Rectangles and fooling sets Week 5 3/20 Lesson 4: Rank lower bound Week 6 3/27 Lesson 5: Nondeterministic protocols (HW 1 is out, due in two weeks) Week 7 4/03 No lesson Week 8 4/10 Lesson 6: Det. and nondet. communication complexity Week 9 4/17 Lesson 7: Ranks and covers Week 10 4/24 Lesson 8: Randomized protocols Week 11 5/01 No lesson Week 12 5/08 Lesson 9: Det. and randomized protocols Week 13 5/15 Lesson 10: Distributional complexity and discrepancy Week 14 5/22 Lesson 11: Asymmetric communication and variable partition models Week 15 5/29 No lesson Week 16 6/05 Lesson 12 & 13: Applications on networks and VLSI and data structures Week 17 6/12 Lesson 14: Applications on Turing machines