During Spring 2022, we held four groups, each focused on a different topic within TCS. The groups were: Computational Geometry, High-Dimensional Probability and Applications to CS, Philosophy and Theoretical Computer Science, and Quantum Computing. Each group was run by an undergraduate student organizer, and some groups had a graduate student mentor.

Please see the descriptions and tables below for a summary and the list of talks for each of the groups.

This was the third iteration of the TCS seminar. The seminar was run by Cassandra Marcussen.

Organizer: Ari. Graduate Student Mentor: Maryam.

Date | Topic | Speaker |
---|---|---|

February 15th | Introduction | Ari |

February 22nd | Plane Embeddings | Jeffrey |

March 1st | Packing & Covering | |

March 22nd | Polytopes, Part 1 | Jet and Carlos |

March 29th | Polytopes, Part 2 | Jet and Carlos |

April 5th | Convex Hulls | Casey |

April 12th | Delaunay Triangulations, Part 1 | Ashwin and Walt |

April 19th | Delaunay Triangulations, Part 2 | Ashwin and Walt |

Organizer: Cassandra. Graduate Student Mentor: Shivam.

Resource | Title | Link |
---|---|---|

Vershynin | High-Dimensional Probability: An Introduction with Applications in Data Science | Link |

Date | Topic | Speaker | Reading |
---|---|---|---|

February 5th | Introduction, Probability Review, and Concentration Inequalities | Cassandra | Vershynin Chap. 1, Chap. 2 Sections 2.1, 2.2 |

February 12th | Hoeffding's and Chernoff's Inequalities | Chris | Vershynin Chap. 2 Sections 2.2, 2.3 |

February 23rd | Sub-gaussian Distributions | Cassandra | Vershynin Chap. 2 Sections 2.5, 2.6 |

March 2nd | Random Vectors: Concentration of the norm, covariance matrices, and principal component analysis | Chris | Vershynin Chap. 3, Sections 3.1 and 3.2 |

March 23nd | Examples of High-Dimensional Distributions | Cassandra | Vershynin Chap. 3, Section 3.3 |

March 30th | Grothendiek's inequality and semidefinite programming | Savik | Vershynin Chap. 3, Section 3.5 |

April 6th | Maximum cut for graphs | Ryan | Vershynin Chap. 3, Sections 3.6, 3.7 |

April 13th | Introduction to Random Matrices and Randomized Singular Value Decomposition | Chris | Vershynin Chap. 4, Section 4.1 |

April 20th | Nets, Covering Numbers, Packing Numbers, and Error-Correcting Codes | Cassandra | Vershynin Chap. 4, Sections 4.2, 4.3 |

April 27th | Final Meeting |

Organizer: Yunya. Graduate Student Mentors: Tim and Samara.

Resource | Title | Link |
---|---|---|

MIT Philosophy and TCS Course | Philosophy and Theoretical Computer Science | Link |

Organizer: Alex.

**Description:** We explored the potential of circuits and algorithms that take advantage of quantum phenomena such as superpositions, entangled states, and exponential information managed by Nature. Then, we moved onto high-level algorithms, the quantum query model, and applications of the Quantum Fourier Transform (like Shor's algorithm which lets us factor large primes efficiently).

Resource | Title | Link |
---|---|---|

O'Donnell | Quantum Computation and Information | Link |

Yuen | Introduction to Quantum Computing | Link |

Nielson and Chuang | Quantum Computation and Quantum Information | Textbook |

Date | Topic | Speaker | Reading |
---|---|---|---|

February 6th | Classical Boolean Circuits to Quantum Circuits | Alex | O'Donnell 1 |

February 13th | Math of Quantum States and Quantum Computation | Christine | O'Donnell 2. Supplemental Readings: Nielson and Chuang 1.2-1.3.4, Prof. Yuen's Worksheet 1 and 2 |

February 20th | No-Cloning Theorem, Quantum Teleportation, CSHS Game | Tony | O'Donnell 3 |

February 27th | Oracles and Grover's Algorithm | Phil | O'Donnell 4 |

March 25th | The Quantum Query Model, Deutsch-Josza, Starting Simon's Problem | Alex | O'Donnell 5, Section 5.2 of Yuen 3 |

April 1st | Simon's Problem cont. | Christine | Yuen 4, O'Donnell 6 |