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 13: Line 13:
:Communication Complexity of Gap Hamming Distance.  
:Communication Complexity of Gap Hamming Distance.  
||  
||  
[https://arxiv.org/pdf/1009.3460v3.pdf Chakrabarti-Regev 2010], [http://web.cs.ucla.edu/~sherstov/pdf/hamming.pdf Sherstov's proof]
[http://web.cs.ucla.edu/~sherstov/pdf/hamming.pdf Sherstov's simplified proof]
[https://arxiv.org/pdf/1009.3460v3.pdf Chakrabarti-Regev 2010]
|-
|-
|align="center"|
|align="center"|

Revision as of 10:55, 23 September 2016

时间地点 Speakers Topics Readings

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