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

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 |