Columbia Undergraduate Learning Seminar in Theoretical Computer Science

Spring 2022

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.

Computational Geometry

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

High-Dimensional Probability and Applications to CS

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

Philosophy and Theoretical Computer Science

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

Resource Title Link
MIT Philosophy and TCS Course Philosophy and Theoretical Computer Science Link
Date Topic Speaker Reading
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"

Quantum Computing

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

Previous Semesters

Fall 2021

Summer 2021