Pre-party Activities

This Saturday, a good way to spend your time before the reception at the Simons Institute is to attend the FOCS’17 workshops. Three workshops will be running in parallel, on sketching, on distribution testing, and on query and communication complexity.


Annuntio vobis gaudium magnum: habemus directors

(Photo credit: ACM)

Formally ending a search started in March 2016 (and a process started in the Fall of 2015), we are pleased to finally officially announce that Shafi Goldwasser will take over from Dick Karp as director of the Simons Institute for Computing on January 1st, and will return to Berkeley after a 30+ year hiatus.

Shafi is the co-inventor and developer of the notions semantic security in encryption; of zero-knowledge proofs; of pseudorandom functions; of the connection between PCP and hardness of approximation; and of property testing in sublinear algorithms, among others. She has received the Turing award for her work on cryptography and of two Gödel prizes for her work on complexity.

I cannot put in words how happy I am for the Berkeley community, including myself, and for the future of the Institute.

The director search was my first glimpse into how the Berkeley central campus bureaucracy operates, and it was horrifying. The simplest thing couldn’t be done without a sequence of authorities signing off on it, and each authority had a process for that, which involved asking for other things that other authorities had to sign off on, and so on in what at times seemed actual infinite descent.

The announcement linked above was in the works for at least three weeks!

Alistair Sinclair, after two terms as associate director of the Simons Institute, during which his heroic efforts were recognized with the SIGACT service award, also retired from his position at the Institute, and last July 1st was replaced by Berkeley professor Peter Bartlett, a noted pioneer of the study of neural networks.

This weekend, on Saturday, the Simons Institute will host the FOCS reception, which will double as celebration for Alistair’s prize. There will buses leaving the conference hotel at 6:45pm, and there will be plenty of food (and drinks!) at the Institute. There will also be buses taking people back to the hotel, although once you are in downtown Berkeley on a Saturday evening (bring a sweater) you may want to hang out a bit more and then take a rideshare service back to the hotel.

How was FOCS 2015?

Back around 2010, the Simons Institute for the Theory of Computing at Berkeley offered to organize FOCS in 2013, 2015 and 2017. So far, the IEEE technical committee on mathematical foundations of computing has taken us up on this offer in 2013 and 2015, and, unless a competing bid is presented, FOCS will come again to Berkeley in 2017.

Unfortunately there is no hotel in downtown Berkeley that is able to accommodate FOCS. The Shattuck hotel almost but not quite is. (There are two conference rooms, but they are of very different size, and the space to hang out for coffee breaks is much too small for 200+ people, and it’s outdoors, which is potentially bad because rain in October is unlikely but not impossible in Berkeley.)

This leaves us with the Doubletree hotel in the Berkeley Marina, which has some advantages, such as views of the bay and good facilities, and some disadvantages, such as the isolated location and the high prices. The location also forces us to provide lunches, because it would be inconvenient for people to drive to lunch places and then drive back during the lunch break. Being well aware of this, the hotel charges extortionate fees for food.

This is to say that, planning for FOCS 2017, there is nothing much different that we can do, although there are lots of little details that we can adjust, and it would be great to know how people’s experience was.

For example, did the block of discounted hotel rooms run out too soon? Would you have liked to have received something else with your registration than just the badge? If so, what? (So far, I have heard suggestions for FOCS-branded hats, t-shirts, and teddy bears.) Wasn’t it awesome to have a full bar at the business meeting? Why did nobody try the soups at lunch? The soups were delicious!

FOCS 2015

This is an odd-numbered year, and FOCS is back in Berkeley. The conference, whose early registration deadline is coming up, will be held on October 18-20 at the Double Tree hotel near the Berkeley marina, the same location of FOCS 2013, and it will be preceded by a day-long conference in honor of Dick Karp’s 80th birthday.

Early registration closes next Friday, so make sure that you register before then.

The weekend before FOCS there will be the Treasure Island Music Festival; Treasure Island is halfway along the Bay Bridge between Oakland and San Francisco, and from the Island there are beautiful views of the Bay Area.

After FOCS, there is a South Asian Film Festival in San Francisco.

If you arrive on Friday the 16th and you want to spend an afternoon in San Francisco, at the end of the day you can find your way to the De Young Museum in Golden Gate park, which stays open until 8:30pm on Fridays, and it has live music and a bar in the lobby from 5:30 to 8:30.

