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, Iraq, Libya, Somalia, Sudan, Syria, and Yemen. As Scott Aaronson points out, one consequence of this is that students from these countries would not be able to study or do research in U.S. universities.

The U.S. has mostly known to separate its treatment of foreign governments from its treatment of their citizens, whether it is Cubans, Russians, or other cases. Based on the past records, the danger of terrorism by lawful visitors to the U.S. from the seven countries above is slim to none. But over the years, visitors and immigrants from these countries did contribute immensely to the U.S. society, economy, and the scientific world at large.

We personally have collaborated and built on the scientific works of colleagues from these countries. In particular, both of us are originally from Israel, but have collaborated with scientists from Iran who knew that the issues between the two governments should not stop scientific cooperation.

This new proposed policy is not just misguided, but also directly contradicts the interests of the U.S., and the advancement of science. We call on all our fellow scientists to express their strong  disagreement with it, and their solidarity and gratitude for the contributions of visiting and immigrant scientists, without which the U.S., and the state of human knowledge, would not have been the same.

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 talk on the work Harald Helfgott found an error in the original running time analysis of one of the subroutines. Laci fixed the error but with running time that is quantitatively weaker than originally stated, namely  $\exp(\exp(\sqrt{\log n}))$  time (hiding poly log log factors). Harald has verified that the modified version is correct.

This is a large quantitative difference, but I think makes very little actual difference for the (great) significance of this paper. It is tempting to judge theoretical computer science papers by the “headline result”, and hence be more impressed with an algorithm that improves $2^n$  time to $n^3$ than, say, $n^3$ to $n^{2.9}$. However, this is almost always the wrong metric to use.

Improving quantitative parameters such as running time or approximation factor is very useful as intermediate challenge problems that force us to create new ideas, but ultimately the important contribution of a theoretical work is the ideas it introduces and not the actual numbers. In the context of algorithmic result, for me the best way to understand what a bound such as $\exp(\exp(\sqrt{\log n}))$ says about the inherent complexity of the problem is whether you meet it “on the way up” or “on the way down”.

Often, if you have a hardness result that (for example based on the exponential time hypothesis) shows that some problem (e.g., shortest codeword) cannot be solved faster than  $\exp(\exp(\sqrt{\log n}))$  then you could expect that eventually this hardness would improve further and the true complexity of the problem is $\exp(n^c)$ for some $c>0$ (maybe even $c=1$). That is, when you meet such a bound “on your way up”, it sometimes makes sense to treat $\exp(\sqrt{\log n})$ as a function that is “almost polynomial”.

On the other hand, if you meet this bound “on your way down” in an algorithmic result, such as in this case, or in cases where for example you improve an $n^2$ algorithm to an $n\exp(\sqrt{\log n})$ then one expects further improvements and so in that context it sometimes makes sense to treat $\exp(\sqrt{\log n})$ as “almost polylogarithmic”.

Of course it could be that for some problems this kind of bound is actually their inherent complexity and not simply the temporary state of our knowledge. Understanding whether and how “unnatural” complexity bounds can arise for natural problems is a very interesting problem in its own right.

I’m happy to invite (in the name of the Stanford theory group) applications for the inaugural Motwani Postdoctoral Fellowship in Theoretical Computer Science, made possible by a gift from the Motwani-Jadeja foundation. Please see application instructions . Please apply by Jan 6, 2017 for full consideration.

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 anything but “happy campers”.

NAFTA’s effect on U.S. employment  has probably been something between a modest gain to a loss of several hundred thousand U.S. jobs. The effect of trade with China has probably been greater, resulting in a loss of perhaps a million or more jobs. But both of these effects  are likely to be much smaller than the result of the U.S.’s completely unregulated trade with a different country, one that has no labor protections and whose workers work very long hours for very low wages.

I am talking about the “Nation of AI”. According to the Bureau  of Labor and Statistics,  in the U.S. there are 3.85 million drivers (of trucks, buses, taxis, etc..), 3.5 million cashiers, 2.6 million customer service representatives, and many other people working in jobs that could be automated in the near future. It is sometimes said that “routine” jobs are the ones most at risk, but perhaps a better term for this is quantifiable jobs. If your job consists of performing well-defined tasks that have a clear criteria of success (like “getting from point A to point B”) then it is at risk of first being “Uberized” (or “M-Turk’ed”)  and then automated. After all, optimizing well defined objectives is what computers do best.

Of course, like other trade deals and technological advances in the past, it could well be that the the eventual net effect of artificial intelligence on human employment is zero or even positive. But it will undoubtedly involve shifting of jobs, and, especially if it happens on a short time scale, many people whose jobs are eliminated would be unable to acquire the skills for obtaining the jobs that are created.

Understanding how to deal with this (arguably more realistic) type of “AI risk” is a grand challenge on the interface of Economics and Computer Science, as well as many other areas. Like other questions of incentives, privacy, fairness, and others, I believe theoretical computer science can and should play some role in addressing this challenge.

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 excited about the workshops and events we have planned, so it should be a great time to be in the area.

The two sister sum-of-squares seminars at Cambridge and Princeton have  been maintaining a fairly extensive set of online lecture notes (with links to videos of Cambridge lectures added as we go along). While these notes are still a work in progress, I am already quite happy  with how they turned out (but would be grateful for any feedback to help make them more accessible).

