IMG_2614

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…

tiananmen

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.

I was having dinner at Machne Yuda, that was recommended to me as one of the best places to eat in Jerusalem (although I liked Chakra much better), and I was sitting at the bar, cramped between the French gay couple and the drunk Israeli lady with the huge boyfriend.

At the same time that I got my dessert, the lady with the huge boyfriend stood up to leave and, with remarkable swiftness for a drunk lady, took a piece of my cake asking, while she was already doing so, if she could try it.

Now, between the fact of the ground that a piece of my cake was already on her fork, the size of the boyfriend, the fate of the last people who tried to fight with the Israeli about what is whose and, really, haven’t the Jewish people suffered enough already?, the only logical thing to say was, sure, help yourself.

A little bit later, the bartender presented me with another (different) dessert. “This is on the house,” the bartender said, “I saw what she did, and it wasn’t right.”

The second dessert was better.

Dieter van Melkebeek, the conference chair of the Computational Complexity Conference (CCC), has started a discussion on whether to end the IEEE “sponsorship” of CCC. This is, I realize, a supremely boring topic, which seemingly affects only the handful of people who are tasked with organizing the conference. It does, however, affect to some extent all who ever paid a registration fee or published a paper in CCC, and I would like to discuss why I am, in the strongest possible way, in favor of leaving IEEE.

First of all, the term “sponsoring” here is a bit misleading. IEEE sponsors CCC not in the way Coca Cola sponsors the Olympics, but more in the way pirates sponsor navigation, or Elsevier sponsors scholarly publications. That is, it’s not that IEEE subsidizes the conference in exchange for exposure and good will; IEEE takes a huge chunk of our registration money, in exchange for making the lives of the local organizers harder. (I don’t mean to single out IEEE, when a professional society sponsors a conference it always works this way, but IEEE is particularly skilled at making the lives of the organizers hard.)

Last year I was an organizer of the complexity conference at Stanford. We had 108 attendees, who paid a total of $37,425 of registrations, or $346.5 each on average. How did we spend this money?

IEEE charged a 20% overhead to all expenses; that’s about $60 per person and about $6,500 for the whole conference. This, I should emphasize, is for doing literally nothing, except creating problems. For example, our conference could not be “approved” until all the paperwork of the previous conference was closed; it wasn’t closed because they were expecting some banking documents from them and I don’t remember if the issue was that the document does not exist in Portugal, or that they had already received the document and they had lost it. We were not allowed to make the conference web site go live until this was resolved.

One of the perks of organizing the conference with IEEE is that they provide free banking in the United States. (If the conference were organized by a created-for-this-purpose non-profit, it could have its own permanent bank account for little or no fee.) Three weeks after we sent all the paperwork to have our IEEE bank account set up, we get an email from the person we paid $6,500 to “assist” us, saying “URGENT, URGENT, you have to send us the paperwork for the bank account”. After we reminded them that they had had it for three weeks, they replied, “oh yes, we do,” no apology. (And it still took a while to get the checks.)

The free banking does not include free registration handling, however. Here I accept responsibility for being foolish enough, after all this, to trust IEEE with their registration service. At a cost of more than $26 per person (that’s almost $3,000) they produced a registration website that seemed put together by a high school intern, and which required filling up five pages of… well, if you attended the conference you remember it.

Finally, IEEE press charged almost $2,000 (almost $18 per person) for the proceedings. Which proceedings, you may ask, since the conference had no proceedings? That’s a very good question. The charge of $1,925 was to take our papers, take the copyright, and then put the papers were it is impossible to find them, even if you subscribe to the IEEE digital library. (Seriously, try to google a paper appeared in an ACM conference and one appeared in an IEEE conference and see if you are able to get the IEEE paper. Say what you want about the ACM, at least they know how to build a web site.)

In summary, IEEE took $6,500 for doing nothing but causing delays, $3,000 for a terrible registration site, and $2,000 to hide our papers. That’s more than $100 per attendee, and about 30% of how we spent the registration fee. The rest went on food and room rent.

