The Columbia Undergraduate Learning Seminar in Theoretical Computer Science is a student-run seminar for undergraduates at Columbia interested in theoretical computer science. The goal of the learning seminar is to provide undergraduate students with the opportunity to learn about theoretical computer science in a collaborative, student-driven setting and to meet other students interested in theoretical computer science.
The learning seminar is dedicated to providing an inclusive and welcoming environment for all students interested in theoretical computer science. No background in theoretical computer science is required to participate in the seminar, and everyone is welcome to join!
Each semester, the Columbia Undergraduate Learning Seminar in Theoretical Computer Science will hold one or more seminars on topics related to TCS. The presentations will primarily be given by students, which is a great opportunity to gain experience giving a technical talk in TCS.
The seminar is currently run by Cassandra Marcussen. If you have any questions or would like to join the seminar's Slack channel, please email her here.
Sign up for the mailing list here: Mailing List Sign-Up.
During Spring 2022, we will be holding four groups, each focused on a different topic within TCS. The groups are: Computational Geometry, High-Dimensional Probability and Applications to CS, Philosophy and Theoretical Computer Science, and Quantum Computing. Each group is run by an undergraduate student organizer, and some groups have a graduate student mentor. The groups meet weekly and should be approachable for students of all ranges of prior exposure to TCS.
Please see the descriptions and tables below for a summary and the list of talks for each of the groups.
Organizer: Ari. Graduate Student Mentor: Maryam.
|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.
|HDP||High-Dimensional Probability: An Introduction with Applications in Data Science||Link|
|February 5th||Introduction, Probability Review, and Concentration Inequalities||Cassandra||HDP Ch. 1, Ch. 2 Sections 2.1, 2.2|
|February 12th||Hoeffding's and Chernoff's Inequalities||Chris||HDP Ch. 2 Sections 2.2, 2.3|
|February 23rd||Sub-gaussian Distributions||Cassandra||HDP Ch. 2 Sections 2.5, 2.6|
|March 2nd||Random Vectors: Concentration of the norm, covariance matrices, and principal component analysis||Chris||HDP Ch. 3, Sections 3.1 and 3.2|
|March 23nd||Examples of High-Dimensional Distributions||Cassandra||HDP Ch. 3, Section 3.3|
|March 30th||Grothendiek's inequality and semidefinite programming||Savik||HDP Ch. 3, Section 3.5|
|April 6th||Maximum cut for graphs||Ryan||HDP Ch. 3, Sections 3.6, 3.7|
|April 13th||Introduction to Random Matrices and Randomized Singular Value Decomposition||Chris||HDP Ch. 4, Section 4.1|
|April 20th||Nets, Covering Numbers, Packing Numbers, and Error-Correcting Codes||Cassandra||HDP Ch. 4, Sections 4.2, 4.3|
|April 27th||Final Meeting|
Organizer: Yunya. Graduate Student Mentors: Tim and Samara.
|MIT Philosophy and TCS Course||Philosophy and Theoretical Computer Science||Link|
|February 4th||Analytic Philosophy and TCS||Yunya|
|February 11th||Notions of Computation||Brian Cantwell Smith: The philosophy of computation - meaning, mechanism, mystery|
|February 18th||Mathematical Proof/Definiteness||Adiba||Aaronson "Why philosophers should care about computational complexity" (Section 9), Shieber "The Turing Test as Interactive Proof"|
|February 25th||TCS, Free will, and Determinism||Alex||Aaronson lecture notes, Aaronson blog|
|March 4th||Complexity: NP-completeness||Joe||Aaronson "Why philosophers should care about computational complexity"(Section 4), Aaronson "NP-complete Problems and Physical Reality"|
|March 25th||Complexity: Learning Theory||Richard||Kelly "Learning theory and epistemology"|
|April 1st||Complexity: Kolmogorov Complexity||Anthony||De Wolf "Philosophical Applications of Computational Learning Theory" (Section 3), Schmidhuber "A Computer Scientist’s View of Life, the Universe, and Everything"|
|April 15th||Connectionism and Symbolism||Yicheng||Schneider "The Language of Thought"|
|April 22nd||Evolvability||Yunya||Livnat and Papadimitriou "Sex as an Algorithm: The Theory of Evolution Under the Lens of Computation", Valiant "Evolvability"|
|April 29th||Algorithmic Game Theory||Quintus||Scott Alexander "Meditations On Moloch"|
Description: We explore the potential of circuits and algorithms that take advantage of quantum phenomena such as superpositions, entangled states, and exponential information managed by Nature. Then moving 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).
|O'Donnell||Quantum Computation and Information||Link|
|Yuen||Introduction to Quantum Computing||Link|
|Nielson and Chuang||Quantum Computation and Quantum Information||Textbook|
|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|