Did I mention that the early registration deadline is coming up? Don’t forget to register.

On Berkeley and Recycling

For the past few days, I have been getting emails that are the Platonic ideal of the U.C. Berkeley administration.

Today, there was a one-hour presentation on recycling and composting at Soda Hall, the computer science building. This is worth saying once more: a one hour presentation on putting glass, metal, and certain plastics in one container, clean paper in another, and compostable material in a third one. We received an email announcement, then an invitation to add the event to our calendar, then two remainders.

But what if one cannot make it? Not to worry! There will be a second one hour presentation on recycling, for those who missed the first one, and for those that were so enthralled by the first one that they want to spend one more hour being told about recycling.

Meanwhile, I have been trying since February to get a desk, a conference table and a bookshelf for my office in Soda Hall. So far I got the desk.

I asked Christos what he thought about the two one-hour presentations on recycling, and he said it reminded him of a passage from a famous essay by Michael Chabon:

Passersby feel empowered-indeed, they feel duty-bound-to criticize your parking technique, your failure to sort your recycling into brown paper and white, your resource-hogging four-wheel-drive vehicle, your use of a pinch-collar to keep your dog from straining at the leash.

Sometimes I think that when the administration started hearing about MOOCs, they must have started to dream about a future with no professors, because the students all take MOOCs, and no students on campus, because they all take the MOOCs from their home, and the campus would just be filled by Assistant Chancellors of this and that, giving each other training workshops. And this would be like the episode of Get Smart in which Max infiltrates a criminal gang until he finds out that everybody is an infiltrator and there is no criminal left.

It’s the University of California COMMA Berkeley

As of today, I am again an employee of the University of California, this time as senior scientist at the Simons Institute, as well as professor of EECS.

As anybody who has spent time there can confirm, the administrative staff of the Simons Institute is exceptionally good and proactive. Not only they take care of the things you ask them, but they take care of the things that you did not know you should have asked them. In fact at Berkeley the quality of the administration tracks pretty well the level at which it is taking place. At the level of departments and of smaller units, everything usually works pretty well, and then things get worse as you go up.

Which brings me to the office of the Chancellor, which runs U.C. Berkeley, and from which I received my official job offer. As you can see, that office cannot even get right, on its own letterhead, the name of the university that it runs:

Also, my address was spelled wrong, and the letter offered me the wrong position. I can’t believe they managed to put on the correct postage stamp. I was then instructed by the EECS department chair to respond by saying “I accept your offer of [correct terms],” which sounded passive-aggressive, but that’s what I did.

This week in history


The great earthquake of 1906 struck San Francisco on April 18, around 5 in the morning. While the earthquake already caused a lot of damage, it was the subsequent fire that ravaged the city: the earthquake had broken the water pipes, and so it was impossible to fight the fire because the hydrants were not working. Except for the hydrant at Church and 20th, which saved my house and a good part of the mission. The hydrant is painted golden, and once a year, on the anniversary of the earthquake, the fire department repaints it and leaves a token of appreciation. (They actually do it at 5 in the morning.)

By the way, there are two faults that can cause earthquakes in the San Francisco Bay Area. One is (our stretch of) the San Andreas fault, which runs close to the ocean, and which caused the 1906 quake and the 1989 one, and which may not be an imminent risk given the energy released in 1989. The other is the Hayward fault, which runs near Berkeley. The Hayward fault had big earthquakes in 1315, 1470, 1630, 1725, and 1868, that is about every 100-140 years, with the last one being 146 years ago…


25 years ago on April 15, Hu Yaobang died. The day before his funeral, about 100,000 people marched to Tiananmen square, an event that led to the occupation of the square, and which culminated in what in mainland China used to be referred to as the “June 4 events,” and now as the “I don’t know what you are talking about” events.

Also, something happened, according to tradition, 1981 years ago.

Fellowships at the Simons Institute

The Simons Institute for the Theory of Computing at Berkeley has started operations a couple of months ago, it has been off to a great start. This semester there is a program on applications of real analysis to computer science, in which I am involved, and one on “big data,” whose workshops have been having such high attendance that they had to be organized offsite.

The institute itself is housed in a beautiful circular three-story building, half of whose second floor is an open space with sofas, whiteboards, tall ceilings, big windows, and exposed pipes on the ceiling, for an added loft-like look. If it had a ball pit, a foosball table, and free sushi it would look like the offices of a startup.

