קולוקוויום וסמינרים

כדי להצטרף לרשימת תפוצה של קולוקוויום מדעי המחשב, אנא בקר בדף מנויים של הרשימה.

קולוקוויום וסמינרים בקרוב

  • Theory Seminar: How to Refute a Random CSP

    דובר:
    דוד ויטמר (קרנגי מלון)
    תאריך:
    יום שני, 10.8.2015, 10:30
    מקום:
    יפורסם

    Consider a random constraint satisfaction problem (CSP) over $n$ variables with $m$ constraints, each being a predicate $P$ applied to $k$ random literals. When $m \gg n$ the instance will be unsatisfiable with high probability, and the natural associated algorithmic task is to find a refutation --- i.e., a certificate of unsatisfiability. Understanding the density required for average-case refutation is important in various areas of complexity including cryptography, proof complexity, and learning theory.

    In this talk, we give a general criterion that often allows efficient refutation at much lower densities than previous algorithms. Specifically, if $P$ fails to support a $t$-wise uniform probability distribution, then there is an efficient algorithm that refutes random instances with high probability, provided $m \gg n^{t/2}$. Indeed, our algorithm will ``somewhat strongly'' refute instances, certifying that the optimum is bounded away from 1. If $t = k$, then we furthermore get the strongest possible refutation, certifying that the optimum is within o(1) of its expectation. This last result is new even in the context of random $k$-SAT. Our refutation algorithm can be carried out by the $O(1)$-round SOS SDP hierarchy and prior work on SDP hierarchies provides evidence that its dependence on $m$ is optimal for every $P$.

    This is joint work with Sarah R. Allen and Ryan O’Donnell.

  • בית-ספר קיץ הרביעי בנושא סייבר אבטחת מחשוב ומידע

    בית-ספר קיץ הרביעי בנושא סייבר אבטחת מחשוב ומידע

    תאריך:
    יום ראשון, 6.9.2015, 09:00
    מקום:
    חדר 1003, בניין מאייר, הפקולטה להנדסת חשמל

    בימים א'-ג', 6-9 בספטמבר 2015 יערוך המרכז להנדסת מחשבים בטכניון את כנס הקיץ השנתי הרביעי שלו בנושא סייבר ואבטחת מחשוב ומידע. ראשי הכנס, פרופ' אלי ביהם ופרופ' אביגדור גל, וכן הדוברים בכנס, אנשי אקדמיה ותעשייה, הם ממובילי התחומים בארץ ובעולם. ניתן לקרוא עוד מידע על הכנס כאן.

    חלק מההרצאות יינתנו באנגלית. השנה מבנה השבוע שונה מהרגיל וכולל גם נושאים של מידע רב ויזמות הקשורים לאבטחת מידע. במסגרת השבוע יינתנו יומיים של הרצאות מאת מומחי אינטל לאבטחת מחשבים, הכוללות סקירה של הטכנולוגיות המובילות בשוק, ואף סקירת עומק של טכנולוגיות עתידיות.

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

    המרכז להנדסת מחשבים הוא מרכז מחקר יישומי משותף לפקולטות להנדסת חשמל ומדעי המחשב בטכניון, שותפות בו חברות רבות וחברי סגל משתי הפקולטות. המרכז מקדם מחקר מעשי ויישומי ומאפשר דיאלוג שוטף בין התעשייה לאקדמיה בנושאים מחקריים המעניינים את שני הצדדים.