Haifa University CS Theory Seminar

The seminar, organized by Uri Rabinovich and Ronen Shaltiel, 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:30, Haifa U., Education building, room 570.

Send an email to ronen at cs.haifa.ac.il if you want to be added to the mailing list.

Here is a link to the seminar page for 2006-2007 for past talks.

Fall 2007-2008 - Schedule

15/11 Oren Weimann, MIT. Finding an Optimal Tree Searching Strategy in Linear Time.
22/11 Iftach Haitner, Weizmann. Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments.
6/12 Adi Shraibman, Hebrew University. Lower bounds on randomized and quantum communication complexity based on factorization norms.
20/12 Or Meir, Weizmann Combinatorial Construction of Locally Testable Codes.
27/12 Robert Krauthgamer, Weizmann. Overcoming the L_1 Non-Embeddability Barrier.
3/1 Uri Feige, Weizmann. Algorithms for allocation problems.
10/1 Shachar Lovett, Weizmann. Unconditional pseudorandom generators for low degree polynomials
17/1 Ran Raz, Weizmann. Elusive Functions and Lower Bounds for Arithmetic Circuits.

Continued Fall 2007-2008 - Schedule (Semester a-1).

14/2 Amir Shpilka, Technion. Reconstruction of depth-3 arithmetic circuits.
28/2 Amir Yehudayoff, Weizmann. Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors.
6/3 Danny Hermelin, CRI Haifa. On problems without polynomial kernels.
13/3 Ze'ev Dvir, Weizmann. Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits.
3/4 David Xiao, Princeton Secure Internet Path Quality Monitoring: Tradeoffs in Security and Efficiency.
17/4 Danny Harnik, IBM. Combiners via Secure Computation.

Spring 2008 - Schedule (Semester b).

15/5 Alex Samorodnitsky, Hebrew University Low degree tests at large distances.
5/6 Shay Solomon, BGU Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners.
12/6 Oded Regev, TAU Unique Games with Entangled Provers are Easy.
19/6 Alon Rosen, IDC Chosen Ciphertext Security via Correlated Products.
26/6 Irit Dinur, Weizmann TBA
3/7 Amnon Ta-Shma, TAU A combinatorial construction of almost-Ramanujan graphs using the zig-zag product
24/7 Adi Akavia, IAS Locally & Obliviously Finding Significant Fourier Coefficients