-
04-24
2009
Soundness amplification in probabilistically checkable proofs (with an eye towar
Speaker: Andrej Bogdanov The Chinese University of Hong Kong Time: 2009-04-24 10:00-2009-04-24 11:30 Venue: FIT Building 1-222, Tsinghua University Abstract: DESCRIPTION: A key step in the proof o...
-
04-16
2009
Lift-and-project integrality gaps from local-global metrics
Speaker: Moses Charikar Princeton University Time: 2009-04-16 16:00-2009-04-16 17:00 Venue: FIT Building 4-603, Tsinghua University Download: Click! Abstract: Lift-and-project procedures are system...
-
04-16
2009
Soft heaps simplified
Speaker: Prof. Uri Zwick Tel Aviv University Time: 2009-04-16 15:00-2009-04-16 16:00 Venue: FIT Building 4-603, Tsinghua University Download: Click! Abstract: Chazelle (JACM 47(6), 2000) devised an...
-
04-09
2009
Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)
Speaker: Ning Xie MIT Time: 2009-04-09 16:00-2009-04-09 17:00 Venue: FIT Building 4-603, Tsinghua University Download: Click! Abstract: For Boolean functions that are $\epsilon$-far from the set of...
-
04-09
2009
Chosen Ciphertext Security via Correlated Products
Speaker: Alon Rosen IDC Herzliya Time: 2009-04-09 15:00-2009-04-09 16:00 Venue: FIT Building 4-603, Tsinghua University Download: Click! Abstract: In this talk I will present a new notion of securi...
-
03-06
2009
Geometry and expansion: A survey
Speaker: Sanjeev Arora Princeton University Time: 2009-03-06 14:00-2009-03-06 15:00 Venue: Lecture Hall, FIT Building, Tsinghua University Download: Click! Abstract: Partitioning a graph into two (...