-
04-12
2006
Probabilistic Proof Systems: Part I
Speaker: Oded Goldreich Weizmann Institute of Science, Israel Time: 2006-04-12 14:00-2006-04-12 15:00 Venue: FIT Building,Tsinghua University Abstract: Various types of probabilistic proof systems ...
-
04-12
2006
A Short Introduction to Combinatorial Property Testing: Part I
Speaker: Dana Ron Tel Aviv University, Israel Time: 2006-04-12 15:00-2006-04-12 16:00 Venue: FIT Building,Tsinghua University Abstract: Property testing problems are a relaxation of decision proble...
-
04-07
2006
Exclusive Set Systems and Applications
Speaker: David Woodruff MIT Time: 2006-04-07 10:00-2006-04-07 11:00 Venue: FIT Building,Tsinghua University Abstract: A family of subsets C of [n] = {1, ..., n} is (r,t)-exclusive if for every subs...
-
03-31
2006
Gowers Uniformity, Influence of Variables and Probabilistically Checkable Proofs
Speaker: Luca Trevisan UC Berkeley Time: 2006-03-31 14:00-2006-03-31 15:00 Venue: FIT Building, Tsinghua University Abstract: The "Gowers uniformity norms" measure the "pseudorandomness" of functio...
-
03-29
2006
Pseudo randomness and Combinatorial Constructions
Speaker: Luca Trevisan UC Berkeley Time: 2006-03-29 14:00-2006-03-29 15:00 Venue: FIT Building, Tsinghua University Abstract: In combinatorics, the probabilistic method is a very powerful tool to p...
-
03-21
2006
Search via Quantum Walks
Speaker: Ashwin Nayak University of Waterloo, and Perimeter Institute for Theoretical Physics Time: 2006-03-21 14:30-2006-03-21 14:30 Venue: FIT-1-222 Abstract: Randomization of quantum states is ...