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 1: Line 1:
* 这是南京大学理论计算机科学的讨论班主页。
* 这是南京大学理论计算机科学的讨论班主页。
* 本讨论班是open seminar,欢迎各方向的老师、研究生、以及本科生来参加。
* 本讨论班是open seminar,欢迎各方向的老师、研究生、以及本科生来参加。


:{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
:{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
Line 8: Line 9:
|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/7/14<br> 计算机系楼 224
|align="center"|
潘笑吟
||
:'''Optimal Hashing-based Time–Space Trade-offs for Approximate Near Neighbors'''
||
[https://arxiv.org/pdf/1608.03580.pdf Optimal Hashing-based Time–Space Trade-offs for Approximate Near Neighbors]
|-
|align="center"|
3:00'''pm''',  2017/6/30<br> 计算机系楼 224
|align="center"|
[http://www.ntu.edu.sg/home/xhbei/ '''贝小辉''']<br>(NTU)
||
:'''Cake Cutting: Networked Fairness, Envy and Truth'''
||
|-
|align="center"|
2:00'''pm''',  2017/6/23<br> 计算机系楼 224
|align="center"|
[http://homes.soic.indiana.edu/yzhoucs/ '''周源''']<br>(Indiana University)
||
:'''Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints'''
||
[https://arxiv.org/abs/1511.00648 Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints]
|-
|align="center"|
3:00'''pm''',  2017/6/16<br> 计算机系楼 224
|align="center"|
刘明谋
||
:Information complexity and direct-sum theorems.
||
[http://people.seas.harvard.edu/~madhusudan/courses/Spring2016/papers/BBCR.pdf BBCR paper]
[http://drops.dagstuhl.de/opus/volltexte/2014/4717/pdf/34.pdf The Information Complexity of Hamming Distance]
[http://people.seas.harvard.edu/~madhusudan/courses/Spring2016/papers/BJKS.pdf The disjointness lower bound of Bar-Yossef ''et al''.]
|-
|align="center"|
3:00'''pm''',  2017/5/5<br> 计算机系楼 224
|align="center"|
凤维明<br>
孙宇鑫
||
:What can be sampled locally?
||
[https://arxiv.org/abs/1702.00142 Our PODC 2017 paper]
|-
|align="center"|
3:00'''pm''',  2017/4/28<br> 计算机系楼 224
|align="center"|
[http://www.chihaozhang.com/ 张驰豪]<br>(香港中文大学)
||
:Rapid Mixing of Hypergraph Independent Set.
||
[https://arxiv.org/abs/1610.07999 Hermon-Sly-Zhang's result]
|-
|align="center"|
3:00'''pm''',  2017/4/14<br> 计算机系楼 224
|align="center"|
凤维明
||
:MCMC sampling for independent sets.
||
[http://www.comp.leeds.ac.uk/dyer/papers/dg00.pdf Dyer-Greenhill's algorithm]
[http://www1.icsi.berkeley.edu/ftp/pub/techreports/1999/tr-99-002 Luby-Vigoda's analysis of Glauber dynamics]
[http://www.emis.de/journals/EJC/Volume_8/PDF/v8i1r8.pdf Vigoda's note]
|-
|align="center"|
3:00'''pm''',  2017/4/7<br> 计算机系楼 224
|align="center"|
陈海敏
||
:Distributed algorithms for maximal independent set.
||
[http://www.cc.gatech.edu/~vigoda/7530-Spring10/MIS.pdf Luby's algorithm]
[https://arxiv.org/abs/1506.05093 Mohsen Ghaffari's breakthrough paper]
|-
|align="center"|
3:00'''pm''',  2017/3/31<br> 计算机系楼 224
|align="center"|
宋仁杰
||
:Roots of the independence polynomial.
||
[https://arxiv.org/abs/1701.08049 On a conjecture of Sokal concerning roots of the independence polynomial]
|-
|-
|align="center"|
|align="center"|
Line 84: Line 177:
:Fourier analysis; Hypercontractivity; Locality-sensitive hashing (LSH); approximate nearest neighbor search (ANNS)   
:Fourier analysis; Hypercontractivity; Locality-sensitive hashing (LSH); approximate nearest neighbor search (ANNS)   
||  
||  
[http://www.cims.nyu.edu/~naor/homepage%20files/lsh-new.pdf Motwani-Naor-Panigrahy's lower bound on LSH],
[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.]
|-
|-

Revision as of 05:34, 13 July 2017

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


时间地点 Speakers Topics Readings

3:00pm, 2017/7/14
计算机系楼 224

潘笑吟

Optimal Hashing-based Time–Space Trade-offs for Approximate Near Neighbors

Optimal Hashing-based Time–Space Trade-offs for Approximate Near Neighbors

3:00pm, 2017/6/30
计算机系楼 224

贝小辉
(NTU)

Cake Cutting: Networked Fairness, Envy and Truth

2:00pm, 2017/6/23
计算机系楼 224

周源
(Indiana University)

Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints

Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints

3:00pm, 2017/6/16
计算机系楼 224

刘明谋

Information complexity and direct-sum theorems.

BBCR paper

The Information Complexity of Hamming Distance

The disjointness lower bound of Bar-Yossef et al.

3:00pm, 2017/5/5
计算机系楼 224

凤维明
孙宇鑫

What can be sampled locally?

Our PODC 2017 paper

3:00pm, 2017/4/28
计算机系楼 224

张驰豪
(香港中文大学)

Rapid Mixing of Hypergraph Independent Set.

Hermon-Sly-Zhang's result

3:00pm, 2017/4/14
计算机系楼 224

凤维明

MCMC sampling for independent sets.

Dyer-Greenhill's algorithm

Luby-Vigoda's analysis of Glauber dynamics

Vigoda's note

3:00pm, 2017/4/7
计算机系楼 224

陈海敏

Distributed algorithms for maximal independent set.

Luby's algorithm

Mohsen Ghaffari's breakthrough paper

3:00pm, 2017/3/31
计算机系楼 224

宋仁杰

Roots of the independence polynomial.

On a conjecture of Sokal concerning roots of the independence polynomial

3:00pm, 2017/3/24
计算机系楼 224

郑朝栋

Neighbor Discovery in Cognitive Radio Networks

Communication Primitives 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

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

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