Theory Seminar
- 这是南京大学理论计算机科学的讨论班主页。
- 本讨论班是open seminar，欢迎各方向的老师、研究生、以及本科生来参加。
时间地点 Speakers Topics Readings 3:00pm, 2019/7/26
计算机系楼 224刘明谋
- 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 [1]
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.