Why are we still doing this? One reason is that the only people that are really affected by this system are the local organizers, and once one is done with the job, one doesn’t want to hear of or talk about IEEE any more. The other reason is that there is a big initial effort that is needed to make the conference independent. One needs to start some kind of entity to own the conference (the IACR, for example, was founded pretty much for the purpose of running CRYPTO and the other crypto conferences), which needs to have a statute, officers, a bank account and all kind of paperwork needs to be done. After that, however, it’s smooth sailing and considerable savings.

Here is one thing that IEEE does: if the conference runs a deficit, they cover it. We did, in fact run a deficit last year, of about $1,000; so IEEE “covered” it, but that just means that instead of $6,500 for the “sponsorship” they got $5,500. If, going forward, we budget with the intention of putting away $5,000 to $7,000 per year, the registration costs will go down slightly and over a few years we can put away, say $20,000 that can be a cushion for any kind of unforeseen event, and from that point forward budget to a balanced budget, with notably lower registration fees, and with some years running a surplus and some years running a deficit. Plus, we own our papers, and people can find them!

Ok, this is as boring as could be expected. I thank all those that have read so far, and, for the sanity of future local organizers and the principle of keeping our hard-earned taxpayer money and our papers, please support making CCC an independent conference.

Link to CCC forum

大展鴻圖

I would like to pass along the following piece of information that I received from Tal Rabin: the next bi-annual Women in Theory Workshop will be this May 28-30, 2014, in New York City, immediately preceding STOC 2014, which will also take place there.

Applications are due by January 20, 2014.

The relevant information is at womenintheory.wordpress.com

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 simons.berkeley.edu/fellows2014; the deadline to apply is December 15.

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.

“I think we have some folks who believe that our job is to be college professors. Now college professors are fine I guess. Being a college professor, they basically spout out ideas that nobody does anything about.”

Chris Christie, Governor of New Jersey, in a recent speech in, of all places, Boston.

This year is the centennial of Paul Erdős’s birth. Erdős lived most of his adult life as a traveling mathematician, “couchsurfing,” as we would say now, from place to place and from mathematical conference to mathematical conference. He wrote more than 1,500 papers with more than 500 different coauthors, introduced the probabilistic method and was the defining figure of the “Hungarian approach” to combinatorics. He died at age 83 while attending a mathematical conference.

Last year, we celebrated the centennial of Alan Turing’s birth. Turing and Erdős have become such iconic figures both for the impact of their work and for the fascinating facts of their lives. I would like to argue that the cultural archetype through which we interpret their lives is that of the saint. It is clearly that of the martyr saint in the case of Turing, while Erdős gave up material possessions and devoted his life to others, traveling everywhere and “preaching” to everybody, much in the mold of Saint Francis.

(A comparison of the Turing centennial celebration and Erdős’s, and a look at the frescoes of Medieval Catholic churches will show which kind of saint people are more interested in.)

The first step to become a saint of the Catholic church is to establish that the person exhibited “heroic virtues,” which is a great expression. This is an archetype that is not restricted to religion: you see it occurring in communist propaganda (Stakhanov, Lei Feng) and in every civil rights movement.

Saints were the “celebrities” of the Middle Ages, those whose life people liked to talk about. But contemporary celebrities come from a totally different archetype, that of the Greek God. Greek (and Roman) gods were petty and jealous, they cheated on their spouses, they were terrible parents, but there were good stories to be told about them. We don’t want (at least, I don’t) to live the life of a saint, but thinking about them is certainly inspirational and it makes us think that if someone can be so much better than us, maybe we can be a little better ourself in the practice of “virtues”, whatever this may mean to us. And we don’t admire gods, but, well, it’s probably fun to be one.

As usual, I have lost track of what I was trying to say, but I think that it speaks well of the academic community that we are more interested in saints than in gods, I will close by saying that my favorite saint of complexity theory is Avi Wigderson, I will keep to myself who my favorite god of complexity theory is, and I will leave it to the readers to contribute their picks.

This week, the topic of my online course on graph partitioning and expanders is the computation of approximate eigenvalues and eigenvectors with the power method.

