Colloquia and Seminars

To join the email distribution list of the cs colloquia, please visit the list subscription page.

Upcoming Colloquia & Seminars

  • Theory Seminar: How to Refute a Random CSP

    David Witmer (Carnegie Melon)
    Monday, 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.

  • The 4th TCE Summer School on Cyber and Computer Security

    The 4th TCE Summer School on Cyber and Computer Security

    Sunday, 6.9.2015, 09:00
    EE Meyer Building 1003

    The 4th TCE Summer School on Cyber and Computer Security will be held on Sunday-Tuesday, September 6th-9th, 2015.

    Location: Room 1003, Meyer Building (EE), Technion, Haifa. Attendance is free, but registration is required

    Registration and preliminary program available here

    Topics include innovation and entrepreneurship in big data: from preaching to (effective, efficient and secure) data science practices. The program includes a two days’ workshop by Intel experts, presenting all security technologies integrated into computing solution, including future technologies not yet in the market.

    Eli Biham (CS, Technion)
    Avigdor Gal (IE&M, Technion)

    Guest Speakers
    Ziv Belfer (PTC)
    Orr Dunkelman (CS, University of Haifa)
    Nava Levy (Intel)
    Tomer Teller (Microsoft)