Haifa U. CS Theory Seminar - Academic year 2008-2009


The seminar this year is organazied by Yuri Rabinovich and Ilan Newman. A link for last year is at 2007-8 seminar

The seminar is meant to host talks by researchers in Theory of CS (TCS) and expose the audience to up-to-date research in TCS.

Seminar hours and room: Thursday 12:15 - 13:15, Haifa U., Jacobs, room 205.

For list of last years talks see: previous terms

Fall 2008-2009 - Schedule

  • Nov. 6 - Guy Wolfovitz, Haifa U., abstract: Lower bounds for the size of random maximal H-free graphs.

  • Nov. 13 - Dieter van Melkebeek, University of Wisconsin abstract: Lower Bounds for Satisfiability and Related Problems

  • Nov. 20 - Nati Linial, Hebrew University, abstract: Eigenfunctions of graphs and why we care

  • Nov. 27 - Eli Ben Sasson, Technion, abstract: Affine Dispersers from Subspace Polynomials

  • Dec. 4 - Sourav Chakraborty, Technion, abstract: An Online Multi-unit Auction for Perishable Goods with Unknown Supply.

  • Dec 11 - Shachar Lovett, Weizmann Institute abstract: approximation and calculation of low-degree polynomials

  • Dec. 18 - Yuval Emek, Tell-Aviv U. abstract: $k$-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees.

  • Dec. 25 - Avinatan Hassidim, Hebrew U. abstract: The Bayesian Learner is Optimal for Noisy Binary Search.

  • Jan 8 - Reuven Rubinstein, the Technion abstract: Randomized algorithms with splitting: Why the classic randomized algorithms do not work and how to make them work.

  • Jan 15 - Vincent Limouzy, CRI, abstract: On some generalization of modular decomposition and relations with graph classes


    Spring 2009 - Schedule

  • March 12 - Ilya Volkovich, Technion, abstract: Polynomial Identity Testing for Read-Once Formulas

  • March 26 - Oren Weinmann, MIT, abstract: Shortest paths and cycles in planar graphs

  • April 2 - Oren Ben-Zwi, CS Haifa abstract: Target set selection in bounded tree width graphs

  • April 23 - Krzysztof Onak, MIT, abstract: Approximating Edit Distance in Near-Linear Time

  • May 21 - No seminar : The 9th Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics and Algorithms.

  • May 28 - Adi Schreibman, TBA