This fall I taught CS 121 - "Introduction to Theoretical Computer Science" - at Harvard. This is analogous to courses known at other universities as "Introduction to the Theory of Computation", "Automata and Computability", or "Great Ideas in Theoretical Computer Science", and are often taught using Sipser's excellent book. However, I decided to significantly revise it … Continue reading Intro TCS course post-mortem

The deadline to register to the Women In Theory workshop is January 16, 2018.  As Omer Reingold posted, this is a wonderful workshop with a strong set of speakers (confirmed speakers include  Bonnie Berger, Yael Kalai, Julia Kempe,  Gillat Kol, Nancy Lynch, and Barna Saha). It is sure to have a great technical content, as well … Continue reading Women In Theory – registration deadline getting closer

Message from Costis, Yael, and Vinod: ITCS is back in the east coast, and will be at MIT from January 11-14, 2018. As you know, ITCS is a conference that is unique in many respects: it's a conference that emphasizes dialog and discussion among all sub-areas of TCS, facilitating it with a single track structure and "chair … Continue reading ITCS early registration deadline

(I'm a non native speaker - is it Hopkins' or Hopkins's? --Boaz) Sam Hopkins just completed a heroic 6 part blog post sequence on using the Sum of Squares algorithm for  unsupervised learning. The goal of unsupervised learning is to recover the underlying structure of a distribution $latex \mathcal{D}$ given samples $latex X_1,\ldots,X_n$ sampled from … Continue reading Sam Hopkins’s 6 part learning via SoS series

This is the 6th and final part of a series on clustering, Gaussian mixtures, and Sum of Squares (SoS) proofs. If you have not read them yet, I recommend starting with Part 1, Part 2, Part 3, Part 4, and Part 5. Also, if you find errors please mention them in the comments (or otherwise … Continue reading Clustering and Sum of Squares Proofs, Part 6

This is part 5 of a continuing series on clustering, Gaussian mixtures, and Sum of Squares (SoS) proofs. If you have not read them yet, I recommend starting with Part 1, Part 2, Part 3, and Part 4. Also, if you find errors please mention them in the comments (or otherwise get in touch with … Continue reading Clustering and Sum of Squares Proofs, Part 5

This is part 4 of a continuing series on clustering, Gaussian mixtures, and Sum of Squares (SoS) proofs. If you have not read them yet, I recommend starting with Part 1, Part 2, and Part 3. Also, if you find errors please mention them in the comments (or otherwise get in touch with me) and … Continue reading Clustering and Sum of Squares Proofs, Part 4

This is part 3 of a continuing series on clustering, Gaussian mixtures, and Sum of Squares (SoS) proofs. If you have not read them yet, I recommend starting with Part 1 and Part 2. Also, if you find errors please mention them in the comments (or otherwise get in touch with me) and I will … Continue reading Clustering and Sum of Squares Proofs, Part 3

This is part 2 of a series on clustering, Gaussian mixtures, and Sum of Squares (SoS) proofs. If you have not read it yet, I recommend starting with Part 1. Also, if you find errors please mention them in the comments (or otherwise get in touch with me) and I will fix them ASAP. Welcome … Continue reading Clustering and Sum of Squares Proofs, Part 2

Update (1/5/18): a pdf containing all six posts in this series is now available on my website. I am excited to (temporarily) join the Windows on Theory family as a guest blogger! This is the first post in a series which will appear on Windows on Theory in the coming weeks. The aim is to … Continue reading Clustering and Sum of Squares Proofs, Part 1