תוכן הקורס ומטרתו
סיבוכיות תקשורת עוסקת בתקשורת בין שני שחקנים (או יותר), שמעוניינים לשתף פעולה ע"מ להשיג מטרה משותפת, למשל, לחשב פונקציה על קלט שכל שחקן יודע רק חלק ממנו. מטרתנו להוכיח חסמים תחתונים על כמות התקשורת הנדרשת לשם כך.
בקורס תיאורטי זה נסקור שיטות להוכחת חסמים תחתונים, כולל שיטות אלגבריות, שיטות קומבינטוריות, וכלים מתורת האינפורמציה. כמו-כן נדגים שימושים של חסמים תחתונים בסיבוכיות תקשורת כדי להוכיח חסמים תחתונים במגוון תחומים אחרים בתיאוריה של מדעי המחשב: מעגלים בוליאניים, מבני נתונים, אלגוריתמי סטרימינג ועוד.
הקורס דורש בגרות מתמטית ורקע טוב בהסתברות.
הסילבוס המפורט מפורסם לתלמידי הקורס בלבד
