סילבוס

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

פונקציות בוליאניות


1. מבוא לאנליזת פורייה דיסקרטית
נפתח את הקורס בהצגת הגדרות ורעיונות בסיסיים, כגון התמרת פורייה וinfluence של משתנים. במהלך הקורס נציג כלים בסיסיים ותוצאות בתחום, כמו אי-השוויון ההיפר-קונטרקטיבי, משפט KKL, משפטי החונטה של פרידגוט ובורגיין, sharp thresholds ועקרונן הinvariance.

2. אפליקציות של אנליזת פורייה בתחומים שונים בתיאורייה של מדעי המחשב
נדון בכמה יישומים של אנליזת פורייה בתחומים כמו property testing ולמידה חישובית.

3. אפליקציות של אנליזת פורייה בקושי קירוב
נדון בקצרה בהשערת Unique-Games, השערה מרכזית במדעי המחשב התיאורטיים. נשתמש בתוצאות בסיסיות מאנליזת פורייה כדי להראות כמה מסקנות מהשערה זו, כגון האופטימליות (המותנית) של אלגוריתם Goemans-Williamson עבור בעיית Max-Cut, וקושי (מותנה) של בעיית Vertex-Cover.

4. יישומי ניתוח פורייה קומבינטוריקה אקסטרימאלית.
קומבינטוריקה קיצונית היא התחום השואל, בהכללה, כמה גדול יכול להיות אוסף כלשהו של אובייקטים ספציפיים, תחת תנאים מסוימים. לדוגמא, כמה גדול יכול אוסף של תתי-קבוצות של [n] להיות תחת ההנחה שלכל זוג באוסף יש חיתוך לא טריוויאלי? נראה איך תוצאות מאנליזה ממלאות תפקיד חשוב במתן תשובות מפורטות לחלק משאלות אלו.

5. נושאים מתקדמים.
לקראת סוף הקורס נדון בנושאים מתקדמים יותר ובתוצאות בתחום שהושגו רק לאחרונה. אלה כוללים את הפתרון של השערת הsensitivity, הרחבה של אי-השוויון ההיפר-קונטרקטיבי המכונה בספרות "היפר-קונטרקטיביות גלובלית", והשערת הFourier entropy.