If M is a positive semidefinite matrix (a symmetric matrix all whose eigenvalues are nonnegative), then the power method is simply to pick a random vector x\in \{ -1,+1 \}^n, and compute y:= M^k x. If k is of the order of \frac 1 \epsilon \log \frac n \epsilon, then one has a constant probability that

\frac {y^T M y}{y^T y} \geq (1-\epsilon) \max_{x} \frac {x^T M x}{x^T x} = (1-\epsilon) \lambda_1

where \lambda_1 is the largest eigenvalue of M. If we are interested in the Laplacian matrix L = I - \frac 1d A of a d-regular graph, where A is the adjacency matrix of the graph, this gives a way to compute an approximation of the largest eigenvalue, and a vector of approximately maximum Rayleigh quotient, which is useful to approximate Max Cut, but not to apply spectral partitioning algorithms. For those, we need a vector that approximates the eigenvector of the second smallest eigenvalue.

Equivalently, we want to approximate the second largest eigenvalue of the adjacency matrix A. The power method is easy to adjust to compute the second largest eigenvalue instead of the largest (if we know an eigenvector of the largest eigenvalue): after you pick the random vector, subtract the component of the vector that is parallel to the eigenvector of the largest eigenvalue. In the case of the adjacency matrix of a regular graph, subtract from every coordinate of the random vector the average of the coordinates.

The adjacency matrix is not positive semidefinite, but we can adjust it to be by adding a multiple of the identity matrix. For example we can work with \frac 12 I + \frac 1{2d} A. Then the power method reduces to the following procedure: pick randomly x \sim \{ -1,1\}, then subtract \sum_i x_i/n from every entry of x, then repeat the following process k = O\left( \frac 1 \epsilon \log \frac n \epsilon \right) times: for every entry i, assign x_i := \frac 12 x_i + \frac 1 {2d} \sum_{j: (i,j) \in E} x_j, that is, replace the value that the vector assigns to vertex i with a convex combination of the current value and the current value of the neighbors. (Note that one iteration can be executed in time O(|V|+|E|).

The problem is that if we started from a graph whose Laplacian matrix has a second smallest eigenvalue \lambda_2, the matrix \frac 12 I + \frac 1{2d} A has second largest eigenvalue 1- \frac {\lambda_2}2, and if the power method finds a vector of Rayleigh quotient at least (1-\epsilon) \cdot \left( 1- \frac {\lambda_2}2 \right) for \frac 12 I + \frac 1{2d} A, then that vector has Rayleigh quotient about \lambda_2 - 2\epsilon for L, and unless we choose \epsilon of the same order as \lambda_2 we get nothing. This means that the number of iterations has to be about 1/\lambda_2, which can be quite large.

The video below (taken from this week’s lecture) shows how slowly the power method progresses on a small cycle with 31 vertices. It goes faster on the hypercube, which has a much larger \lambda_2.

A better way to apply the power method to find small eigenvalues of the Laplacian is to apply the power method to the pseudoinverse L^+ of the Laplacian. If the Laplacian of a connected graph has eigenvalues 0 = \lambda_1 < \lambda_2 \leq \cdots \leq \lambda_n, then the pseudoinverse L^+ has eigenvalues 0, \frac 1 {\lambda_2}, \cdots, \frac 1 {\lambda_n} with the same eigenvectors, so approximately finding the largest eigenvalue of L^+ is the same problem as approximately finding the second smallest eigenvalue of L.

Although we do not have fast algorithms to compute L^+, what we need to run the power method is, for a given x, to find the y such that L y = x, that is, to solve the linear system Ly = x in y given L and x.

For this problem, Spielman and Teng gave an algorithm nearly linear in the number of nonzero of L, and new algorithms have been developed more recently (and with some promise of being practical) by Koutis, Miller and Peng and by Kelner, Orecchia, Sidford and Zhu.

Coincidentally, just this week, Nisheeth Vishnoi has completed his monograph Lx=b on algorithms to solve such linear systems and their applications. It’s going to be great summer reading for those long days at the beach.

a

Follow

Get every new post delivered to your Inbox.

Join 228 other followers