88-558 גרפים מרחיבים סמסטר א תשעו: הבדלים בין גרסאות בדף

גרסה אחרונה מ־15:07, 12 בינואר 2016

קישורים

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

הודעות

כנס לכבוד יום הולדת 60 של נוגה אלון

בשבוע הבא, בין התאריכים 17.1 ל-21.1, יתקיים כנס Combinatorics: Challenges and Applications באוניברסיטת תל אביב. ראו באתר הכנס [1] את רשימת הדוברים. כולם מוזמנים!

הכניסה חופשית, והמארגנים מבקשים להרשם באתר לצורך הערכת מספר האנשים שמגיעים.

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

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

@@ שורה 2: / שורה 2: @@
 ==קישורים==
-* ספרות: [http://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/ Expander graphs and their applications], by Shlomo Hoory, Nathan Linial and Avi Wigderson
+* [http://www.ams.org/journals/bull/2006-43-04/S0273-0979-06-01126-8/ Expander graphs and their applications], by Shlomo Hoory, Nathan Linial and Avi Wigderson
+* [http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/combpcp.pdf The PCP Theorem by gap amplification] by Irit Dinur
 ==תרגילי בית==
@@ שורה 9: / שורה 10: @@
 * [[מדיה: 88558exe2_2016A.pdf | תרגיל 2]]
 * [[מדיה: 88558exe3_2016A.pdf | תרגיל 3]]
+* [[מדיה: 88558exe4_2016A.pdf | תרגיל 4]]
 ==הודעות==
+===כנס לכבוד יום הולדת 60 של נוגה אלון===
+בשבוע הבא, בין התאריכים 17.1 ל-21.1, יתקיים כנס [http://www.math.tau.ac.il/~noga60/  Combinatorics: Challenges and Applications] באוניברסיטת תל אביב. ראו באתר הכנס [http://www.math.tau.ac.il/~noga60/] את רשימת הדוברים. כולם מוזמנים!
+הכניסה חופשית, והמארגנים מבקשים להרשם באתר לצורך הערכת מספר האנשים שמגיעים.
 ===הערות לגבי תרגיל בית 2===