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 |