STOC 2017 is going to be part of an expanded “Theory Festival” which will include not just the paper presentations, but a host of other activities such as plenary talks and tutorials, workshops, and more. One of the components I am most excited about is a sequence of invited plenary short talks where we will … Continue reading Celebrating TCS at STOC 2017

TeX and LaTeX are in many ways, amazing pieces of software. Their contribution to improving and enabling scientific communication cannot be questioned, and I have been a (mostly) grateful user. But sometimes even grateful users have to rant a bit.. My main issue with TeX is that, at its heart, it is a programming language. … Continue reading Why I dislike TeX (a pre-deadline rant)

By Boaz Barak and Omer Reingold President Trump had just signed a new executive order revising the prior ban on visitors from seven (now six) muslim-majority countries. It is fundamentally the same, imposing a blanket 90-day ban on entry of people from six countries, with the conditions for lifting the ban depending on the cooperation of these … Continue reading The immigration ban is still antithetical to scientific progress

By Boaz Barak and Omer Reingold Update (1/28): If you are an academic that opposes this action, please consider signing the following open letter. Today leaked drafts of planned executive actions showed that president Trump apparently intends to issue an order suspending (and possibly permanently banning) entry  to the U.S. of citizens of seven countries:  Iran, … Continue reading Immigration ban is antithetical to scientific progress

Update: I made a bit of a mess in my original description of the technical details, which was based on my faulty memory from Laci's talk a year ago at Harvard. See Laci's and Harald's posts for more technical information.   Laci Babai has posted an update on his graph isomorphism algorithm. While preparing a Bourbaki … Continue reading On exp(exp(sqrt(log n))) algorithms.

Economists generally agree that free trade agreements between countries such as the U.S. and Mexico or China that have complimentary strengths result in a net benefit to both sides. But this doesn't mean that every individual citizen benefits. There are definitely winners and losers, and as we have seen in this election, the losers are … Continue reading Free trade and CS

As also posted by Michael Mitzenmacher, we have several postdoc positions at Harvard,  please apply by December 1st. In particular in 2017-2018, Harvard's center for mathematical sciences and applications will be hosting a special year on combinatorics and complexity,  organized by  Noga Alon, me, Jacob Fox, Madhu Sudan, Salil Vadhan, and Leslie Valiant. I am quite … Continue reading Some announcements

Now that the important event of the STOC deadline has passed, we can talk about trivial matters such as the future of the free world (but of course, like a broken record, I will come back to talking about sum of squares by the end of the post). A priori predicting the result of the … Continue reading Post-deadline diversion: Election predictions

As mentioned before on this blog,   STOC 2017 will be part of an expanded “Theory Fest” (http://acm-stoc.org/stoc2017/) which is being planned by a small committee (Sanjeev Arora, Paul Beame, Avrim Blum, and Ryan Williams, as well as SIGACT chair Michael Mitzenmacher and STOC’17 PC chair Valerie King).   One component of Theory Fest would be a series of … Continue reading Theory Fest short presentations – call for suggestions