Study Group: Difference between revisions
imported>TCSseminar |
imported>TCSseminar |
||
| (17 intermediate revisions by the same user not shown) | |||
| Line 3: | Line 3: | ||
* 本学习小组对外开放，欢迎各方向的老师、研究生、以及本科生来参加。 | * 本学习小组对外开放，欢迎各方向的老师、研究生、以及本科生来参加。 | ||
== | ==理论计算机科学学习小组== | ||
:{|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 13: | Line 13: | ||
|- | |- | ||
|align="center"| | |align="center"| | ||
7:30'''pm''', 2020/5/8<br> ZOOM<br>5253336283 | |||
|align="center"| | |||
王天行 | |||
|| | |||
:Boolean functions and the Fourier expansion | |||
|| | |||
[http://www.cs.tau.ac.il/~amnon/Classes/2016-PRG/Analysis-Of-Boolean-Functions.pdf Analysis Of Boolean Functions]: Chapter 1. | |||
|- | |||
|align="center"| | |||
7:00'''pm''', 2018/12/14<br> 计算机系楼 224 | |||
|align="center"| | |||
凤维明 | |||
|| | |||
:Probability-Generating Function and Galton–Watson Process | |||
|| | |||
[http://galton.uchicago.edu/~lalley/Courses/312/Branching.pdf Galton–Watson process] | |||
|- | |||
|align="center"| | |||
7:00'''pm''', 2018/12/11<br> 计算机系楼 224 | |||
|align="center"| | |||
刘明谋 | |||
|| | |||
:Lower Bound of Locality-Sensitive Hashing | |||
|| | |||
|- | |||
|align="center"| | |||
10:00'''am''', 2018/11/26<br> 计算机系楼 224 | |||
|align="center"| | |||
凤维明 | |||
|| | |||
:The Recursion of Counting Monotone CNF Solutions | |||
|| | |||
[https://homepages.inf.ed.ac.uk/hguo/papers/HIS.pdf Approximation via Correlation Decay when Strong Spatial Mixing Fails] | |||
|- | |||
|align="center"| | |||
7:00'''pm''', 2018/6/29<br> 计算机系楼 224 | |||
|align="center"| | |||
陈海敏 | |||
|| | |||
:Randomized Computation (Ⅱ). | |||
|| | |||
[http://theory.cs.princeton.edu/complexity/book.pdf Sanjeev Arora and Boaz Barak's Book]: Chapter 7. | |||
|- | |||
|align="center"| | |||
7:00'''pm''', 2018/6/22 <br> 计算机系楼 224 | |||
|align="center"| | |||
樊一麟 | |||
|| | |||
:Boolean Circuits. | |||
|| | |||
[http://theory.cs.princeton.edu/complexity/book.pdf Sanjeev Arora and Boaz Barak's Book]: Chapter 6. | |||
|- | |||
|align="center"| | |||
7:00'''pm''', 2018/6/15 <br> 计算机系楼 224 | |||
|align="center"| | |||
刘明谋 | |||
|| | |||
:Interactive Proofs (Ⅱ). | |||
|| | |||
[http://theory.cs.princeton.edu/complexity/book.pdf Sanjeev Arora and Boaz Barak's Book]: Chapter 8 | |||
|- | |||
|align="center"| | |||
7:00'''pm''', 2018/6/7<br> 计算机系楼 224 | |||
|align="center"| | |||
宋仁杰 | |||
|| | |||
:Class #P. | |||
|| | |||
[http://theory.cs.princeton.edu/complexity/book.pdf Sanjeev Arora and Boaz Barak's Book]: Chapter 9 <br> | |||
[http://www.dcs.ed.ac.uk/home/mrj/ETHbook/chap2.ps Mark Jerrum's lecture notes] | |||
|- | |||
|align="center"| | |||
7:00'''pm''', 2018/5/31<br> 计算机系楼 224 | |||
|align="center"| | |||
刘雅辉 | |||
|| | |||
:Alternating Turing machines. | |||
|| | |||
[http://theory.cs.princeton.edu/complexity/book.pdf Sanjeev Arora and Boaz Barak's Book]: Chapter 5 | |||
|- | |||
|align="center"| | |||
7:00'''pm''', 2018/5/25<br> 计算机系楼 225 | |||
|align="center"| | |||
刘明谋 | |||
|| | |||
:Interactive Proofs (Ⅰ). | |||
|| | |||
[http://theory.cs.princeton.edu/complexity/book.pdf Sanjeev Arora and Boaz Barak's Book]: Chapter 8 | |||
|- | |||
|align="center"| | |||
3:00'''pm''', 2018/4/20<br> 计算机系楼 224 | |||
|align="center"| | |||
刘雅辉 | |||
|| | |||
:Polynomial Hierarchy. | |||
|| | |||
[http://theory.cs.princeton.edu/complexity/book.pdf Sanjeev Arora and Boaz Barak's Book]: Chapter 5 | |||
|- | |||
|align="center"| | |||
3:00'''pm''', 2018/4/12<br> 计算机系楼 229 | |||
|align="center"| | |align="center"| | ||
潘笑吟 | 潘笑吟 | ||
| Line 27: | Line 127: | ||
凤维明 | 凤维明 | ||
|| | || | ||
:Class coNP and Randomized Computation. | :Class coNP and Randomized Computation (Ⅰ). | ||
|| | || | ||
[http://theory.cs.princeton.edu/complexity/book.pdf Sanjeev Arora and Boaz Barak's Book]: Chapter 2, Chapter 7. | [http://theory.cs.princeton.edu/complexity/book.pdf Sanjeev Arora and Boaz Barak's Book]: Chapter 2, Chapter 7. | ||
Latest revision as of 15:12, 6 May 2020
- 这是南京大学理论计算机科学学习小组的主页。
- 本学习小组由学生组织，旨在学习理论计算机科学的基础知识。
- 本学习小组对外开放，欢迎各方向的老师、研究生、以及本科生来参加。
理论计算机科学学习小组
时间地点 Speakers Topics Readings 7:30pm, 2020/5/8
ZOOM
5253336283王天行
- Boolean functions and the Fourier expansion
Analysis Of Boolean Functions: Chapter 1.
7:00pm, 2018/12/14
计算机系楼 224凤维明
- Probability-Generating Function and Galton–Watson Process
7:00pm, 2018/12/11
计算机系楼 224刘明谋
- Lower Bound of Locality-Sensitive Hashing
10:00am, 2018/11/26
计算机系楼 224凤维明
- The Recursion of Counting Monotone CNF Solutions
Approximation via Correlation Decay when Strong Spatial Mixing Fails
7:00pm, 2018/6/29
计算机系楼 224陈海敏
- Randomized Computation (Ⅱ).
Sanjeev Arora and Boaz Barak's Book: Chapter 7.
7:00pm, 2018/6/22
计算机系楼 224樊一麟
- Boolean Circuits.
Sanjeev Arora and Boaz Barak's Book: Chapter 6.
7:00pm, 2018/6/15
计算机系楼 224刘明谋
- Interactive Proofs (Ⅱ).
Sanjeev Arora and Boaz Barak's Book: Chapter 8
7:00pm, 2018/6/7
计算机系楼 224宋仁杰
- Class #P.
Sanjeev Arora and Boaz Barak's Book: Chapter 9
Mark Jerrum's lecture notes7:00pm, 2018/5/31
计算机系楼 224刘雅辉
- Alternating Turing machines.
Sanjeev Arora and Boaz Barak's Book: Chapter 5
7:00pm, 2018/5/25
计算机系楼 225刘明谋
- Interactive Proofs (Ⅰ).
Sanjeev Arora and Boaz Barak's Book: Chapter 8
3:00pm, 2018/4/20
计算机系楼 224刘雅辉
- Polynomial Hierarchy.
Sanjeev Arora and Boaz Barak's Book: Chapter 5
3:00pm, 2018/4/12
计算机系楼 229潘笑吟
- Space Complexity.
Sanjeev Arora and Boaz Barak's Book: Chapter 4
3:00pm, 2018/3/29
计算机系楼 319陈海敏
凤维明- Class coNP and Randomized Computation (Ⅰ).
Sanjeev Arora and Boaz Barak's Book: Chapter 2, Chapter 7.
3:00pm, 2018/3/22
计算机系楼 319凤维明
- Class NP and Reductions.
Sanjeev Arora and Boaz Barak's Book: Chapter 2
3:00pm, 2018/3/15
计算机系楼 319樊一麟
- Turing Machines and Class P.
Sanjeev Arora and Boaz Barak's Book: Chapter 1