Columbia CS Theory Student Seminar

Starting fall 2019, this group is a setting for Columbia PhD students and postdocs in the CS Theory group to learn from each other by presenting papers, sharing research problems, and studying CS topics together. This is technically a combination of two events which occur on alternate weeks:

We meet at 5pm in CSB 488 and communicate primarily on the theory-student-seminar channel of the Columbia CS PhD Students Slack. Please contact Clayton if you have any questions about the seminar. We have food!

Spring 2020

Reading Group: Pseudorandomness

We're covering topics in pseudorandomess. We draw heavily from Salil Vadhan's book and Eshan Chattopadhyay's course.

Date Topic/Reading Material Presenter Notes
February 6, 2020 Intro to Pseudorandomness Sandip Sinha
February 20, 2020 Expanders and Spectral Graph Theory Dan Mitropolski
March 12, 2020 TBD Kiran Vodrahalli
April 2, 2020 TBD Clayton Sanford
April 16, 2020 TBD Victor Lecomte
April 30, 2020 TBD TBD


Date Topic Presenter Notes
January 30, 2020 Dynamic Optimality and Binary Search Trees, Part I Victor Lecomte
February 13, 2020 Dynamic Optimality and Binary Search Trees, Part II Victor Lecomte
February 27, 2020 Local Decodability of the Burrows-Wheeler Transform Sandip Sinha
March 5, 2020 Lightning Talks and Q&A for New Student Visit Day TBD Abnormal Date and Time; 11:30am - 12:30pm
March 26, 2020 TBD Arnold Filtser
April 9, 2020 TBD TBD
April 23, 2020 TBD TBD

Fall 2019

Reading Group: The Classics

For the first semester of the seminar, we read classical papers from various subfields of Theoretical Computer Science.

Date Reading Material Presenter Notes
September 19, 2019 Alan Turing: Computing Machinery and Intelligence (1950) Victor Lecomte
October 10, 2019 Claude Shannon: A Mathematical Theory of Communication (1947) Shunhua Jiang
October 24, 2019 Leslie Valiant: The complexity of computing the permanent (1979) Binghui Peng
November 7, 2019 N. Karmarkar: A new polynomial-time algorithm for linear programming (1984) Sandip Sinha
November 21, 2019 Christos Papadimitriou: Games against nature (1985) Kiran Vodrahalli
December 5, 2019 Goldreich, Goldwasser, Micali: How to Construct Random Functions (1986) Chengyu Lin