Theory Seminar
- 这是南京大学理论计算机科学的讨论班主页。
- 本讨论班是open seminar，欢迎各方向的老师、研究生、以及本科生来参加。
时间地点 Speakers Topics Readings 7:30pm, 2020/4/17
ZOOM
5253336283刘明谋 - Succinct data structures for sets of unknown sizes
2:00pm, 2020/4/10
ZOOM
5253336283赵铭南 - Information Causality as a Physical Principle
2:00pm, 2020/4/3
ZOOM
5253336283吴旭东 - 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.
2:00pm, 2020/3/20
ZOOM
5253336283汪昌盛
- Separations in communication complexity using cheat sheets and information complexity. Part I.
2:00pm, 2020/3/13
ZOOM
5253336283陈小羽
- Eigenvalues 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 Algorithms3: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.
2:00pm, 2019/12/27
计算机系楼224王天行
- Shearer's bound.
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
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
3:00pm, 2019/7/26
计算机系楼 319刘明谋
- Lower Bounds for Succinct Range Minimum Query
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 Tight3:00pm, 2018/12/18
计算机系楼 224高宇
GaTech, advised by Richard Peng (彭泱)- Graph algorithms via random walks.
3:00pm, 2018/12/11
计算机系楼 224- Distributed Statistical Estimation of Matrix Products with Applications.
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 notes7:00pm, 2018/6/28
计算机系楼 231- 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 Jamming3: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.
3:00pm, 2018/1/12
计算机系楼 224刘明谋
- Communication Complexity of Lopsided Set Disjointness.
3:00pm, 2017/12/29
计算机系楼 224潘笑吟
- Boolean function analysis and hypercontractivity.
3:00pm, 2017/12/15
计算机系楼 224宋仁杰
- Belief Propagation and Bethe Approximation.
3:00pm, 2017/12/8
计算机系楼 319张驰豪
（香港中文大学）- Counting hypergraph colorings in the local lemma regime.
3:00pm, 2017/12/1
计算机系楼 224陈海敏
- 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
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
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
3:00pm, 2017/6/16
计算机系楼 224刘明谋
- Information complexity and direct-sum theorems.
3:00pm, 2017/5/5
计算机系楼 224凤维明
孙宇鑫- What can be sampled locally?
3:00pm, 2017/4/28
计算机系楼 224张驰豪
（香港中文大学）- Rapid Mixing of Hypergraph Independent Set.
3:00pm, 2017/4/14
计算机系楼 224凤维明
- MCMC sampling for independent sets.
3:00pm, 2017/4/7
计算机系楼 224陈海敏
- Distributed algorithms for maximal independent set.
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
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
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.