# Congratulations

I was really delighted with all the prizes that were announced at STOC this year.

Our own Pasin Manurangsi received the Danny Lewin STOC Student Paper Award for his work on the hardness of the dense k-subgraph problem. This is the problem in which we are given a graph and a number k, and we want to find the set of k vertices that induces the most edges. Pasin, who is co-advised by Prasad Raghavendra and me, discovered a new, simple but ingenious reduction that establishes hardness up to almost polynomial factors.

I received the same award exactly twenty years ago, also for a hardness-of-approximation result established via a simple reduction. (Prasad also received it, nine years ago, for a hardness-of-approximation result established via a difficult reduction.) I then spent time at MIT, where Oded Goldreich was, and, partly thanks to his influence, I did my best work there. Pasin is spending this summer at Weizmann, where Oded Goldreich is, so, no pressure, but let’s see what happens. . .

Alistair Sinclair received the ACM SIGACT Distinguished Service prize, for his work setting up and leading the Simons Institute for the Theory of Computing.

Those who have been to the institute, that is, almost the whole theoretical computer science community, have seen that it is a place uniquely conducive to do good work. If you stop at think about what it is that makes it so, Alistair’s hand is behind it. The open layout of the second floor, with the whiteboards dividing the space and absorbing sound? Alistair worked closely with the architect, for a year, during the renovation, to make sure that the design would best fit the needs of our community. The friendly, competent and responsive staff? Alistair sat in all the interviews when the staff was recruited, and participates in their performance review. So many things happening and never a conflict? You know whom to thank.

More substantially, almost all the programs that we have had were, to some extent, solicited, and Alistair led the conversations and negotiations with all prospective organizers, shepherding promising concepts to approved programs.

Alistair has also been relentless in making people do things, and making them do things by prescribed deadlines, something that is notoriously difficult in our community. The Simons Institute programs have succeeded, in part, because of the tremendous amount of volunteer work that the organizers donated to our community, and while they would all have been extremely generous with their time in any case, Alistair made sure that they were extra generous. A personal anecdote: I was one of the organizers of one of the Fall 2013 inaugural programs. At that point, I was at Stanford and we were beginning to discuss the idea that I could come back to Berkeley. At some point, around October, I get a phone call from Alistair, and I assume he wants to talk about it. Instead, he goes “you know, I haven’t been seeing you much at the Institute so far. We expect organizers to be around a lot more.” A few months later, I got the offer to move to Berkeley, with a 50% affiliation at the Institute. Even knowing who my boss would be, I enthusiastically accepted.

Oded Goldreich received the Knuth Prize. I have already said how I feel about Oded, so there is no need to repeat myself, but I will add that I am also really happy for the Knuth Prize itself, that has managed to consistently make really good choices for the past 21 years, which is an outstanding record.

Finally, and I can’t believe that it took so long, the paper of Dwork, McSherry, Nissim and Smith, that introduced differential privacy, has been recognized with the Godel prize. I am very happy for them, especially for my matron of honor and former neighbor Cynthia.

Congratulations to all, and by all I don’t mean just the aforementioned awardees, but also our whole community, that nurtures so many great people, inspires so many good ideas, and makes being part of it such a joy (even when Alistair makes me do things).

# Chariots of Fire: Silvio Micali on Oded Goldreich and Scientific Collaborations

At the aforementioned Oded Fest that took place at Weizmann a couple of weeks ago, Silvio Micali read from an epic prepared speech, which tied together the early work on foundations of cryptography, ancient Greece, the Renaissance, Viennese cafés, and the movies “Chariots of Fire” and “The Seven Samurai.”

Silvio has given his kind permission to share the speech, and he has put it in a pdf form that includes the pictures that he used as slides.

Here it is

# Fests

I have been in Israel for the last couple of days attending an event in honor of Oded Goldreich‘s 60th birthday.

Oded has touched countless lives, with his boundless dedication to mentoring, executed with a unique mix of tough love and good humor. He embodies a purity of vision in the pursuit of the “right” definitions, the “right” conceptual point of view and the “right” proofs in the areas of theoretical computer science that he has transformed with his work and his influence.

A turning point in my own work in theoretical computer science came when I found this paper online in the Spring of 1995. I was a second-year graduate student in Rome, and I was interested in working on PCP-based hardness of approximation, but this seemed like an impossible goal for me. Following the publication of ALMSS, there had been an avalanche of work between 1992 and 1995, mostly in the form of extended abstracts that were impossible to understand without an awareness of a context that was, at that point, purely an oral tradition. The aforementioned paper, instead, was a 100+ page monster, that explained everything. Studying that paper gave me an entrance into the area.

Three years later, while i was a postdoc at MIT and Oded was there on sabbatical, he played a key role in the series of events that led me to prove that one can get extractors from pseudorandom generators, and it was him who explained to me that this was, in fact, what I had proved. (Initially, I thought my argument was just proving a much less consequential result.) For the most part, it was this result that got me a good job and that is paying my mortgage.

