הרצאה 1 - 12.3.15

• מנהלות
• הגדרות
• מלבן קומבינטורי
• תמליל מחלק את המטריצה של הפונק' למלבנים קומבינטוריים
• fooling set
• דוגמא - הפונק' Equality
• משחקי קרצ'מר ויגדרסון וחסמים על מעגלים

הרצאה 2 - 19.3.15

• שיטות חדשות לחסמים תחתונים
• rectangle size
• rank lower bound
• הקשר בין 3 השיטות
• log rank conjecture
• הצצה לפרוטוקולים דטרמיניסטיים

הרצאה 3 - 26.3.15

• ניתוח של פרוטוקולים עם אקראיות
• חסמים במעבר מאקראיות פומבית לפרטית לבכלל לא
• משפט ניומן (אם מוכנים להוסיף שגיאה קטנה, משלמים רק Logn בשביל לעבור מאקראיות פומבית לפרטית)
• עיקרון המינימקס של יאו ו distributional complexity

הרצאה 4 - 31.3.15

• corruption ו - discrepency
• streaming algorithm

חג פסח שמח!

הרצאה 5 - 16.4.15

• אינפורמציה (במובן של תורת ה-, לא במובן של מידע)
• הגדרת אנטרופיה, אינפורמציה
• אינפורמציה פנימית וחיצונית בפרוטוקול
• למה אקראיות לא משנה בניתוח (גם פרטית וגם פומבית)

חג עצמאות שמח!

הרצאה 6 - 30.4.15

• ממשיכים עם אינפורמציה
• תזכורות (כי השיעור הקודם היה מלפני קום המדינה)
• בבעיית EQUALITY, האינפורמציה הפנימית היא (1)O. (בעזרת מטריצה הפיכה שהטורים שלה הם ה"האשים")
• בבעיית DISJOINTNESS, האינפו' הפנימית היא N פעמים האינפו' הפנימית של בעיית הAND.
• הוכחה בשני שלבים: קודם כל DIRECT SUM, אחר כך להציג התפלגות כך שבעיית DISJOINTNESS נפתרת עם DIRECT SUM
• (את ההוכחה של החלק השני לא סיימנו)

הרצאה 7 - 7.5.15

• סיום הוכחה מהשיעור הקודם
• חסם תחתון לאינדקס בעזרת אינפורמציה
• דחיסה: הצגת התוצאות הכי טובות כיום
• טענה על בניית דחיסה ודגימה בעזרת זריקת חיצים