נושאים

  • דרישות הקורס

    הציון בקורס יקבע באופן הבא:

    50 נקודות - מבחן כיתה.

    50 נקודות - ציוני עבודות בית (ינתנו 4-6 עבודות)

    • רשימת ספרות

      1. L. Babai and P. Frankl. Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science.

      2. S. Jukna. Extremal Combinatorics.  

      3. O. Pikhurko. Algebraic Methods in Combinatorics

      4. N. Alon. Combinatorial Nullstellensatz.

      5. S. Horry, N. Linial and A. Wigderson. Expander graphs and their applications

      6. R. Saptharishi. A survey of lower bounds in arithmetic circuit complexity

      7. V. Guruswami, C. Umans and S. Vadhan Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes

        • שיעור 1 29.10.14

          1. משפט לינדסטרום
          2. הלמה של רדון
          3. משפט הלי
          4. n נקודות שאינן על ישר אחד קובעות n ישרים לפחות.
          5. Even town - Odd town
          6. אי שיוויון פישר
          7. מספרי רמזי והבניה ההסתברותית של ארדש
          8. בניית גרף רמזי של נאגי

          • שיעור 2 5.11.2014

            1. משפט גרהם-פולק

            2. נקודות בעלות שני מרחקים


            • שיעור 3 12.11

              דיברנו על משפט Ray-Chaudhuri-Wilson ווריאנטים שלו (מודולרי-לא מודולרי, יוניפורמי-לא יוניפורמי).

              ראינו מספר שימושים: 

              מספר צביעה של גרף מרחקי היחידה במרחב (ראינו גם חסמי כיסוי ואריזה ע״י כדורים n-מימדיים).

              בניית גרף רמזי של Frankl-Wilson

              • שיעור 4 19.11.2014

                דיברנו על ערכים עצמיים של מטריצות.

                הוכחנו את משפט הופמן סינגלטון ומשפט הידידות.

                התחלנו לדבר על גרפים מרחיבים וראינו שימוש להורדת טעות באלגוריתמים אקראיים.

                דיברנו גם על קודים לתיקון שגיאות.

                • שיעור 5 26.11.2014

                  בנייה של קודים לתיקון שגיאות מגרפים מרחיבים דו-צדדיים ואלגוריתם לתיקון שגיאות.

                  גרף אקראי מרחיב בהסתברות גבוהה

                  חסם תחתון על הערך העצמי השני (בערך מוחלט) ע״י שורש הדרגה

                  הצגת הבנייה של LPS של גרף רמנוג׳אן

                  Expander Mixing Lemma

                  • שיעור 6 3.12.2014

                    הילוכים מקריים על גרפים

                    הילוך מקרי על גרף מרחיב ״בורח״ מכל קבוצה 

                    חסם צ׳רנוף

                    חסם צ׳רנוף להילוכים על גרפים מרחיבים

                    • שיעור 7 10.12.2014

                      סיימנו הוכחת חסם צ׳רנוף להילוכים מקריים על גרפים מרחיבים

                      הגדרנו אקסטרקטורים

                      בניית אקסטרקטור למקורות עם מינ-אנטרופי גבוה דרך הילוך על גרף מרחיב.

                      • שיעור 8 17.12.2014

                        קודי Reed-Solomon

                        אלגוריתם Berlekamp-Welch לפענוח טעויות עד חצי המרחק

                        הגדרת List-Decoding

                        חסם קומבינטורי על גודל הרשימה לקודי ריד-סולומון

                        אלגוריתם List-Decoding של מדהו סודאן.

                        בעיית קקייה (Kakeya) הממשית ובשדות סופיים.

                        פתרון לבעיית קקייה בשדות סופיים. 

                        • שיעור 9 24.12.2014

                          הגדרת Condenser

                          קשר לגרפים מרחיבים

                          בנייה של GUV 

                          משפט אפסים קומבינטורי

                          • שיעור 10 31.12.2014

                            שימושים של משפט האפסים הקומבינטורי:

                            1. 1. משפט קושי-דבנפורט
                            2. 2. משפט שבלי-וורנינג
                            3. 3. הצגת הקוביה הבוליאנית המנוקבת כאיחוד של על מישורים.
                            4. 4. למת הפרמננט ושימושיה


                            טרנסורם פורייה.

                            מבחן ליניאריות של BLR.

                            • נושא 15