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

Suppose that we want to construct a very good family of ${d}$-regular expander graphs. The Alon-Boppana theorem says that the best we can hope for, from the point of view of spectral expansion, is to have ${\lambda_2 \leq 2 \sqrt{d-1}}$, and we would certainly be very happy with a family of graphs in which ${\lambda_2 \leq O(\sqrt d)}$.

Known constructions of expanders produce Cayley graphs (or sometimes Schreier graphs, which is a related notion), because it is easier to analyze the spectra of such graphs. If ${\Gamma}$ is a group with operation ${\cdot}$ and ${a^{-1}}$ is the inverse of element ${a}$, and ${S}$ is a symmetric set of generators, then the Cayley graph ${Cay(\Gamma, S)}$ is the graph whose vertices are the elements of ${\Gamma}$ and whose edges are the pairs ${(a,b)}$ such that ${a\cdot b^{-1} \in S}$.

When the group is Abelian, there is good news and bad news. The good news is that the eigenvectors of the graphs are completely characterized (they are the characters of ${\Gamma}$) and the eigenvalues are given by a nice formula. (See here and here.) The bad news is that constant-degree Cayley graphs of Abelian groups cannot be expanders.

That’s very bad news, but it is still possible to get highly expanding graphs of polylogarithmic degree as Cayley graphs of Abelian groups.

Here we will look at the extreme case of a family of graphs of degree ${d_n = n/2}$, where ${n}$ is the number of vertices. Even with such high degree, the weak version of the Alon-Boppana theorem still implies that we must have ${\sigma_2 \geq \Omega(\sqrt d_n)}$, and so we will be happy if we get a graph in which ${\sigma_2 \leq O(\sqrt d) = O(\sqrt n)}$. Highly expanding graphs of degree ${n/2}$ are interesting because they have some of the properties of random graphs from the ${G_{n,\frac 12}}$ distribution. In turn, graphs from ${G_{n,\frac 12}}$ have all kind of interesting properties with high probabilities, including being essentially the best known Ramsey graphs and having the kind of discrepancy property that gives seedless extractors for two independent sources. Unfortunately, these properties cannot be certified by spectral methods. The graph that we will study today is believed to have such stronger properties, but there is no known promising approach to prove such conjectures, so we will content ourselves with proving strong spectral expansion.

The graph is the Payely graph. If ${p}$ is a prime, ${{\mathbb Z} / p {\mathbb Z}}$ is the group of addition modulo ${p}$, and ${Q}$ is the set of elements of ${{\mathbb Z}/ p{\mathbb Z}}$ of the form ${r^2 \bmod p}$, then the graph is just ${Cay ( {\mathbb Z}/p{\mathbb Z}, Q)}$. That is, the graph has a vertex ${v}$ for each ${v\in \{ 0,\ldots,p-1\}}$, and two vertices ${a,b}$ are adjacent if and only if there is an ${r\in \{ 0,\ldots,p-1\}}$ such that ${a-b \equiv r^2 \pmod p}$.

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.