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:

A seminar, in which students present research ideas, explain their current work, and give practice talks.
A reading group, in which we read papers and learn about areas of TCS as a group.

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

Seminar

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