Theory Seminar - 2009

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.

• Speaker: Dieter van Melkebeek, U. of Wisconsin
  • Title: Lower Bounds for Satisfiability and Related Problems
  • Time: 23.11.08, 12:00
  • Place: Taub 601


• Speaker: Enav Weinreb, Technion
  • Title: Partition Arguments in Multiparty Communication Complexity
  • Time: 30.11.08
  • Place: Taub 601


• Speaker: Ronen Shaltiel, Haifa University
  • Title: Hardness amplification proofs require majority
  • Time: 07.12.08, 12:00
  • Place: Taub 601


• Speaker: Shachar Lovett, Weizmann Institute of Science
  • Title: Approximation and calculation of low-degree polynomials
  • Time: 14.12.08, 12:00
  • Place: Taub 601


• Speaker: Avinatan Hassidim, M.I.T.
  • Title: Derandomizing Algorithms on Product Distributions and Improved Implicit Probe Search using Same-source Extractors for very low entropy
  • Time: 28.12.08, 12:00
  • Place: Taub 601


• Speaker: Guy Rothblum, M.I.T.
  • Title: When and How Can Data be Efficiently Released with Privacy?
  • Time: 04.01.09, 12:00
  • Place: Taub 601


• Speaker: Adi Akavia, IAS & DIMACS
  • Title: Finding Significant Fourier Transform Coefficients Deterministically and Locally
  • Time: 11.01.09, 12:00
  • Place: Taub 701


• Speaker: Tamar Ziegler, Technion
  • Title: The inverse conjecture for the Gowers norm over finite fields
  • Time: 18.01.09, 12:00
  • Place: Taub 601


• Speaker: Oded Regev, Tel Aviv
  • Title: Unique Games with Entangled Provers are Easy
  • Time: 25.01.09, 12:00
  • Place: Taub 601


• Speaker: Ishai Haviv, Tel Aviv
  • Title: Rounding Parallel Repetitions of Unique Games
  • Time: 8.02.09, 12:00
  • Place: Taub 601


• Speaker: Enav Weinreb, Technion
  • Title: On the Complexity of Communication Complexity
  • Time: 15.02.09
  • Place: Taub 601


• Speaker: Avi Wigderson, IAS
  • Title: New Direct Product Code Testers, and PCPs
  • Time: 01.03.09, 12:00
  • Place: Taub 337


• Speaker: Klim Efremenko, Weizmann Insitute of Science
  • Title: 3-Query Locally Decodable Codes of Subexponential Length
  • Time: 18.03.09, 14:30
  • Place: Taub 701


• Speaker: Prahladh Harsha, UT Austin & Technion
  • Title: 2-query PCP Composition
  • Time: 25.03.09, 15:00
  • Place: Taub 701


• Speaker: Elad Eban, Hebrew University
  • Title: Interactive Proofs For Quantum Computations
  • Time: 22.04.09, 15:00
  • Place: Taub 337


• Speaker: Shachar Lovett, Weizmann Institute of Science
  • Title: List-decoding for Reed-Muller Codes
  • Time: 06.05.09, 15:00
  • Place: Taub 337


• Speaker: : Eli Ben Sasson, Technion
  • Title: Affine Dispersers from Subspace Polynomials
  • Time: 13.05.09, 15:00
  • Place: Taub 337


• Speaker: : Troy Lee, Columbia University
  • Title: Rank minimization via the gamma_2 norm
  • Time: 07.06.09, 14:30
  • Place: Taub 337


• Speaker: : Partha Mukhopadhyay, Technion
  • Title: Identity Testing, Isolation and Lower Bounds
  • Time: 10.06.09, 15:00
  • Place: Taub 337


• Speaker: Michael Viderman, Technion
  • Title: Locally Testable Codes Require Redundant Testers
  • Time: 17.06.09, 15:00
  • Place: Taub 337


• Speaker: Udi Wieder, Microsoft Research
  • Title: Balanced Allocations: Simplifications and Generalizations
  • Time: 24.06.09, 15:00
  • Place: Taub 337