Theory Seminar: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
No edit summary
Roundgod (talk | contribs)
No edit summary
 
(111 intermediate revisions by 5 users not shown)
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 7: Line 8:
|bgcolor="#A7C1F2" align="center"|'''Speakers'''
|bgcolor="#A7C1F2" align="center"|'''Speakers'''
|bgcolor="#A7C1F2" align="center"|'''Topics'''
|bgcolor="#A7C1F2" align="center"|'''Topics'''
|bgcolor="#A7C1F2" align="center"|'''Readings'''
|bgcolor="#A7C1F2" align="center"|'''Materials'''
 
 
|-
|align="center"|
7:00 '''pm''',  2022/3/9 <br> 计算机系楼224
 
|align="center"|
[http://wcysai.com  '''王淳扬''']
||
: Towards derandomising Markov Chain Monte Carlo
||
 
|-
|align="center"|
7:00 '''pm''',  2022/3/3 <br> 计算机系楼224
 
|align="center"|
董杨静
||
: Locally testable classical codes and quantum LPDC codes
||
 
|-
|align="center"|
10:00 '''am''',  2020/12/13 <br> Zoom 5221214665
 
|align="center"|
[https://www-users.cs.umn.edu/~xuexx193/ '''XUE Jie''']
||
: Efficient Algorithms and Data Structures for Geometric Computing
||
密码2020
 
 
|-
|align="center"|
2:00 '''pm''',  2020/12/9 <br> 计算机系楼 224
|align="center"|
[http://www.cs.huji.ac.il/~yupan/ '''刘宇攀''']
||
: StoqMA meets distribution testing
||
[https://arxiv.org/abs/2011.05733 paper]
 
|-
|align="center"|2:00 '''pm''',  2020/6/5<br> ZOOM <br>5253336283
|align="center"|
陈海敏
||
: Competitive Broadcast against Adaptive Adversary in Multi-channel Radio Networks
||
[https://arxiv.org/abs/2001.03936 paper]
 
|-
|align="center"|
2:00'''pm''',  2020/5/15<br> ZOOM <br>5253336283
|align="center"|
张昕渊
||
:Counting graph colourings.
||
[http://tcs.nju.edu.cn/yinyt/multispin_13.pdf Improved FPTAS for Multi-Spin Systems.],
 
|-
|align="center"|
8:00 '''pm''',  2020/5/1<br> ZOOM <br>5253336283
|align="center"|
凤维明
||
: Fast sampling and counting k-SAT solutions in the local lemma regime
||
[https://arxiv.org/abs/1911.01319 Fast sampling and counting k-SAT solutions in the local lemma regime]
 
|-
|align="center"|
2:00'''pm''',  2020/4/24<br> ZOOM <br>5253336283
|align="center"|
陈海敏
||
: Two lower bounds towards fault-tolerant consensus
||
[https://www.amazon.com/Distributed-Algorithms-Kaufmann-Management-Systems/dp/1558603484 Book Chapter 6.7], [https://groups.csail.mit.edu/tds/papers/Lynch/FischerLynchMerritt-dc.pdf paper]
 
|-
|align="center"|
7:30'''pm''',  2020/4/17<br> ZOOM <br>5253336283
|align="center"|
刘明谋
||
: Succinct data structures for sets of unknown sizes
||
[https://docs.qq.com/pdf/DQXN1U2FLdGhGUk5a paper]
 
|-
|align="center"|
2:00'''pm''',  2020/4/10<br> ZOOM <br>5253336283
|align="center"|
赵铭南
||
: Information Causality as a Physical Principle
||
[https://arxiv.org/pdf/0905.2292.pdf paper]
 
|-
|align="center"|
2:00'''pm''',  2020/4/3<br> ZOOM <br>5253336283
|align="center"|
吴旭东
||
: Moser and tardos meet Lovász
||
[https://dl.acm.org/doi/10.1145/1993636.1993669 Moser and tardos meet Lovász]
 
|-
|align="center"|
2:00'''pm''',  2020/3/27<br> ZOOM <br>5253336283
|align="center"|
董杨静
||
: Separations in communication complexity using cheat sheets and information complexity. Part II.
||
[https://arxiv.org/abs/1605.01142 paper]
|-
|align="center"|
2:00'''pm''',  2020/3/20<br> ZOOM <br>5253336283
|align="center"|
汪昌盛
||
: Separations in communication complexity using cheat sheets and information complexity. Part I.
||
[https://arxiv.org/abs/1605.01142 paper]
|-
|align="center"|
2:00'''pm''',  2020/3/13<br> ZOOM <br>5253336283
|align="center"|
陈小羽
||
:Eigenvalues and mixing time.
||
[https://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf Markov chain and mixing time]
|-
|align="center"|
1:00'''pm''',  2020/3/6<br> ZOOM <br>5253336283
|align="center"|
姜勇刚
||
:Network Decomposition and Derandomization on Local Model.
||
[https://arxiv.org/pdf/1907.10937.pdf Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization]<br>
[https://arxiv.org/pdf/1711.02194.pdf On Derandomizing Local Distributed Algorithms]
 
|-
|align="center"|
3:00'''pm''',  2020/2/28<br> ZOOM<br> 5253336283
|align="center"|
刘弘洋
||
:Rapid mixing of Glauber dynamics for colorings.
||
[http://people.csail.mit.edu/moitra/docs/colormerge.pdf Improved Bounds for Sampling Colorings via Linear Programming.]<br>
[https://arxiv.org/pdf/1804.04025.pdf  Rapid mixing of Glauber dynamics for colorings below Vigoda's 11/6 threshold.]
 
|-
|align="center"|
3:00'''pm''',  2020/2/21<br> ZOOM<br> 331722721
|align="center"|
王淳扬
||
:Counting CNF solutions.
||
[https://arxiv.org/pdf/1610.04317.pdf Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models.]
 
 
 
|-
|align="center"|
7:00'''pm''',  2020/1/7<br> 计算机系楼224
|align="center"|
凤维明
||
:Strong spatial mixing for graph colourings.
||
[https://arxiv.org/pdf/1207.1223.pdf Strong spatial mixing for list coloring of graphs.],
 
 
|-
|align="center"|
7:00'''pm''',  2020/1/3<br> 计算机系楼224
|align="center"|
张昕渊
||
:A deterministic algorithm for counting colorings with 2∆ colors.
||
[https://arxiv.org/pdf/1906.01228.pdf A deterministic algorithm for counting colorings with 2∆ colors.],
 
|-
|align="center"|
3:00'''pm''',  2020/1/2<br> 计算机系楼224
|align="center"|
[https://quics.umd.edu/people/tongyang-li 李彤阳]
<br />
University of Maryland, College Park
||
:Quantum algorithms for machine learning and optimization.
||
[https://arxiv.org/abs/1710.02581], [https://arxiv.org/abs/1809.01731], [https://arxiv.org/abs/1901.03254], [https://arxiv.org/abs/1904.02276]
 
|-
|align="center"|2:00'''pm''',  2019/12/27<br> 计算机系楼224
|align="center"|
王天行
||
:Shearer's bound.
||
[https://link.springer.com/content/pdf/10.1007%2FBF02579368.pdf On a problem of spencer]
 
|-
|align="center"|
7:00'''pm''',  2019/11/18<br> 计算机系楼224
|align="center"|
[https://tsdjh.github.io 钦明珑]
||
:The Invariance Principle
||
[https://arxiv.org/pdf/math/0503503.pdf Noise stability of functions with low influences: invariance and optimality]
 
|-
|align="center"|
7:00'''pm''',  2019/10/27<br> 计算机系楼224
|align="center"|
王天行
||
:Maximal matching on Massively Parallel Computation model
||
[https://people.inf.ethz.ch/gmohsen/MPA19/Notes/MPA.pdf Massively Parallel Algorithms]
 
|-
|align="center"|
6:30'''pm''',  2019/9/27<br> 计算机系楼224
|align="center"|
陈海敏
||
:Constant-Length Labeling Schemes for Deterministic Radio Broadcast
||
[https://arxiv.org/abs/1710.03178 Constant-Length Labeling Schemes for Deterministic Radio Broadcast]
 
|-
|align="center"|
3:00'''pm''',  2019/8/29<br> 计算机系楼 224
|align="center"|
[https://iiis.tsinghua.edu.cn/en/weizh/ '''魏朝晖''']
||
:Analytic Semi-device-independent Entanglement Quantification for Bipartite Quantum States
||
[https://arxiv.org/abs/1903.05303v2 paper]
|-
|align="center"|
3:00'''pm''',  2019/7/26<br> 计算机系楼 <font color = red>319</font>
|align="center"|
刘明谋
||
:Lower Bounds for Succinct Range Minimum Query
||
[https://people.csail.mit.edu/mip/papers/ranklb/paper.pdf '''Cell-probe lower bounds for succinct partial sums'''], [https://arxiv.org/abs/2004.05738 paper]
|-
|align="center"|
3:00'''pm''',  2019/7/11<br> 计算机系楼 112
|align="center"|
 
[https://homepages.inf.ed.ac.uk/hguo/research.html '''郭珩''']<br>University of Edinburgh
||
:'''Modified log-Sobolev inequalities for strongly log-concave distributions.'''
||
[https://homepages.inf.ed.ac.uk/hguo/papers/Log-Sob-matroid.pdf Modified log-Sobolev inequalities for strongly log-concave distributions. ]
|-
|align="center"|
3:00'''pm''',  2019/7/5<br> 计算机系楼 222
|align="center"|
 
[http://homes.sice.indiana.edu/yzhoucs/ '''周源''']<br>UIUC
||
:'''Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits.'''
||
[https://arxiv.org/abs/1904.00242 Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits. ]
|-
|align="center"|
3:00'''pm''',  2019/5/31<br> 计算机系楼 224
|align="center"|
 
陈海敏
||
:Fast and Resource Competitive Broadcast in Multi-channel Radio Networks.
||
[https://arxiv.org/abs/1904.06328 Fast and Resource Competitive Broadcast in Multi-channel Radio Networks. ]
|-
|align="center"|
3:00'''pm''',  2019/5/28<br> 计算机系楼 224
|align="center"|
 
[http://www.ntu.edu.sg/home/yili/ '''李翼''']
||
:'''Tight Bounds for the Subspace Sketch Problem with Applications'''
||
paper [https://arxiv.org/abs/1904.05543]
|-
|-
|align="center"|
3:00'''pm''',  2019/5/10<br> 计算机系楼 224
|align="center"|
 
'''黄昕'''<br>CUHK <br> 导师: [http://www.cse.cuhk.edu.hk/~syzhang/  张胜誉]
||
:'''Envy-freeness up to any item with high Nash welfare: The virtue of donating items'''
||
[https://arxiv.org/abs/1902.04319 Envy-freeness up to any item with high Nash welfare: The virtue of donating items]
|-
|-
|align="center"|
3:00'''pm''',  2018/12/20<br> 计算机系楼 224
|align="center"|
 
'''何昆'''<br>中科院计算所 <br> 导师: [http://theory.ict.ac.cn/sunxiaoming/  孙晓明]
||
:'''Lovász Local Lemma: Classical, Commuting and Quantum'''
||
[https://arxiv.org/pdf/1709.05143.pdf Variable Version Lovász Local Lemma: Beyond Shearer's Bound]<br>[https://arxiv.org/pdf/1804.07055.pdf Quantum Lovász Local Lemma: Shearer's Bound is Tight]
|-
|align="center"|
3:00'''pm''',  2018/12/18<br> 计算机系楼 224
|align="center"|
 
[https://www.aco.gatech.edu/users/gao-yu/ '''高宇''']<br>GaTech, advised by [https://www.cc.gatech.edu/~rpeng/  Richard Peng (彭泱)]
||
:'''Graph algorithms via random walks.'''
||
papers[https://arxiv.org/abs/1704.04830],[https://arxiv.org/abs/1804.04038],[https://arxiv.org/abs/1805.12051]
|-
|align="center"|
3:00'''pm''',  2018/12/11<br> 计算机系楼 224
|align="center"|
 
[http://homes.sice.indiana.edu/qzhangcs/ '''张勤''']
||
:'''Distributed Statistical Estimation of Matrix Products with Applications.'''
||
paper[http://homes.sice.indiana.edu/qzhangcs/papers/pods18-matrix.pdf]. and slides[http://homes.sice.indiana.edu/qzhangcs/papers/pods18-MM-slides.pdf]
|-
|align="center"|
4:00'''pm''',  <font color = red>2018/9/6</font><br> 计算机系楼 223
|align="center"|
 
[http://www.cs.huji.ac.il/~yupan/ '''刘宇攀''']
||
:'''Toward an area law for stoquastic frustration-free Hamiltonians.'''
||
[https://epubs.siam.org/doi/abs/10.1137/08072689X Complexity of Stoquastic Frustration-Free Hamiltonians]<br/>
[https://arxiv.org/pdf/1401.3916.pdf Quantum Hamiltonian Complexity]<br/>
[http://cseweb.ucsd.edu/~slovett/workshops/quantum-computation-2018/files/david-day4-1.pdf David Gosset's lecture notes]
 
|-
|align="center"|
7:00'''pm''',  2018/6/28<br> 计算机系楼 231
|align="center"|
 
[http://quics.umd.edu/people/penghui-yao '''姚鹏晖''']
||
:'''Rectangles are Nonnegative Juntas.'''
||
[https://www.cs.utexas.edu/~diz/pubs/junta.pdf Rectangles are Nonnegative Juntas]
|-
|align="center"|
3:00'''pm''', 2018/6/1<br> 计算机系楼 224
|align="center"|
[http://tcs.nju.edu.cn/chenhm/ 陈海敏]
||
:1-to-1 Resource-Competitive Broadcast with Jamming.
||
[https://arxiv.org/abs/1202.6456 A resource-competitive jamming defense] <br/>
[https://web.eecs.umich.edu/~pettie/papers/Jamming.pdf (Near) Optimal Resource-Competitive Broadcast with Jamming]
|-
|align="center"|
3:00'''pm''',  2018/5/3<br> 计算机系楼 319
|align="center"|
刘明谋
||
:An XOR Lemma for Quantum Communication Complexity.
||
[https://arxiv.org/abs/1011.4935 Strong direct product theorems for quantum communication and query complexity]
|-
|align="center"|
3:00'''pm''',  2018/4/26<br> 计算机系楼 319
|align="center"|
[http://lcs.ios.ac.cn/~mingji/ '''夏盟佶''']<br>(中科院软件所)
||
:'''On variable Lovász Local Lemma.'''
||
[https://arxiv.org/abs/1709.05143 Variable Version Lovász Local Lemma: Beyond Shearer's Bound]
|-
|align="center"|
3:00'''pm''',  2018/1/12<br> 计算机系楼 224
|align="center"|
刘明谋
||
:Communication Complexity of Lopsided Set Disjointness.
||
[http://people.csail.mit.edu/mip/papers/structures/paper.pdf Unifying the Landscape of Cell-Probe Lower Bounds]
|-
|align="center"|
3:00'''pm''',  2017/12/29<br> 计算机系楼 224
|align="center"|
潘笑吟
||
:Boolean function analysis and hypercontractivity.
||
[https://www.cs.cmu.edu/~odonnell/boolean-analysis/ Ryan O’Donnell's lecture notes]
|-
|align="center"|
3:00'''pm''',  2017/12/15<br> 计算机系楼 224
|align="center"|
宋仁杰
||
:Belief Propagation and Bethe Approximation.
||
[http://www.cs.princeton.edu/courses/archive/spr06/cos598C/papers/YedidaFreemanWeiss2004.pdf Yedida-Freeman-Weiss paper]
|-
|align="center"|
3:00'''pm''',  2017/12/8<br> 计算机系楼 319
|align="center"|
[http://www.chihaozhang.com '''张驰豪''']<br>(香港中文大学)
||
:Counting hypergraph colorings in the local lemma regime.
||
[https://arxiv.org/abs/1711.03396 Counting hypergraph colorings in the local lemma regime]
|-
|align="center"|
3:00'''pm''',  2017/12/1<br> 计算机系楼 224
|align="center"|
陈海敏
||
:A lower bound for the distributed Lovász local lemma
||
[https://arxiv.org/abs/1511.00900 A lower bound for the distributed Lovász local lemma]
|-
|align="center"|
3:00'''pm''',  2017/11/10<br> 计算机系楼 <font color=red>319</font>
|align="center"|
刘雅辉
||
:A constructive algorithm for the Lovász Local Lemma on permutations
||
[http://www.cs.umd.edu/~srin/PDF/2014/lll-perm-jou.pdf A constructive algorithm for the Lovász Local Lemma on permutations]
|-
|align="center"|
3:00'''pm''',  2017/11/3<br> 计算机系楼 224
|align="center"|
[https://www.quantumlah.org/people/penghui '''姚鹏晖''']<br>(U Maryland)
||
:Information Complexity
||
[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/10/20<br> 计算机系楼 <font color=red>224</font>
|align="center"|
樊一麟
||
:Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds.
||
[http://theory.stanford.edu/~yuhch123/files/RangeCounting.pdf Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds]
|-
|align="center"|
3:00'''pm''',  2017/9/15<br> 计算机系楼 <font color=red>223</font>
|align="center"|
凤维明
||
:Randomly Coloring Constant Degree Graphs
||
[https://www.math.cmu.edu/~af1p/Texfiles/colorbdd.pdf Dyer-Frieze-Hayes-Vigoda]
|-
|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"|
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"|
3:30'''pm''',  2016/12/22<br> 计算机系楼 224
|align="center"|
[http://pages.cs.wisc.edu/~hguo/ '''郭珩''']<br>(Queen Mary, University of London)
||
: '''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"|
Line 17: Line 625:
||  
||  
[https://arxiv.org/pdf/1602.07415.pdf Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling]
[https://arxiv.org/pdf/1602.07415.pdf Ensuring Rapid Mixing and Low Bias for Asynchronous Gibbs Sampling]
|-
|align="center"|
2:00'''pm''',  2016/12/6<br> 计算机系楼 224
|align="center"|
[https://www.quantumlah.org/people/penghui '''姚鹏晖''']<br>(U Maryland)
||
: '''Some Recent Progress on Quantum Information Complexity'''
||
[https://arxiv.org/pdf/1605.04601v1.pdf Lower bound on expected communication cost of quantum Huffman coding]
[https://arxiv.org/pdf/1404.1366v4.pdf New one shot quantum protocols with application to communication complexity]
[https://arxiv.org/abs/1611.08946.pdf Exponential Separation of Quantum Communication and Classical Information]
|-
|-
|align="center"|
|align="center"|
Line 34: Line 655:
: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.]
|-
|-

Latest revision as of 17:28, 7 March 2023

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


时间地点 Speakers Topics Materials


7:00 pm, 2022/3/9
计算机系楼224

王淳扬

Towards derandomising Markov Chain Monte Carlo

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

董杨静

Locally testable classical codes and quantum LPDC codes

10:00 am, 2020/12/13
Zoom 5221214665

XUE Jie

Efficient Algorithms and Data Structures for Geometric Computing

密码2020


2:00 pm, 2020/12/9
计算机系楼 224

刘宇攀

StoqMA meets distribution testing

paper

2:00 pm, 2020/6/5
ZOOM
5253336283

陈海敏

Competitive Broadcast against Adaptive Adversary in Multi-channel Radio Networks

paper

2:00pm, 2020/5/15
ZOOM
5253336283

张昕渊

Counting graph colourings.

Improved FPTAS for Multi-Spin Systems.,

8:00 pm, 2020/5/1
ZOOM
5253336283

凤维明

Fast sampling and counting k-SAT solutions in the local lemma regime

Fast sampling and counting k-SAT solutions in the local lemma regime

2:00pm, 2020/4/24
ZOOM
5253336283

陈海敏

Two lower bounds towards fault-tolerant consensus

Book Chapter 6.7, paper

7:30pm, 2020/4/17
ZOOM
5253336283

刘明谋

Succinct data structures for sets of unknown sizes

paper

2:00pm, 2020/4/10
ZOOM
5253336283

赵铭南

Information Causality as a Physical Principle

paper

2:00pm, 2020/4/3
ZOOM
5253336283

吴旭东

Moser and tardos meet Lovász

Moser and tardos meet Lovász

2:00pm, 2020/3/27
ZOOM
5253336283

董杨静

Separations in communication complexity using cheat sheets and information complexity. Part II.

paper

2:00pm, 2020/3/20
ZOOM
5253336283

汪昌盛

Separations in communication complexity using cheat sheets and information complexity. Part I.

paper

2:00pm, 2020/3/13
ZOOM
5253336283

陈小羽

Eigenvalues and mixing time.

Markov chain and mixing time

1:00pm, 2020/3/6
ZOOM
5253336283

姜勇刚

Network Decomposition and Derandomization on Local Model.

Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
On Derandomizing Local Distributed Algorithms

3:00pm, 2020/2/28
ZOOM
5253336283

刘弘洋

Rapid mixing of Glauber dynamics for colorings.

Improved Bounds for Sampling Colorings via Linear Programming.
Rapid mixing of Glauber dynamics for colorings below Vigoda's 11/6 threshold.

3:00pm, 2020/2/21
ZOOM
331722721

王淳扬

Counting CNF solutions.

Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models.


7:00pm, 2020/1/7
计算机系楼224

凤维明

Strong spatial mixing for graph colourings.

Strong spatial mixing for list coloring of graphs.,


7:00pm, 2020/1/3
计算机系楼224

张昕渊

A deterministic algorithm for counting colorings with 2∆ colors.

A deterministic algorithm for counting colorings with 2∆ colors.,

3:00pm, 2020/1/2
计算机系楼224

李彤阳
University of Maryland, College Park

Quantum algorithms for machine learning and optimization.

[1], [2], [3], [4]

2:00pm, 2019/12/27
计算机系楼224

王天行

Shearer's bound.

On a problem of spencer

7:00pm, 2019/11/18
计算机系楼224

钦明珑

The Invariance Principle

Noise stability of functions with low influences: invariance and optimality

7:00pm, 2019/10/27
计算机系楼224

王天行

Maximal matching on Massively Parallel Computation model

Massively Parallel Algorithms

6:30pm, 2019/9/27
计算机系楼224

陈海敏

Constant-Length Labeling Schemes for Deterministic Radio Broadcast

Constant-Length Labeling Schemes for Deterministic Radio Broadcast

3:00pm, 2019/8/29
计算机系楼 224

魏朝晖

Analytic Semi-device-independent Entanglement Quantification for Bipartite Quantum States

paper

3:00pm, 2019/7/26
计算机系楼 319

刘明谋

Lower Bounds for Succinct Range Minimum Query

Cell-probe lower bounds for succinct partial sums, paper

3:00pm, 2019/7/11
计算机系楼 112

郭珩
University of Edinburgh

Modified log-Sobolev inequalities for strongly log-concave distributions.

Modified log-Sobolev inequalities for strongly log-concave distributions.

3:00pm, 2019/7/5
计算机系楼 222

周源
UIUC

Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits.

Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits.

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

陈海敏

Fast and Resource Competitive Broadcast in Multi-channel Radio Networks.

Fast and Resource Competitive Broadcast in Multi-channel Radio Networks.

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

李翼

Tight Bounds for the Subspace Sketch Problem with Applications

paper [5]

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

黄昕
CUHK
导师: 张胜誉

Envy-freeness up to any item with high Nash welfare: The virtue of donating items

Envy-freeness up to any item with high Nash welfare: The virtue of donating items

3:00pm, 2018/12/20
计算机系楼 224

何昆
中科院计算所
导师: 孙晓明

Lovász Local Lemma: Classical, Commuting and Quantum

Variable Version Lovász Local Lemma: Beyond Shearer's Bound
Quantum Lovász Local Lemma: Shearer's Bound is Tight

3:00pm, 2018/12/18
计算机系楼 224

高宇
GaTech, advised by Richard Peng (彭泱)

Graph algorithms via random walks.

papers[6],[7],[8]

3:00pm, 2018/12/11
计算机系楼 224

张勤

Distributed Statistical Estimation of Matrix Products with Applications.

paper[9]. and slides[10]

4:00pm, 2018/9/6
计算机系楼 223

刘宇攀

Toward an area law for stoquastic frustration-free Hamiltonians.

Complexity of Stoquastic Frustration-Free Hamiltonians
Quantum Hamiltonian Complexity
David Gosset's lecture notes

7:00pm, 2018/6/28
计算机系楼 231

姚鹏晖

Rectangles are Nonnegative Juntas.

Rectangles are Nonnegative Juntas

3:00pm, 2018/6/1
计算机系楼 224

陈海敏

1-to-1 Resource-Competitive Broadcast with Jamming.

A resource-competitive jamming defense
(Near) Optimal Resource-Competitive Broadcast with Jamming

3:00pm, 2018/5/3
计算机系楼 319

刘明谋

An XOR Lemma for Quantum Communication Complexity.

Strong direct product theorems for quantum communication and query complexity

3:00pm, 2018/4/26
计算机系楼 319

夏盟佶
(中科院软件所)

On variable Lovász Local Lemma.

Variable Version Lovász Local Lemma: Beyond Shearer's Bound

3:00pm, 2018/1/12
计算机系楼 224

刘明谋

Communication Complexity of Lopsided Set Disjointness.

Unifying the Landscape of Cell-Probe Lower Bounds

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

潘笑吟

Boolean function analysis and hypercontractivity.

Ryan O’Donnell's lecture notes

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

宋仁杰

Belief Propagation and Bethe Approximation.

Yedida-Freeman-Weiss paper

3:00pm, 2017/12/8
计算机系楼 319

张驰豪
(香港中文大学)

Counting hypergraph colorings in the local lemma regime.

Counting hypergraph colorings in the local lemma regime

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

陈海敏

A lower bound for the distributed Lovász local lemma

A lower bound for the distributed Lovász local lemma

3:00pm, 2017/11/10
计算机系楼 319

刘雅辉

A constructive algorithm for the Lovász Local Lemma on permutations

A constructive algorithm for the Lovász Local Lemma on permutations

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

姚鹏晖
(U Maryland)

Information Complexity

The disjointness lower bound of Bar-Yossef et al.

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

樊一麟

Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds.

Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

3:00pm, 2017/9/15
计算机系楼 223

凤维明

Randomly Coloring Constant Degree Graphs

Dyer-Frieze-Hayes-Vigoda

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