We had last week the "Women In Theory" workshop at Harvard. Thanks to the efforts of the organizers  Tal Rabin, Shubhangi Saraf, and Lisa Zhang, as well as the hard work of our staff at Harvard, it was (in my opinion) a huge success. But there is still so much more to be done. A … Continue reading Women in theory (and CS in general)

It's that time of the year again, where you can see TheoryFest decorations in every home,  and TheoryFest music is playing in shops and on the radio. For those making the pilgrimage to Los Angeles, I hope to see you there. There are many great papers, workshops, and other content in the program, but I … Continue reading Celebrating TheoryFest

By Boaz Barak and Jarosław Błasiok [Jarek gave a great informal exposition of this paper on Friday, and I asked him to make it into a blog post. My only knowledge of the paper is from Jarek's explanations: my main contribution to this post was to delete some details and insert some inaccuracies --Boaz.]   A … Continue reading On the Raz-Tal oracle separation of BQP and PH

A couple of years ago I posted about Theory Life Hacks. "Life" might be a bit too grand, but what I really mean are technological tools that can help in the day to day work. In the last two years, perhaps because of taking more responsibilities, I found myself using more technology and so I … Continue reading Theory Life-Hacks II

This spring I taught Cryptography at Harvard (as usual my lecture notes are online ). Teaching it was a great fun because of the fantastic group of students that took the course.  They were genuinely interested in cryptography, and kept asking me extremely interesting questions and had excellent insights. Thanks also to Yael Kalai and … Continue reading Cryptography course projects

As I mentioned before, I am teaching CS 121  at Harvard, and have written my own text, with the (not very original) title "Introduction to Theoretical Computer Science" . I am hoping for this text to turn into a published textbook in the next year or two. Toward this end, I would be grateful for any comments … Continue reading Call for comments: “Introduction to Theoretical Computer Science”

There is an old joke that an economist would not lift a $100 bill lying on the sidewalk, since in equilibrium it should not be there. But economist Bryan Caplan from George Mason University believes the world is leaving trillion dollars or so on the sidewalk. The culprit in his mind is education, which developed … Continue reading Short non-review of Caplan’s “Case Against Education”

Quanta magazine has an excellent article by Erica Klarreich on the recent progress on the 2 to 2 conjecture, which I have blogged about before.  The article does not go into the technical details, but gives a good perspective on what's been done and what are the challenges ahead. Eric Posner and Glen Weyl have a … Continue reading Some reading recommendations

(Announcement from Ilias Diakonikolas and David Kempe) We are pleased to announce that we will provide pooled, subsidized child care at STOC 2018. The cost will be $40 per day per child for regular conference attendees, and $20 per day per child for students. For more detailed information, including how to register for STOC 2018 childcare, … Continue reading Childcare at STOC 2018 “TheoryFest”

Mitali Bafna, Chi-Ning Chou, and Zhao Song wrote scribe notes for my lectures on the Dinur et al proof of the 2 to 2 conjecture (see the DKKMS  and KMS papers, though this presentation follows a different, and in my view simpler, approach.) "Scribe notes" is really an understatement. In a heroic work, Mitali, Chi-Ning and Zhao … Continue reading Lecture notes on DKKMS