Windows On Theory

I just came back from the Simons Foudnations annual meeting for Mathematical and Physical Sciences. Unfortunately, due to a flight delay I missed many of the talks, but the ones I did see were fascinating.

One talk in particular caught my attention: Leonardo Rastelli‘s talk on “The Superconformal Bootstrap” who discussed the work of the Simons Bootstrap collaboration. I didn’t understand much of the talk (in fact, probably less than 10 percent) but the high level tidbits I got seemed fascinating, and so am posting here some of my understanding. Most, if not all, of what is written below is probably false or inaccurate, but I hope other people that understand this more will correct me.

So, it seems one way to think of a physical theory is as being a way to predict some observables. More formally, a theory maps a point in spacetime to the observable values. In fact apparently the right way to think about this map is to map a tuple of points to the correlation between these observables, something that is known as a “correlation function”.

The traditional view is that these observables arise out of some local interactions between particles. In a computer science way, we could think of modelling spacetime by a graph G such as the d-dimensional lattice. The state of the system corresponds to some assignment of values to the vertices of G, and there is some function that maps each state to its “energy” by summing up   over the local interactions. Then the probability of obtaining a particular assignment is weighed by something exponentially small in its energy, and the predictions are obtained by sampling (or computing analytically) this distribution. Unfortunately, it seems (if I understand correctly) that there are some theories for which the physicists don’t know of (and even strongly suspect that there exists no) such local “Lagrangian” explanation for the theory. Moreover (as we can all relate to), even when such an explanation exists, computing the global predictions from the local information could be very hard.

Apparently however, if one posits certain symmetries on the theory, and particular conformal symmetry (which I believe means that the theory be scale free – the predictions are the same if we focus on a small region of space time as it would be in a large one, and is also invariant under rotations), then there are some global constraints on the form of these theories. However, figuring out what these constraints mean is not so simple, and I guess many physicists thought that even after doing all this work, probably they would not be able to derive much from these seemingly few global constraints.

However, it turns out that they can use semidefinite programming to calculate constraints on the allowed theories in “theoryspace” and in fact, using these semidefinite programs alone it might be possible to completely determine some properties of physical theories from first principles. This is not  about using optimization to analyze data in applied physics but rather doing pure theoretical physics via semidefinite programming. (In fact, if I understand correctly, these conformal theories are about idealized universes which do not precisely match our own.)

This reminds me of course of Razborov’s Flag Algebra work of using semidefinite programming to derive inequalities in combinatorics. In fact, at least to me, some of the notation used in both cases look quite similar (one of the figures below is from a talk by Lovász on flag algebras, the other is from the Simons collaboration on the superconformal bootstrap)

One can almost imagine an updated version of David Hilbert’s famous quote

We hear within us the perpetual call: There is the problem. Seek its solution. You can find it by semidefinite programming, for in mathematics there is no ignorabimus.

p.s.  Scott Aaronson invokes a roughly contemporaneous quote of Roosevelt in discounting critics. While I agree with both of Scott’s sentiment and the examples he mentions (except perhaps that the particular “critics” he talks about are best left alone in the dark corners of the Internet), I can’t help but thinking that he is being a little hypocritical. After all, Scott himself keeps criticizing one person who constantly strives valiantly for the American people. A person that, unlike some of his critics, was never captured by the enemy, but overcame debilitating foot spurs to achieve great skill in golf, only to make the ultimate sacrifice and restrict his playing to the weekends for the good of the nation. A person who unites Americans of all stripes, from white nationalists to businessmen who want their taxes cut.  Perhaps Scott can take some of his own medicine, and learn to appreciate greatness (and bigness) rather than criticize it.

Following the Harvey Weinstein scandal, I’d like to believe that the academic environment at large, and theoretical computer science in particular, is a much better environment than Hollywood. But we would be misleading ourselves to think that we are completely without our issues. This story can be an opportunity for each of us, men and women, to think what can we do to eradicate such behavior from our field. I don’t have any easy answers, but all of us, especially senior men in positions of influence, should try to do what we can and not look the other way. There is not much that can be more damaging for a person coming up in a field than somebody abusing and objectifying them rather than treating them as a colleague and an intellectual.

This is not exactly related, but what prompted me to write this post was hearing from a  friend (who is a non CS faculty in another part of the U.S.) whose children were kicked out from a private (non religious) school when the principal learned they come from an LGBT family. I was truly shocked that something like that can happen in a fairly large U.S. city. It got me thinking (again) of how easy it is to believe that such issues are a thing of the past, or happen in only the remotest parts of the world or the country, when you are not part of the affected population.

The call for paper for STOC is up, see  http://acm-stoc.org/stoc2018/ and  here. The deadline is November 3, 2017 4:59pm Eastern Daylight Time.

STOC 2018 will again be a Theory Fest and also celebrate the 50th anniversary of STOC. As part of the “retro” atmosphere, the STOC PC also asks submissions to be sent by mail in 20 printed copies at most 10 pages.

[This is a guest blog post on behalf of MSR, communicated to me by Yuval Peres. Like everyone who knew Michael, I was incredibly shocked and saddened by the news. I had relatively few interactions with Michael, but he has made a deep impression. I was always hoping we’d get a chance to collaborate , as it was clear to me that he’s exceptionally talented and creative.  If you’ve known Michael, feel free to share your perspective in the comments. -Boaz]

The Microsoft Research family is shocked and deeply saddened by the tragic loss of our colleague and friend Michael Cohen.  Michael was a brilliant mathematician and a rising star in his field.  He spent this past summer with us as a Microsoft Research Fellow, doing what he loved most. Over the summer, he made sweeping progress in online learning and online algorithms, two fields he had just recently become acquainted with. In addition to solving five open problems in these areas, he continued his substantial progress on the k-server problem, one of the most celebrated and notoriously difficult challenges in the space of adaptive algorithms.

Michael was a truly exceptional individual.  We will remember Michael for his infectious smile and his larger-than-life personality. We will never forget his unrelenting curiosity, his thirst for knowledge, and his deep love for mathematics and theoretical foundations of computing.  We are stunned by his loss.  We will hold onto our memories of Michael, and know that his ideas and scientific accomplishments will continue on as important advances.

We extend our most sincere condolences to Michael’s family and friends.

This year Harvard’s Center for Mathematical Sciences and Applications is running a special year on combinatorics and complexity. We have many long-term visitors and postdocs, and several events that theoretical computer scientists might wish to take part in, including four workshops:

Fall is coming, and with it the annual holiday of FOCS. FOCS 2017 will be held at Berkeley from Oct 15-17, with a day of workshops/tutorials on Oct 14th. Registrations are now open at http://focs17.simons.berkeley.edu/registration.html

Early registration deadline for the conference is Sept 25th, 2017.

Speaking of workshops, there is one way to guarantee that FOCS has a workshop in an area you care about, and it is to organize such a workshop yourself!

Speaking from experience, organizing a workshop is non-zero but not unmanageable amount of work. It is a great way to connect with colleagues in your area, as well as expose some other people in the TCS community to it. The call for workshops is now up at http://focs17.simons.berkeley.edu/workshopAndTutorial.html

A proposal for a workshop can be quite minimal – the main thing you need is the names of the organizers and speakers. To submit a proposal, send an email to Aleskander Mądry and James Lee by September 3, 2017.