Theory Seminar

• 这是南京大学理论计算机科学的讨论班主页。
• 本讨论班是open seminar，欢迎各方向的老师、研究生、以及本科生来参加。

时间地点	Speakers	Topics	Readings
4:30pm, 2016/12/9 计算机系楼 224	凤维明	Rigorous Analysis of Asynchronous Gibbs Sampling	Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling
4:30pm, 2016/11/25 计算机系楼 224	陈海敏	Lovász local lemma and approximate counting	Ankur Moitra's breakthrough paper on counting CNF
4:30pm, 2016/11/11 计算机系楼 224	潘笑吟	Fourier analysis; Hypercontractivity; Locality-sensitive hashing (LSH); approximate nearest neighbor search (ANNS)	Motwani-Naor-Panigrahy's lower bound on LSH, O’Donnell-Wu-Zhou's optimal lower bound on LSH, a hash-based lower bound of Andoni et al.
4:30pm, 2016/10/28 计算机系楼 223	孙宇鑫	MCMC sampler; Glauber dynamics; path-coupling;	Frieze-Vigoda survey
4:30pm, 2016/10/14 计算机系楼 224	宋仁杰	Approximate Counting via Correlation Decay.	Weitz's paper
1pm, 2016/9/27 计算机系楼 224	刘明谋	Communication Complexity of Gap Hamming Distance.	Sherstov's simplified proof Chakrabarti-Regev 2010
4:30pm, 2016/9/23 计算机系楼 224	张驰豪 （上海交通大学 & 香港中文大学）	Sparsest cut; Bourgain Theorem; Leighton-Rao algorithm.	Luca Trevisan's notes: 1, 2
1pm, 2016/9/20 计算机系楼 224	张驰豪 （上海交通大学 & 香港中文大学）	Graph spectrum; Cheeger's Inequality; Fiedler's algorithm.	Luca Trevisan's notes: 1, 2, 3, 4