Theory Seminar

From TCS Wiki
Revision as of 11:53, 4 December 2016 by imported>Etone
Jump to navigation Jump to search
  • 这是南京大学理论计算机科学的讨论班主页。
  • 本讨论班是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

2:00pm, 2016/12/6
计算机系楼 224

姚鹏晖
(U Maryland)

Some Recent Progress on Quantum Information Complexity

Lower bound on expected communication cost of quantum Huffman coding

New one shot quantum protocols with application to communication complexity

Exponential Separation of Quantum Communication and Classical Information

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