Skip to content

Doing Theoretical Physics with Semidefinite Programming

October 21, 2017

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.


Do we have TCS “Harvey Weinsteins”?

October 19, 2017

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.



October 16, 2017

The call for paper for STOC is up, see 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.

Michael Cohen

September 27, 2017

[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.

Special year on combinatorics and complexity

September 8, 2017

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:

Our Friday theory reading group will move to the CMSA center and feature many speakers from the special year.

In addition, the program will feature a series of public lectures by Noga Alon (Sept. 7), Jennifer Chayes (Nov. 2), Jacob Fox (Feb. 1), and Dan Spielman (March 20).

Combinatorics will also be featured in this year’s Ahlfors Lecture Series, given by Timothy Gowers (University of Cambridge) on October 11-12. Leslie Valiant will give the Ding Shum lecture on October 10.

Harvard will also host the Women In Theory workshop in the summer of 2018 (details forthcoming),

Participation: Researchers interested in participating in the special year through a short- or long-term visit to CMSA are encouraged to contact the organizers through the CMSA Administrative Coordinator, Sarah LaBauve (  Each of the workshops is also open to participation by all interested researchers subject to capacity. Registration forms can be found on the webpages for the individual workshops. 


Men in Computer Science

August 16, 2017

There have been some discussions lately on gender ratios and equality in Computer Science. In this post I don’t want to rehash the scientific studies, but just talk about my own experience as a man in the field of theoretical computer science, ever since I started graduate school nearly 20 years ago. I don’t presume to talk for all males, but I don’t think my story is completely non-representative. This is also a good opportunity to recommend that people read the research life stories series that Omer Reingold initiated on this blog, as well as the Turing centennial series on Luca Trevisan’s blog.


Like many other new grad students, when I just started at the Weizmann Institute of Science, I was extremely anxious. While I loved (the little I knew about) theory, I was not sure if I’m smart enough to do original research in this area. The professors seemed like beings from another world, but one thing that helped was that at least I did share some background with them. Almost all of them were males (and in fact, this being Israel, almost all were, like me, Ashkenazi secular jews). So, it was not completely unthinkable to imagine that I would some day be like them.


Another thing that helped me a lot in my early time in Weizmann was my study group.
I quickly found three friends, all male, and we spent many hours together studying for exams, talking about research, but also playing video games.


As I progressed in the field, I’ve had a great many research interactions and collaborations. I’ve met people at all hours and various locations, including coffee shops, restaurants, and private homes. I’ve never had to worry about the potential for sexual harassment, nor that I would be judged by my looks or what I wear. I am the type of person that speaks their opinion loudly, perhaps sometimes a little too loudly. In my experience, women that act the same are judged by a different standard and often “rub people the wrong way” and get tagged as having problematic personalities. Also, I was never afraid to ask potentially stupid questions. I did not need to fear that asking such a question would confirm people’s bias about me that I don’t belong in this field. Asking potentially stupid questions is one of the most useful ways to learn and evolve as a scientist.


Last but not least, I would most definitely not be where I am if my wife did not quit her job in Israel to move with me across the Atlantic for my postdoc. Also, while I think of myself as an involved father, I have to admit that Ravit still does more of the childcare duties. (As I’m reading this out loud, my daughter is commenting that I am not such an involved father…) Again, I am not saying that all male scientists are like me, nor that there are no female scientists that greatly rely on the support of their partners, but I don’t think my situation is atypical.


On more general terms, one misconception I see about science in such discussions is that it is about “things” or “facts” and not people, and hence perhaps should be free of biases.
But in fact science is an extremely social enterprise. Since graduating, I have never written a solo paper. Much of my work is spent talking to people in front of a whiteboard or notepad, and I’ve learned a great deal from discussions with fellow scientists. This also explains why certain subfields of science can have outlying gender or ethnicities ratios. People just feel more comfortable working with others similar to them, and role models greatly influence the fields students choose to pursue. For example, there is nothing innately Hungarian about combinatorics. Similarly, there is nothing innately feminine about cryptography, but rather a few extremely strong female scientists have had a huge effect. The influence of people such as Shafi Goldwasser, Tal Rabin, and others has not been limited just to their (amazing) research results but also as role models and mentors to many female cryptographers (and many male cryptographers as well, myself included).


I don’t like the expression “leveling the playing field” because Science is not a game. This is not about competing but about collaborating with each other to uncover the mysteries of the universe. But us males (especially those that, like me, come from amply represented ethnicities), should be aware and grateful for the advantages we’ve had in our careers. We should not try to remove these advantages: access to role models, freedom from bias, ease of networking, are all good things. We should however strive for a world where everyone enjoys the same benefits. In such a world we’ll have more scientists that are more productive and happier, and that will only be better for science.

FOCS 2017: Registration and call for workshops

August 14, 2017

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

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

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.