Study Group: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>TCSseminar
No edit summary
imported>TCSseminar
 
(19 intermediate revisions by the same user not shown)
Line 3: Line 3:
* 本学习小组对外开放,欢迎各方向的老师、研究生、以及本科生来参加。
* 本学习小组对外开放,欢迎各方向的老师、研究生、以及本科生来参加。


==计算复杂性 computational complexity==
==理论计算机科学学习小组==
   
   
:{|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 11: Line 11:
|bgcolor="#A7C1F2" align="center"|'''Topics'''
|bgcolor="#A7C1F2" align="center"|'''Topics'''
|bgcolor="#A7C1F2" align="center"|'''Readings'''
|bgcolor="#A7C1F2" align="center"|'''Readings'''
|-
|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"|
潘笑吟
||
:Space Complexity.
||
[http://theory.cs.princeton.edu/complexity/book.pdf Sanjeev Arora and Boaz Barak's Book]: Chapter 4
|-
|-
|align="center"|
|align="center"|
Line 18: 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

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 notes

7: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