(Edit: scribe notes on my lectures on this topic are now up.) Subhash Khot, Dor Minzer and Muli Safra just posted an exciting manuscript online. In it, they confirm the combinatorial hypothesis I've posted about before on the structure of non-expanding set in the degree two short-code graph (or, equivalently, in the Grassman graph).   Together with … Continue reading Unique Games Conjecture – halfway there?

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

(In this post I am following the venerable tradition of bloggers opining about matters on which they don't really know much about. I hope I learn something from the feedback --Boaz). Nothing is impossible, Child, nothing is impossible. Every bridge is crossable. Every tooth is flossable. Every win is lossable. Every worker's bossable. Every cookie's … Continue reading On the (Im)possiblity of intelligence explosion

[Guest post by Robi Krauthgamer;  note that there is no conflict in nominating the same work/person to be highlighted in both HALG and TheoryFest. --Boaz] Call for Nominations  3rd Highlights of Algorithms conference (HALG 2018) Amsterdam, June 4-6, 2018 http://2018.highlightsofalgorithms.org/  The HALG 2018 conference seeks high-quality nominations for invited talks that will highlight recent advances … Continue reading HALG 2018 Call for Nominations

In his State of the Union address in January 1984, president Ronald Reagan announced that he directed his treasury secretary to simplify and reform the U.S., tax code. Thus began a process of 1.5 years until in June 1985, the house Ways and Means committee began formal discussion on the bill, which it voted on … Continue reading The GOP Tax plan and universities

(This blog post is in the form of a Jupyter notebook. See here for an arguably better formatted version, and here for the version with the omitted code, this (Beta version) website allows you to see the code "live" without needing to install Jupyter on your machine.)