Like me, there are countless people who started to work in a certain area of theoretical computer science because of a course that Oded taught or a set of lecture notes that he wrote, and countless people whose work was made possible by Oded nudging, or usually shoving, them along the right path.

The last two days have felt a bit like going to a wedding, and not just because I saw friends that I do not get to see too often and because there was a lot to eat and to drink. A wedding is a celebration of the couple getting married, but it is also a public event in which friends and family, by affirming their bonds to the newlyweds, also affirm their bonds to each other.

I was deeply moved by the speeches given by Silvio and Shafi, and really everybody did a great job at telling Oded stories and bringing to life various aspects of his work and personality. But perhaps the most fittingly weird tribute was Benny Chor presenting the Chor-Goldreich paper (the one that introduced min-entropy as a measure of randomness for weak random sources, and the problem of 2-source extraction) using the original 1985 slides.

Speaking of public celebrations, there is less than a month left to register for STOC 2017, the “Theory Fest” that will take place in Montreal in June.

# Coincidence?

“Art imitates life, but life imitates bad TV” (Woody Allen)

The mention for a major alumni award given by U.C. Berkeley is for excellence in achievement.

Meanwhile, in the episode “Brother, can you spare two dimes?”, Mr. Burns has to come up on the spot with the name for a fake awards, and he comes up with an award for outstanding achievement in the field of excellence.

(You’ll note that the dancers in the video are wearing gold and blue)

# ما همه ایرانی

Many people are angry and heartbroken at the consequences (on themselves, their loved ones, their friends and coworkers) of the executive order that has banned refugees, as well as legal immigrants and green card holders, from certain countries from entering the US for the next few months. A common question is, what can we do? A few possibilities:

• Donate to the ACLU. They have a long history of fighting for civil rights and, on Saturday, they immediately sprung into action and where able to get a stay on the ban, whose implications are still not clear.
As you are contemplating donations, consider also supporting Planned Parenthood and the Southern Poverty Law Center. This is unrelated to the current refugees/immigrant crisis, but it is relevant to what will probably be future crises instigated by the current administration. (The SPLC does a great work in tracking and documenting hate groups.)
• Sign this petition, which has received significant media coverage
• Do what you can to make sure our professional societies produce a response. Both the outgoing and the incoming presidents of the AMS have signed the above petition, and I understand that the appropriate committee of the AMS  is considering making a statement. I don’t know if the ACM is planning a similar action, and if you have access to the ACM leadership, please lean on them to do so.
(Edited to add: ACM put out a statement Monday morning, and so this the AMS.)
• Call your representatives in congress, especially if you live in a state with Republican senators or in a district with a Republican representative. Don’t email: call and ask to speak with the staffer who is responsible for immigration matters.
• Reach out to colleagues, students and staff who are affected by the executive order. If you have channels to do so, pressure campus leadership to cover their legal expenses, which could be substantial.

# Matrix Multiplication Not Yet Doable In Quadratic Time

Last night, a paper appeared on the arXiv titled A $\Theta(n^2)$ time matrix multiplication algorithm.

At first look the paper seemed to score zero on Scott Aaronson’s list of Ten Signs a Claimed Mathematical Breakthrough is Wrong, and it came from a researcher who has worked extensively on the related problem of all-pairs shortest path, so it looked exciting. Unfortunately, it actually scores one on Scott’s list: it contradicts known impossibility results. (Thanks to Yuval Filmus for the references.)

The first step in the algorithm is to show how to compute the inner product of two $3^n$-dimensional vectors using $n^{O(1)} \cdot 2^n$ multiplication. This contradicts a lower bound due to Pan (see here the proof of a more general result) that computing the inner product of two N-dimensional vectors require at least N multiplications.

In addition, Raz has proved an $\Omega (n^2 \log n)$ lower bound for matrix multiplication arithmetic circuits, and, to the best of my understanding, the paper’s claims imply an $O(n^2)$ size arithmetic circuit. (Raz’s lower bound assumes that the circuit is not given access to large constants; as far as I can see, the formulas in Han’s paper do not require large constants.)

# What’s New at the Simons Institute

This Thursday (December 15) is the deadline to apply for post-doctoral positions at the Simons Institute for the next academic year. In Fall 2017 we will run a single program, instead of two programs in parallel, on optimization. The program will be double the size of our typical programs, and will focus on the interplay between discrete and continuous methods in optimization. In Spring 2018 there will be a program on real-time decision-making and one on theoretical neuroscience.