Next year, there will be programs on spectral graph theory, on applications of algebraic geometry, and on information theory.

Junior people (senior graduate students, postdocs, and junior assistant professors who have received their PhD no longer than six years ago) can participate in the program of the institute as “fellows.” Information on the fellowships is at; the deadline to apply is December 15.

So you are going to FOCS

The theoretical computer science traveling circus returns to the San Francisco Bay Area: FOCS 2013 will be in Berkeley in about 3 weeks. The early registration deadline is this Friday, October 4.

The week before FOCS, the Simons Institute will have a workshop on parallel and distributed algorithms for learning and optimization, as part of its program on big data.

The conference will be held in the same hotel in which FOCS 2006 was held, in the Berkeley marina. It is not a bad idea to rent a car, which will make it easier to go to downtown Berkeley and to San Francisco for dinner. You will get to drive on the new and improved Eastern span of the Bay Bridge, which is totally safe, even if the bolts are defective and will need to be replaced, or so we are being told.

There is plenty to do around San Francisco, and this list of links maintained by the Simons institute is very helpful. A couple of suggestions specific to the weekend of the 26th: open studios will run in the Mission/Castro/Noe Valley area, and there are good coffee, food and drink options in the area after seeing the art. On Friday evening, the De Young museum is open until 9pm, and it has a full bar and live music in the lobby; downstairs there is a temporary exhibition of Bulgari jewels. The De Young was designed by Herzog and de Meuron, who designed the Tate Modern in London and the National Stadium in Beijing; it is one of the few beautiful modern buildings in San Francisco. On the 27th, there is a pre-Halloween costume 5k run in Golden Gate park. Also on the 27th, James Franco will be at the Castro theater to talk about his new book and about how awesome he is.

Turing Centennial Post 7: Ashwin Nayak

[Leaving the best for last, here is Ashwin Nayak’s post. Unlike the other posts in this series, Ashwin does not just talk about events, but he also gives us a view of his inner life at several critical times. What can I say to introduce such a beautiful essay? I got this: congratulations Ashwin! — L.T.]

(Some names have been changed to protect privacy. Some events have been presented out of chronological order, to maintain continuity in the narrative. The unnamed friends in Waterloo are Kimia, Andrew, Anna-Marie, and Carl. I would like to thank them, Joe, Luca, and especially Harry for their feedback on a draft of this blog post. Harry offered meticulous comments, setting aside a myriad commitments. Most of all, I would like to thank my sisters and my parents for graciously agreeing to being included in this story.

For those not in theoretical computer science, FOCS is one of the flagship conferences on this subject. Luca is a professor of computer science at Stanford University, and Irit at Weizmann Institute of Science.

A prelude: I was born into a middle-class family from the South-West coast of India. I am the youngest of three siblings, and grew up in cities all over the country. My father served as an officer in the Indian army, and my mother taught in middle school until she switched to maintaining the household full-time. I went to IIT Kanpur for my undergraduate studies when I was 17. At 21, I moved half-way across the world to Berkeley, CA, for graduate studies. In 2002, after a few years of post-doctoral work in the US, I moved to Waterloo, ON, to take up a university faculty position.)

We were walking through art galleries in San Francisco when Luca brought up the Turing centenary events that were taking place around the world. None of the events celebrating his work referred to Turing’s homosexuality. Luca wondered whether the celebrations would be complete without revisiting this aspect of his life. As a response, he was thinking of having a series of guest blog posts by contemporary gay and lesbian computer scientists about their experiences as gay professionals. How would they compare with those in Turing’s times?

I wonder how much of my attention was on the art in the next few galleries. Would I write a post? What would I write? For me, sexuality is so deeply personal a matter that I’ve talked about it only with a handful of people. Why would I write about it publicly? Something Luca had said stuck in my mind: “The post could even be anonymous. That would be a statement in itself.” It took me back to my first relationship: I dated Mark for over three years and no one other than his friends knew. Times when I was on the verge of telling a friend about my relationships flashed by. I remembered the time I discussed with my immediate family why I would not get married (at least not the way they imagined). Times when students recognized me at events for gays and lesbians resurfaced, as did conversations with friends and colleagues grappling with openness. I would write a post, I told Luca.

That night, I got little sleep. Memories that I thought had slipped into oblivion loomed large. Continue reading