88-558 גרפים מרחיבים סמסטר א תשעו
קישורים[עריכה]
- Expander graphs and their applications, by Shlomo Hoory, Nathan Linial and Avi Wigderson
- The PCP Theorem by gap amplification by Irit Dinur
תרגילי בית[עריכה]
הודעות[עריכה]
כנס לכבוד יום הולדת 60 של נוגה אלון[עריכה]
בשבוע הבא, בין התאריכים 17.1 ל-21.1, יתקיים כנס Combinatorics: Challenges and Applications באוניברסיטת תל אביב. ראו באתר הכנס [1] את רשימת הדוברים. כולם מוזמנים!
הכניסה חופשית, והמארגנים מבקשים להרשם באתר לצורך הערכת מספר האנשים שמגיעים.
הערות לגבי תרגיל בית 2[עריכה]
- אנא הגישו את תרגילי הבית לדפנה במזכירות מדעי המחשב (ולא לסילבי).
- בשאלה 6, כשנאמר ש "X הוא ספרי", הכוונה היא שהסופרמום שמוגדר בשאלה נלקח מבין כל הווקטורים הספריים. (למעשה, כפי שנאמר בהרצאה, אין בכך הגבלת כלליות כי הסופרמום אכן תמיד מתקבל עבור ווקטור ספרי.)
- המושגים "מטריצת השכנויות" ו"מטריצת הסמיכויות" שמופיעים בתרגיל הם אותו מושג.