88-558 גרפים מרחיבים סמסטר א תשעו

88-558 גרפים מרחיבים

קישורים

• Expander graphs and their applications, by Shlomo Hoory, Nathan Linial and Avi Wigderson
• The PCP Theorem by gap amplification by Irit Dinur

תרגילי בית

• תרגיל 1 (עדכון בתאריך 2.12.2015)
• תרגיל 2
• תרגיל 3
• תרגיל 4

הודעות

הערות לגבי תרגיל בית 2

1. אנא הגישו את תרגילי הבית לדפנה במזכירות מדעי המחשב (ולא לסילבי).
2. בשאלה 6, כשנאמר ש "X הוא ספרי", הכוונה היא שהסופרמום שמוגדר בשאלה נלקח מבין כל הווקטורים הספריים. (למעשה, כפי שנאמר בהרצאה, אין בכך הגבלת כלליות כי הסופרמום אכן תמיד מתקבל עבור ווקטור ספרי.)
3. המושגים "מטריצת השכנויות" ו"מטריצת הסמיכויות" שמופיעים בתרגיל הם אותו מושג.