Theory Seminar - 2007

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.
 
 
22.11.06
Speaker: Omer Barkol, Technion.
Taub 337
10:30
Title: Review of Sergey Yekhanin Latest Result: New Locally 
Decodable Codes and Private Information Retrieval Schemes 
 
 
29.11.06
Speaker: Eli Ben-Sasson, Technion.
Taub 337
10:30
Title: Subspace Polynomials and List Decoding of Reed-Solomon
Codes
 
 
6.12.06
Speaker: Zeev Dvir, Weizmann.
Taub 201
10:30
Title: Rank Extractors
 
 
13.12.06
Speaker: Ishay Haviv, Tel Aviv University.
Taub 201
10:30
Title: Tensor-based Hardness of the Shortest 
Vector Problem to within Almost Polynomial Factors.
 
 
20.12.06
Speaker: Yael Tauman-Kalai, Weizmann.
Taub 337
10:30
Title: Interactive PCP
 
 
27.12.06
Speaker: Danny Vilenchik, Tel Aviv University.
Taub 337
10:30
Title: Almost all k-colorable graphs are easy
 
 
3.1.07
Speaker: Swastik Kopparty, M.I.T.
Taub 337
13:30
Title: Local Decoding for Homomorphisms
 
 
10.1.07
Speaker: Guy Kindler, Weizmann.
Taub 337
10:30
Title: Bounded functions with small Fourier tails are Juntas
 
 
17.1.07
Speaker: Adam Tauman Kalai, TTI, Georgia Tech.
Taub 337
10:30
Title: Playing Games with Approximation Algorithms
 
 
24.1.07
Speaker: Amnon Ta-Shma, Tel Aviv University.
Taub 337
10:30
Title: Worst-case to average-case reductions revisited 
 
 
31.1.07
Speaker: Noam Livne, Weizmann.
Taub 337
10:30
Title: All Natural NPC Problems Have Average-Case Complete Versions
 
 
11.3.07
Speaker: Danny Gutfreund, Harvard.
Taub 337
10:30
Title: Designing Efficient Program Checkers by Delegating Their Work
 
 
25.3.07
Speaker: Igor Shparlinski, Macquarie University, Sydney.
Taub 337
10:30
Title: Noisy Polynomial and CRT Interpolation
 
 
15.4.07
Speaker: Keren Censor, Technion.
Taub 337
10:30
Title: Tight Bounds for Asynchronous Randomized Consensus
 
 
22.4.07
Speaker: Prahladh Harsha, TTI.
Taub 337
10:30
Title: The Communication Complexity of Correlation
 
 
29.4.07
Speaker: Amir Yehudayoff, Weizmann.
Taub 337
10:30
Title: A Lower Bound for the Size of Syntactically Multilnear Arithmetic Circuits
 
 
6.5.07
Speaker: Mira Gonen, Tel Aviv.
Taub 337
10:30
Title: On the Benfits of Adaptivity in Property Testing of Dense Graphs
 
 
13.5.07
Speaker: Tal Moran, Weizmann.
Taub 337
10:30
Title: Receipt-Free Universally-Verifiable Voting With Everlasting Privacy
 
 
20.5.07
Speaker: Yuval Rabani, Technion.
Taub 337
10:30
Title: Inference from Sparse Sampling 
 
 
27.5.07
Speaker: Ronitt Rubinfeld, M.I.T.
Taub 337
10:30
Title: Testing Independence Properties of Distributions
 
3.6.07
Speaker: Dorit Aharonov, Hebrew U.
Taub 337
10:30
Title: New Quantum algorithms: Additive approximations for #P hard problems