The focus of the seminar will be on recent results in theoretical computer science
in areas such as algorithms, complexity, and cryptography.
Speakers will be invited from universities in Israel and abroad.
28.10.07
|
Speaker: Johann (Janos) Makowsky, Technion. |
Taub 337 10:30
|
Title: Why is the chromatic polynomial a polynomial? |
4.11.07
|
Speaker: Jonathan Hoch, Weizmann.
|
Taub 337 10:30
|
Title: Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments |
11.11.07
|
Speaker: Ronen Shaltiel, Haifa.
|
Taub 337 10:30
|
Title: Low-end uniform hardness versus randomness tradeoffs for AM |
25.11.07
|
Speaker: Shachar Lovett, Weizmann
|
Taub 337 10:30
|
Title: Unconditional pseudorandom generators for low degree polynomials |
2.12.07
|
Speaker: Julia Kempe, Tel Aviv.
|
Taub 337 10:30
|
Title: On the hardness of entangled multi-prover games |
16.12.07
|
Speaker: Ofer Neiman, Hebrew U.
|
Taub 337 10:30
|
Title: Local Embedding of Metric Spaces |
23.12.07
|
Speaker: Guy Rothblum, MIT.
|
Taub 337 10:30
|
Title: Delegating Computation: Interactive Proofs for Mortals |
30.12.07
|
Speaker: Asaf Shapira, Microsoft.
|
Taub 337 11:00
|
Title: Approximate Hypergraph Partitioning and Applications |
13.1.08
|
Speaker: Amir Yehudayoff, Weizmann.
|
Taub 337 11:00
|
Title: Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors |
20.1.08
|
Speaker: Adi Shraibman, Weizmann.
|
Taub 337 11:00
|
Title: Disjointness is hard in the multi-party number-on-the-forehead model |
27.1.08
|
Speaker: Vinod Vaikuntanathan, M.I.T. |
Taub 337 11:00
|
Title: Trapdoors for Hard Lattices, and New Lattice-based Cryptography |
3.2.08
|
Speaker: Shahar Dobzinski, Hebrew U and Technion. |
Taub 337 11:00
|
Title: The Power of VCG: On Algorithms that are Maximal In Range |
10.2.08
|
Speaker: Irit Dinur, Weizmann.
|
Taub 337 11:00
|
Title: Local testing of direct products |
24.2.08
|
Speaker: Zeev Dvir, Weizmann. |
Taub 337 11:00
|
Title: Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits |
2.3.08
|
Speaker: Robert Krauthgamer, Weizmann. |
Taub 337 11:00
|
Title: Lower Bounds for Edit Distance Estimation |
9.3.08
|
Speaker: Jakob Nordström, Royal Institute of Technology, Stockholm, Sweden |
Taub 337 11:00
|
Title: Towards an Optimal Separation of Space and Length in Resolution |
30.3.08
|
Speaker: David Xiao, Princeton.
|
Taub 337 11:00
|
Title: Secure Internet Path Quality Monitoring: Tradeoffs in Security and Efficiency |
6.4.08
|
Speaker: Avraham Ben-Aroya, Tel Aviv. |
Taub 337 11:00
|
Title: A combinatorial construction of almost-Ramanujan graphs using the zig-zag product |
25.5
|
Speaker: Alex Samorodnitsky, Hebrew U.
|
Taub 337 11:00
|
Title: Bounds for codes and an isoperimetric inequality in the Hamming cube |
1.6.08
|
Speaker: Guy Kindler, Weizmann.
|
Taub 337 11:00
|
Title: Can cubic tiles be sphere-like? |
15.6.08
|
Speaker: Venkatesan Guruswami, Washington U.
|
Taub 337 11:00
|
Title: Expander codes, Euclidean sections, and compressed sensing |
22.6.08
|
Speaker: Avinatan Hassidim, Hebrew U.
|
Taub 337 11:00
|
Title: Quantum Multi Prover Interactive Proofs with Communicating Provers |
29.6.08
|
Speaker: Zeev Dvir, Weizmann. |
Taub 337 11:00
|
Title: The finite field Kakeya conjecture |
6.7.08
|
Speaker: Or Meir, Weizmann. |
Taub 337 11:00
|
Title: Combinatorial Construction of Locally Testable Codes |
13.7.08
|
Speaker: Benjamin Rossman, M.I.T. |
Taub 337 11:00
|
Title: The Constant-Depth Complexity of k-Clique
|
20.7.08
|
Speaker: Dana Moshkovitz, Weizmann. |
Taub 337 11:00
|
Title: Two Query PCP with Sub-Constant Error
|
3.8.08
|
Speaker: Asaf Nussbaum, Weizmann. |
Taub 337 11:00
|
Title: Pseudorandom graphs - what if distinguishers where first order properties? |