Theory Seminar and 高级算法 (Fall 2016)/Greedy and Local Search: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>TCSseminar
No edit summary
 
imported>Etone
(Created page with " <font color=red size=4>Under construction.</font> 50px")
 
Line 1: Line 1:
* 这是南京大学理论计算机科学的讨论班主页。
  <font color=red size=4>Under construction.</font> [[File:Under_construction.png‎|50px]]
* 本讨论班是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;"
|-
|bgcolor="#A7C1F2" align="center"|'''时间地点'''
|bgcolor="#A7C1F2" align="center"|'''Speakers'''
|bgcolor="#A7C1F2" align="center"|'''Topics'''
|bgcolor="#A7C1F2" align="center"|'''Readings'''
|-
|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"|
钦明珑
||
: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"|
4:30'''pm''',  2016/12/9<br> 计算机系楼 224
|align="center"|
凤维明
||
: Rigorous Analysis of 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"|
4:30'''pm''',  2016/11/25<br> 计算机系楼 224
|align="center"|
陈海敏
||
: Lovász local lemma and approximate counting
||
[https://arxiv.org/abs/1610.04317 Ankur Moitra's breakthrough paper on counting CNF]
|-
|align="center"|
4:30'''pm''',  2016/11/11<br> 计算机系楼 224
|align="center"|
潘笑吟
||
: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.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.]
|-
|align="center"|
4:30'''pm''',  2016/10/28<br> 计算机系楼 223
|align="center"|
孙宇鑫
||
:MCMC sampler; Glauber dynamics; path-coupling;
||
[http://www.cc.gatech.edu/~vigoda/MCMC_Course/survey.pdf Frieze-Vigoda survey]
|-
|-
|align="center"|
4:30'''pm''',  2016/10/14<br> 计算机系楼 224
|align="center"|
宋仁杰
||
:Approximate Counting via Correlation Decay.
||
[http://dimacs.rutgers.edu/~dror/pubs/ind_from_tree.pdf Weitz's paper]
|-
|align="center"|
1'''pm''',  2016/9/27<br> 计算机系楼 224
|align="center"|
刘明谋
||
:Communication Complexity of Gap Hamming Distance.
||
[http://web.cs.ucla.edu/~sherstov/pdf/hamming.pdf Sherstov's simplified proof]
[https://arxiv.org/pdf/1009.3460v3.pdf Chakrabarti-Regev 2010]
|-
|align="center"|
4:30'''pm''',  2016/9/23<br> 计算机系楼 224
|align="center"|
[http://basics.sjtu.edu.cn/~chzhang/ 张驰豪]<br>（上海交通大学 & 香港中文大学）
||
:Sparsest cut; Bourgain Theorem; Leighton-Rao algorithm.
||
Luca Trevisan's notes: [https://people.eecs.berkeley.edu/~luca/expanders2016/lecture09.pdf 1], [https://people.eecs.berkeley.edu/~luca/expanders2016/lecture10.pdf 2]
|-
|align="center"|
1'''pm''',  2016/9/20<br> 计算机系楼 224
|align="center"|
[http://basics.sjtu.edu.cn/~chzhang/ 张驰豪]<br>（上海交通大学 & 香港中文大学）
||
:Graph spectrum; Cheeger's Inequality; Fiedler's algorithm.
||
Luca Trevisan's notes: [https://people.eecs.berkeley.edu/~luca/expanders2016/lecture00.pdf 1], [https://people.eecs.berkeley.edu/~luca/expanders2016/lecture02.pdf 2], [https://people.eecs.berkeley.edu/~luca/expanders2016/lecture03.pdf 3], [https://people.eecs.berkeley.edu/~luca/expanders2016/lecture04.pdf 4]
|}

Revision as of 09:24, 25 September 2016

Under construction.
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=Theory_Seminar&oldid=6977"