Theory Seminar: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
No edit summary
imported>Etone
No edit summary
Line 8: Line 8:
|bgcolor="#A7C1F2" align="center"|'''Topics'''
|bgcolor="#A7C1F2" align="center"|'''Topics'''
|bgcolor="#A7C1F2" align="center"|'''Readings'''
|bgcolor="#A7C1F2" align="center"|'''Readings'''
|-
|align="center"|
4:30'''pm''',  2016/11/25<br>
|align="center"|
陈海敏
||
: Lovász local lemma and approximate counting
||
[https://arxiv.org/abs/1610.04317 Ankur Moitra's breakthrough paper on counting CNF]
|-
|-
|align="center"|
|align="center"|

Revision as of 06:13, 22 November 2016

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

4:30pm, 2016/11/25

陈海敏

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