In a few weeks, our Spring 2017 programs will start. The program on pseudorandomness will have a mix of complexity theorists and number theorists, and it will happen at the same time as a program on analytic number theory at MSRI. It will start with a series of lectures. It will start with a series of lectures in the third week of January. The program on foundations of machine learning has been much anticipated, and it will also start with a series of lectures, in the fourth week of January, which will bring to Berkeley at impressive collection of machine learning practitioners whose research is both applied and rigorous. All lectures will be streamed live, and I encourage you to set up viewing parties.

During the current semester, the Simons Institute had for the first time a journalist in residence. The inaugural resident journalist has been Erica Klarreich, that many of you probably know for her outstanding writing on mathematics and computer science for quanta magazine.

Next semester, our resident journalist will be Pulitzer-prize winner John Markoff, who just retired from the New York Times.

# The vocabulary is political

Remember when the (GW) Bush administration decided that torture should be called “enhanced interrogation techniques,” and then the New York Times, like all other American news sources, started to call torture “enhanced interrogation techniques,” and people wrote angry letters to the public editor, and the public editor eventually wrote that if the White House decides that torture should not be called torture then calling torture torture is a political issues on which reporters should not take sides?

And Paul Krugman wrote a column in which he said that if the Bush administration declared that the Earth is flat, then the New York Times would have an article headlined “Roundness of Earth disputed,” in which it would make sure to have quotes both from round-Earther and flat-Earther?

Part of the reason for all this, as explained in this very good article in The Atlantic, is that political reporters (as opposed to political opinion writers) need access, that is, they need White House officials to talk to them, whether on the record or off the record. The ability to withhold access gives administration officials great leverage.

And so Myron Ebell, who works in a think-tank financed by the coal industry, and according to whom climate change is a vast conspiracy perpetrated by left-wing scientists, some of which scientists he has personally attacked, and who is being considered to lead the EPA, is now a climate contrarian, according to the New York Times.

Maybe soon enough, outside the opinion page, the New York Times will start calling racism “race realism.”

# We need to occupy unsafe spaces

Today an atmosphere of grief pervaded Berkeley, and a series of emails came from higher and higher up the chain of command, culminating with one from Janet Napolitano, reaffirming the University of California’s commitment to its principles of inclusivity, diversity, and all things that are good. Here is an email from the Vice-Chancellor for Equity and Inclusion:

Dear Cal Students, Staff, and Faculty,

We know that the results of yesterday’s election have sparked fear and concern among many in our community; in particular our immigrant and undocumented communities, Muslim, African American, Chicanx/Latinx, LGBTQ+, Asian and Pacific Islander communities, survivors of sexual assault, people with disabilities, women, and many others. We are reaching out to you with a message of support. UC Berkeley leadership remains steadfast in our values and committed to the safety and well-being of all of our students, faculty, and staff. We condemn bigotry and hatred in all forms, and hold steadfast in our commitment to equity, access, and a campus that is safe, inclusive, and welcoming to all.

Various communities have organized the following community spaces and resources:

• A community space for undocumented students tonight at 6:30pm in Chavez Room 105.
• CLSD and CLPR are hosting space at the Shorb House, 2547 Channing Way from 12pm-5pm for students to come by. Faculty and staff will be there in community with our students for support.
• MCC is holding a safe space for POC/Black students from 8pm-10pm this evening.
• QTAP is hosting a QTOPC dinner in Anthony Hall at 6pm.
• The Gender Equity Resource Center is open today, until 5pm, for those who wish for a quiet space for contemplation and community. GenEq is also hosting the following healing spaces:
• Women’s Healing Space – Today, November 9th, 1pm-2:30pm
• LGBTQ+ Healing Space – Today, November 9th, 2:30pm-4pm

Now, without discounting the value of having a good place to quietly sob with like-minded people, this strikes me as the message you would send after the Charleston shooting, or the Orlando shooting. This was not the act of one disturbed person. Sixty million Americans went to the trouble of going all the way to the polling place to vote for Trump, or of filling up their absentee ballot, and then mailing it in. That’s one in four adult Americans, a diverse coalition of white people: educated white people and less educated white people, male white people and female white people, religious white people and secular white people, and, one should note, even a few people who are not white. White people who thought it’s their constitutional right to discriminate against gay people, white people who think it’s ok to grab women by their pussy, and that you can get away with it if you are a star, white people who think muslims should not come to the US.

Our students will meet these people everywhere. They will be their neighbors, their coworkers, their bosses, and maybe their in-laws. When our students graduate, there will be no safe space.

And if there were, that is not where they should go. Because those sixty million people will not change their minds by talking among themselves.

But the oppressed cannot be left alone to speak out for themselves.

A feature of rape prevention programs is bystander intervention training: telling people how to recognize a situation in which someone is at risk of assault, and intervene.

We need white people to speak out against racism, christians to speak out for the religion freedom of non-christians, men to speak out against misogyny, straight people to speak out for LGBT people, Republicans to speak out against Trump.

And we need them to do this where it is not safe to do so, because otherwise all we have is angry people talking to the like-minded on the internet.