Theory Seminar

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

时间地点	Speakers	Topics	Readings
7:30pm, 2020/4/30 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
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