You are currently browsing the category archive for the ‘theory’ category.

Today, after a lecture in the spectral graph theory boot camp at the Simons institute, I was asked what the expander mixing lemma is like in graphs that are not regular.

I don’t know if I will have time to return to this tomorrow, so here is a quick answer.

First, for context, the expander mixing lemma in regular graph. Say that ${G=(V,E)}$ is a ${d}$-regular undirected graph, and ${A}$ is its adjacency matrix. Then let the eigenvalues of the normalized matrix ${\frac 1d A}$ be

$\displaystyle 1 = \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$

We are interested in graphs for which all the eigenvalues are small in absolute value, except ${\lambda_1}$, that is, if we define

$\displaystyle \sigma_2 := \max\{ |\lambda_2|, |\lambda_3 | , \ldots , | \lambda_n | \}$

we are interested in graphs for which ${\sigma_2}$ is small. The expander mixing lemma is the fact that for every two disjoint sets ${S}$ and ${T}$ of vertices we have

$\displaystyle \left | E(S,V-S) - \frac d n \cdot |S| \cdot |T| \right | \leq \sigma_2 d \sqrt{ |S| \cdot |T|} \ \ \ \ \ (1)$

The inequality (1) says that, if ${\sigma_2}$ is small, then the number of edges between every two large sets of vertices is almost determined just by the size of the sets, and it is equal to the expected number of edges between the two sets in a random ${d}$-regular graph, up to an error term that depends on ${\sigma_2}$.

For the proof, we observe that, if we call ${J}$ the matrix that has ones everywhere, then

$\displaystyle \sigma_2 = \max_{x \perp (1,\ldots , 1) } \frac { |x^T A x|}{d\cdot x^Tx} = \max_{x} \frac { \left|x^T \left( A - \frac dn J \right) x \right|}{d\cdot x^T x} = \max_{x,y} \frac { \left|x^T \left( A - \frac dn J \right) y \right|}{d\cdot ||x|| \cdot ||y||}$

and then we substitute ${x := {\mathbf 1}_S}$ and ${y:= {\mathbf 1}_T}$ in the above expression and do the calculations.

In the case of an irregular undirected graph ${G=(V,E)}$, we are going to consider the normalized adjacency matrix ${M:= D^{-\frac 12} A D^{-\frac 12 }}$, where ${A}$ is the adjacency matrix of ${G}$ and ${D}$ is the diagonal matrix such that ${D_{v,v} = d_v}$, where ${d_v}$ is the degree of ${v}$. As in the regular case, the eigenvalues of the normalized adjacency matrix satisfy

$\displaystyle 1 = \lambda_1 \geq \lambda_2 \geq \cdots \lambda_n \geq -1$

Let us define

$\displaystyle \sigma_2:= \max \{ |\lambda_2| , |\lambda_3| , \ldots, |\lambda_n| \}$

the second largest eigenvalue in absolute value of ${M}$.

We will need two more definitions: for a set of vertices ${S}$, its volume is defined as

$\displaystyle vol(S):= \sum_{v\in S} d_v$

the sum of the degrees and ${\bar d = \frac 1n \sum_v d_v}$ the average degree, so that ${vol(V) = \bar d n }$. Now we have

Lemma 1 (Expander Mixing Lemma) For every two disjoint sets of vertices ${S}$, ${T}$, we have

$\displaystyle \left | E(S,V-S) - \frac {vol(S) \cdot vol(T) }{vol(V)} \right | \leq \sigma_2 \sqrt{vol(S) \cdot vol(T) } \ \ \ \ \ (2)$

So, once again, we have that the number of edges between ${S}$ and ${T}$ is what one would expect in a random graph in which the edge ${(u,v)}$ exists with probability ${d_ud_v/vol(V)}$, up to an error that depends on ${\sigma_2}$.

The spectral norm of the infinite ${d}$-regular tree is ${2 \sqrt {d-1}}$. We will see what this means and how to prove it.

When talking about the expansion of random graphs, abobut the construction of Ramanujan expanders, as well as about sparsifiers, community detection, and several other problems, the number ${2 \sqrt{d-1}}$ comes up often, where ${d}$ is the degree of the graph, for reasons that tend to be related to properties of the infinite ${d}$-regular tree.

In preparation for the special program on spectral graph theory at the Simons Institute, which starts in a week, I have been reading on the topics of the theory that I don’t know much about: the spectrum of random graphs, properties of highly expanding graphs, spectral sparsification, and so on.

I have been writing some notes for myself, and here is something that bothers me: How do you call the second largest, in absolute value, eigenvalue of the adjacency matrix of a graph, without resorting to the sentence I just wrote? And how do you denote it?

I have noticed that the typical answer to the first question is “second eigenvalue,” but this is a problem when it creates confusion with the actual second largest eigenvalue of the adjacency matrix, which could be a very different quantity. The answer to the second question seems to be either a noncommittal “${\lambda}$” or a rather problematic “${\lambda_2}$.”

For my own use, I have started to used the notation ${\lambda_{2abs}}$, which can certainly use some improvement, but I am still at a loss concerning terminology.

Perhaps one should start from where this number is coming from, and it seems that its important property is that, if the graph is ${d}$ regular and has ${n}$ vertices, and has adjacency matrix A, this number is the spectral norm of ${A - \frac dn J}$ (where ${J}$ is the matrix with ones everywhere), so that it measures the distance of ${A}$ from the “perfect ${d}$-regular expander” in a norm that is useful to reason about cuts and also tractable to compute.

So, since it is the spectral norm of a modification of the adjacency matrix, how about calling it ${<}$adjective${>}$ spectral norm? I would vote for shifted spectral norm because I would think of subtracting ${\frac dn J}$ as a sort of shift.

Shafi Goldwasser sends a reminder that the deadline to submit to the next innovations in theoretical computer science conference is next Friday. The conference will take place in January 2015 at the Weizmann Institute, with contingency plans to hold it in Boston in case the need for a relocation arises.

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.

Where you least expect them:

a common [definiton] for “population” is a geographical cluster of people who mate more within the cluster than outside of it

As you may remember, a few months ago Dieter van Melkebeek, the steering committee chair of the conference on computational complexity, started a discussion on the future of the conference and on its relation to IEEE.

A poll among CCC former participants showed that 97% of respondents favored change, and a majority wanted the conference to be independent of both IEEE and ACM. The steering committee, subsequently, voted unanimously to make the conference independent.

The steering committee is now working out the logistics, and volunteers are needed to help. Already several people have pledged to contribute in various forms, and if you are interested there will be organizational meetings in Vancouver during CCC 2014. (By the way, today is the deadline for early registration.)

I would like to publicly thank Dieter both for the effort that he put on making this change happen and for the transparency of the process. I hope that, if some big change is coming for STOC or FOCS, it will be the result of a similarly open discussion.

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.

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.