סיבוכיות תקשורת עוסקת בשאלה: כמה ביטים של תקשורת נדרשים כדי לבצע חישוב על קלט שמחולק בין שני מחשבים שונים? למשל, אם שני עותקים של קובץ שמורים על מחשבים שונים, ואנו רוצים לוודא שהעותקים זהים, כמה ביטים של תקשורת נדרשים -- האם צריך לשלוח את הקובץ כולו או שניתן להסתפק בפחות תקשורת?

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

הקורס יועבר באנגלית הסמסטר.

דרישות קדם:

• סיבוכיות (אפשר תוך-כדי באישור המרצה)

דרישות הקורס:

• תרגילי בית דו-שבועיים

• בחינה