As I mentioned before, if you want to see the live version, David Steurer and I are going to teach a Sum of Squares Winter Course in UC San Diego in January 4-7, 2017. Should be fun!!

Finally, please send in your suggestions for papers to invite for Theory Fest presentations by December 12, 2016. I’ve been having some issues with the dedicated email I setup for this, so if you sent in a suggestion and didn’t get a response, please send me a copy at my personal email as well.

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 election seems like an unglamorous  and straighforward exercise: you ask $n$ people for their opinions $x_1,\ldots,x_n$ whether they prefer candidate $0$ or candidate $1$, and you predict that the result will be the majority opinion, with probability that is about  $1-\exp(-|\sum x_i - n/2|^2/n)$. This means that if two candidates are at least 2 percent apart, then you should get extremely high confidence if you ask some constant factor times 2,500 people.

Yet somehow, different analysts looking at the polls come up with very different numbers for the probability that Trump will win. As of today 538 says it is 34.2%, NY-times’ Upshot says it is 14%, David Rotchschild’s predictwise says it is 16%,  and Sam Wang’s PEC says it is 2%.

There are several reasons for this discrepancy, including the fact that the U.S. election is not won based on popular vote (though they almost always agree), that we need to estimate the fraction among actual voters as opposed to the general population, that polls could have systematic errors, and of course there is genuine uncertainty in the sense that some people might change their minds.

But at least one of the reasons seems to come up from a problem that TCS folks are familiar with, and arises in the context of rounding algorithms for convex optimization, which is to understand higher level correlations. For example, essentially all these predictors think that there  are a few states such Florida, New Hampshire, Nevada, and North Carolina that have reasonable chance of going either way, but that Trump cannot afford to lose even one of them.  Clearly these are not perfectly independent nor perfectly correlated events, but understanding the correlations between them seems hard, and appears to account for much of the huge discrepancy between the topline predictions.

Even if you do understand the correlations, using them to come up with predictions can be a computationally hard task. The typical way these people do it is to come up with an efficiently samplable distribution that matches the given marginals and correlations, and then run many simulations on this distribution to predict the outcome.

But coming up with efficiently sampleable distributions that match even simple pairwise or three-wise correlations is a computationally hard task.  (For constrained pairwise moments this is related to MAX-CUT while for unconstrained higher moments this is related to SAT, it is possible to do this for unconstrained pairwise moments using the quadratic sampling lemma, also known as Gaussian copula, which is related to the hyperplane rounding technique of Geomans and Williamson.) For an empirical demonstration, see this blog post of David Rothschild for how it is problematic to find a distribution that matches both the statewise and topline marginals of prediction markets (despite a fact that such a distribution should exist under the efficient market hypothesis). The fact that the matching moments problem is hard in general means that people use different heuristics to achieve this, and I don’t know if they have a good understanding of how the choice of heuristic affects the quality of prediction.

In our sum of squares lecture notes we discuss (with a javascript-powered  figure!) this issue with respect to the clique problem. Given a graph $G$ with a hidden $k$ clique $S$,  if we are computationally bounded and want to make predictions on events such as $A \subseteq S$ we cannot find an efficiently sampleable distribution over sets $S'$ that would not make non-sensical predictions such as $\Pr[ |S| \neq k ] < 1$ or $\Pr [ \{ i,j \} \subseteq S ] >0$ for some non neighbors $i,j$. The sos algorithm (and other convex optimization frameworks) can be thought of as a way to come up with predictions without a matching efficiently sampleable distribution, by generalizing to the notion of pseudo-distribution.

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 presentations to highlight some of the best theoretical work in the past two years from other conferences or journals. (A non-exhaustive list of sample venues is ICALP,SODA, CRYPTO, LICS, PODS, PODC, QIP, SPAA, KDD, CCC, SIGMETRICS, Transaction on IT, WWW, ICML/NIPS , Science/Nature, etc..) Invited papers from these venues  will be presented in short (20-30 minute) plenary presentations at Theory Fest.

We (the sub-committee in charge of this component) seek suggestions of theoretical papers that have made breakthrough advances, opened up new questions or areas, made unexpected connections, or had significant impact on practice or other sciences. Anyone is welcome to contact us, but we especially invite members of PCs or editorial boards in various venues to send us suggestions.

If you can think of any recent result that satisfies these criteria, or have any related questions, please email stoc17presentations@boazbarak.org (please CC my personal email as well). Suggestions for presentations should include the following information:

1. Name of the paper and authors.
2. Publication venue (conference / journal), with publication date no earlier than January 1 2015.
3. Short (1-3 paragraph) explanation of the paper and its importance.
4. (Optional) Names of 1-3 knowledgeable experts on the area of this paper.

To ensure maximum consideration, please send us all these suggestions by December 12,  2016. Self-nominations are discouraged.

Thank you,

Theory Fest 2017 short plenaries committee:

Dorit Aharonov (Hebrew University)
Boaz Barak (Harvard University, committee chair)
Paul Beame (University of Washington)
Kamalika Chaudhuri (UC San Diego)
Ronald Fagin (IBM Research – Almaden)
Piotr Indyk (MIT)
Friedhelm Meyer auf der Heide (University of Paderborn)
Eva Tardos (Cornell)
Suresh Venkatasubramanian (University of Utah)