Theory Seminar: Difference between revisions
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"| | |||
3:00'''pm''', 2017/3/24<br> 计算机系楼 224 | |||
|align="center"| | |||
'''郑朝栋''' | |||
|| | |||
: '''Neighbor Discovery in Cognitive Radio Networks''' | |||
|| | |||
[https://arxiv.org/abs/1703.06130 Communication Primitives in Cognitive Radio Networks] | |||
|- | |||
|align="center"| | |||
3:00'''pm''', 2017/3/17<br> 计算机系楼 224 | |||
|align="center"| | |||
[http://www.carch.ac.cn/~xmsun/xmsun.htm '''孙晓明''']<br>（中科院计算所） | |||
|| | |||
: '''On the Optimality of Tape Merge''' | |||
|| | |||
[https://arxiv.org/abs/1610.03266 On the Optimality of Tape Merge of Two Lists with Similar Size] | |||
|- | |||
|align="center"| | |||
4:00'''pm''', 2017/3/10<br> 计算机系楼 224 | |||
|align="center"| | |||
宋仁杰 | |||
|| | |||
:Taylor approximation of non-vanishing complex-valued graph polynomials. | |||
|| | |||
[https://arxiv.org/abs/1607.01167 Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials] | |||
[https://arxiv.org/abs/1701.08049 On a conjecture of Sokal concerning roots of the independence polynomial] | |||
|- | |- | ||
|align="center"| | |align="center"| | ||
| Line 17: | Line 45: | ||
|| | || | ||
[https://arxiv.org/abs/1611.01647 Uniform Sampling through the Lovász Local Lemma] | [https://arxiv.org/abs/1611.01647 Uniform Sampling through the Lovász Local Lemma] | ||
|- | |- | ||
|align="center"| | |align="center"| | ||
Revision as of 07:13, 20 March 2017
- 这是南京大学理论计算机科学的讨论班主页。
- 本讨论班是open seminar，欢迎各方向的老师、研究生、以及本科生来参加。
时间地点 Speakers Topics Readings 3:00pm, 2017/3/24
计算机系楼 224郑朝栋
- Neighbor Discovery in Cognitive Radio Networks
3:00pm, 2017/3/17
计算机系楼 224孙晓明
（中科院计算所）- On the Optimality of Tape Merge
On the Optimality of Tape Merge of Two Lists with Similar Size
4:00pm, 2017/3/10
计算机系楼 224宋仁杰
- Taylor approximation of non-vanishing complex-valued graph polynomials.
Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials On a conjecture of Sokal concerning roots of the independence polynomial
3:30pm, 2016/12/22
计算机系楼 224郭珩
（Queen Mary, University of London）- Uniform Sampling through the Lovász Local Lemma
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
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;
4:30pm, 2016/10/14
计算机系楼 224宋仁杰
- Approximate Counting via Correlation Decay.
1pm, 2016/9/27
计算机系楼 224刘明谋
- Communication Complexity of Gap Hamming Distance.
4:30pm, 2016/9/23
计算机系楼 224张驰豪
（上海交通大学 & 香港中文大学）- Sparsest cut; Bourgain Theorem; Leighton-Rao algorithm.
1pm, 2016/9/20
计算机系楼 224张驰豪
（上海交通大学 & 香港中文大学）- Graph spectrum; Cheeger's Inequality; Fiedler's algorithm.