Haifa U. CS Theory Seminar - Academic year 2006-2007


The seminar this year is organazied by Ronen Shaltiel and Yuri Rabinovich. An update link is at 2007-8 seminar

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

student list is now available

Seminar hours and room: Thursday 12:15 - 13:15, Haifa U., Education building, room 570.

For list of last years talks see: previous terms

Fall 2006-2007 - Schedule

  • Nov. 9 - Ronen Shaltiel, Haifa U., abstract: Randomness Extractors: Motivation, Applications and constructions

  • Nov. 16 - Dana Moshkovitz, Weizmann Inst - cancelled . Title: Sub-Constant Error Low Degree Test of Almost-Linear Size

  • Nov. 23 - Michael Krivelevich, Tell-Aviv U., Regularity Lemma(s)

  • Nov. 30 - Eli Ben Sasson, Technion, Subspace Polynomials and List Decoding of Reed-Solomon Codes

  • Dec. 7 - Alex Samorodnitsky, HUJI, De-quantifying the lower bound for 2-query Locally Decodable Codes.

  • Dec. 14 - Iftach Haitner, Weizmann A New Interactive Hashing Theorem.

  • Dec. 21 - Weinreb Enav, Technion Private Approximation of Search Problems

  • Dec. 28 - Amnon Ta-Shma, TAU Worst-case to average-case reductions revisited

  • Jan 4 - Guy Kindler, Weizmann, TBA

  • Jan 11 - No seminar - Acavia cermony and talk.

  • Jan 18 - Dana Moshkovitz, Weizmann, Title: Sub-Constant Error Low Degree Test of Almost-Linear Size


    Spring 2007 - Schedule

  • Mar 1 - The seminar is joint with the CRI disttingushed lecture series in Mathematics and Computer Science, see announcement

  • Mar 8 - Omer Barkol Title: Review of Sergey Yekhanin latest result: New Locally decodable codes and private information retrieval schemes

  • Mar 15 - Tal Moran, Weizmann institute. Title: Receipt-Free Universally-Verifiable Voting With Everlasting Privacy

  • Mar 22 - Alex Lopez-Ortiz, University of Waterloo, Title: Optimal solution to the m-ray multi-robot searching problem with applications to contract algorithms and other non-geometric AI settings.

  • April 12 - Prahladh Harsha (Toyota Technological Institute at Chicago). Title: The Communication Complexity of Correlation.

  • April 19 - Noam Livne, Weizmann Inst. Title: All Natural NPC problems have average-case complete versions

  • May 10 - Yuval Rabani, Technion.

  • May 17 - Oded Lachish, Technion, Title: Testing st-connectivity.

  • May 24 - Shlomo Hoory, Title: Monotone circuits for the majority function.

  • May 31 - Yuval Ishai, Technion.

  • June 7 - no lecture due to student day.

  • June 14 - Amir Yehudayoff, Weizmann Inst. Title: A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

  • June 28 - Dana Ron, TAU. Title: Approximating the distance to properties in sparse graphs.