סילבוס

תוכן הקורס ומטרתו

בעיה מרכזית בתיאוריה של מדעי המחשב היא האם BPP=P, כלומר, האם כל בעיה שנתנת לפתרון על ידי אלגוריתם הסתברותי יעיל, יש אלגוריתם דטרמנ?סטי יעיל הפותר אותה. כיום ידוע שהבעיה קשורה (וכמעט שקולה) לבעיה של הוכחת חסמים תחתונים על מעגלים בוליאניים לא אוניפורמים. מטרת הקורס היא להסביר קשר זה.

אנו נתחיל עם hardness vs. randomness paradigm ונראה כי קושי גורר דרנדומיזציה. אנו נדבר גם על רדוקציות לקושי בממוצע. לאחר מכן נדבר על משפטי Karp-Lipton ועל התוצאה של IKW עבור NEXP. נסיים חלק זה על ידי שנראה חסמים תחתונים למעגלים (אריתמטים או בוליאנים) תחת ההנחה של PIT יש אלגוריתמים דטרמנסטים יעילים.

בזמן שנותר אנו נדון ב easy witness method ועידונים של השיטה לחסמים על משפחות מעגלים פשוטות יותר.