88-558 גרפים מרחיבים סמסטר א תשעו: הבדלים בין גרסאות בדף
אין תקציר עריכה |
|||
| שורה 3: | שורה 3: | ||
==קישורים== | ==קישורים== | ||
* [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 | * [http://www.wisdom.weizmann.ac.il/~dinuri/mypapers/combpcp.pdf The PCP Theorem by gap amplification] by Irit Dinur | ||
==תרגילי בית== | ==תרגילי בית== | ||
גרסה מ־12:17, 8 בינואר 2016
קישורים
- Expander graphs and their applications, by Shlomo Hoory, Nathan Linial and Avi Wigderson
- The PCP Theorem by gap amplification by Irit Dinur
תרגילי בית
הודעות
הערות לגבי תרגיל בית 2
- אנא הגישו את תרגילי הבית לדפנה במזכירות מדעי המחשב (ולא לסילבי).
- בשאלה 6, כשנאמר ש "X הוא ספרי", הכוונה היא שהסופרמום שמוגדר בשאלה נלקח מבין כל הווקטורים הספריים. (למעשה, כפי שנאמר בהרצאה, אין בכך הגבלת כלליות כי הסופרמום אכן תמיד מתקבל עבור ווקטור ספרי.)
- המושגים "מטריצת השכנויות" ו"מטריצת הסמיכויות" שמופיעים בתרגיל הם אותו מושג.