Theory Seminar: Difference between revisions

Revision as of 02:42, 7 November 2016

时间地点	Speakers	Topics	Readings
4:30pm, 2016/11/11 计算机系楼	潘笑吟	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

@@ Line 17: / Line 17: @@
 ||
 :[http://www.cims.nyu.edu/~naor/homepage%20files/lsh-new.pdf Motwani-Naor-Panigrahy's lower bound on LSH]
-:[http://www.cs.cmu.edu/~odonnell/papers/lsh.pdf O’Donnell-Wu-Zhou's optimal lower bound on LSH]
+[http://www.cs.cmu.edu/~odonnell/papers/lsh.pdf O’Donnell-Wu-Zhou's optimal lower bound on LSH]
-:[https://arxiv.org/abs/1608.03580 a hash-based lower bound of Andoni et al.]
+[https://arxiv.org/abs/1608.03580 a hash-based lower bound of Andoni et al.]
 |-
 |align="center"|