in theory

in theory moves

2008-02-16T23:15:00.000-08:00

We ring in the year of the rat with a move to wordpress, and to its superior handling of latex.

Please update your bookmarks, your RSS readers, and your blogrolls, to

http://lucatrevisan.wordpress.com/

While all old posts and comments are there, the move has broken the latex hacks, the videos, and the cross-links between posts. This will be taken care of in the "near" future.

恭喜发财!

2008-02-06T16:53:00.000-08:00

Overheard in San Francisco

2008-01-27T23:23:00.000-08:00

Young Homeless Guy is sitting on the floor with a cardboard sign. Another guy walks by, holding what look like large leftover bags from a restaurant.

Guy With Bags: [stops and offers the bags] would you like something to eat?
Young Homeless Guy: is there garlic or avocado in it?
GWB: I don't think so, why?
YHG: I am allergic to both. Especially avocado: when I eat it, my throat gets all scratchy.

An Unusual Recruiting Pitch

2008-01-26T18:56:00.000-08:00

Women in their sophomore or junior year of college who are thinking about doing research and going to graduate school should read this article (via Andrew Sullivan). Living the life of the mind is very rewarding, and, apparently, the chances of dating male models are not bad either. (If the author could get some mileage out of being an undergrad at Harvard, just imagine what it can do for you to be a grad student at Berkeley!)

Finally!

2008-01-24T17:58:00.000-08:00

After a hiatus of almost four year, the graduate computational complexity course returns to Berkeley.

To get started, I proved Cook's non-deterministic hierarchy theorem, a 1970s result with a beautifully clever proof, which I first learned from Sanjeev Arora. (And that is not very well known.)

Though the full result is more general, say we want to prove that there is a language in NP that cannot be solved by non-deterministic Turing machines in time $o(n^3)$.

(If one does not want to talk about non-deterministic Turing machines, the same proof will apply to other quantitative restrictions on NP, such as bounding the length of the witness and the running time of the verification.)

In the deterministic case, where we want to find a language in P not solvable in time $o(n^3)$, it's very simple. We define the language $L$ that contains all pairs $(\langle T\rangle,x)$ where: (i) $T$ is a Turing machine, (ii) $x$ is a binary string, (iii) $T$ rejects the input $(\langle T\rangle,x)$ within $|(\langle T\rangle,x)|^3$ steps, where $|z|$ denotes the length of a string $z$.

It's easy to see that $L$ is in P, and it is also easy to see that if a machine $M$ could decide this problem in time $\leq n^3$ on all sufficiently large inputs, then the behavior of $M$ on input $\langle M\rangle,x$, for every $x$ long enough, leads to a contradiction.

We could try the same with NP, and define $L$ to contain pairs $(\langle T\rangle,x)$ such that $T$ is a non-deterministic Turing machine that has no accepting path of length $\leq |\langle T\rangle,x|^3$ on input $(\langle T\rangle,x)$. It would be easy to see that $L$ cannot be solved non-deterministically in time $o(n^3)$, but it's hopeless to prove that $L$ is in NP, because in order to solve $L$ we need to decide whether a given non-deterministic Turing machine rejects, which is, in general, a coNP-complete problem.

Here is Cook's argument. Define the function $f(k)$ as follows: $f(1):=2$, $f(k):= 2^{(1+f(k-1))^3}$. Hence, $f(k)$ is a tower of exponentials of height $k$. Now define the language $L$ as follows.

$L$ contains all pairs $\langleT \rangle,0^t$ where $\langle T\rangle$ is a non-deterministic Turing machine and $0^t$ is a sequence of $t$ zeroes such that one of the following conditions is satisfied

There is a $k$ such that $f(k)=t$, and $T$ has no accepting computation on input $\langle T\rangle,0^{1+f(k-1)}$ of running time $\leq (1+(f(k-1))^3$;
$t$ is not of the form $f(k)$ for any $k$, and $T$ has an accepting computation on input $\langle T\rangle,0^{1+t}$ of running time $\leq (t+1)^3$.

Now let's see that $L$ is in NP. When we are given an input $\langle T\rangle,0^t$ we can first check if there is a $k$ such that $f(k)=t$.

If there is, we can compute $t':=f(k-1)$ and deterministically simulate all computations of $T$ on inputs $\langle T\rangle,0^{t'}$ up to running time $t'^3$. This takes time $2^{O(t'^3)}$ which is polynomial in $t$.
Otherwise, we non-deterministically simulate $T$ on input $\langle T\rangle,0^{t+1}$ for up to $(t+1)^3$ steps. (And reject after time-out.)

In either case, we are correctly deciding the language.

Finally, suppose that $L$ could be decided by a non-deterministic Turing machine $M$ running in time $o(n^3)$. In particular, for all sufficiently large $t$, the machine runs in time $\leq t^3$ on input $\langle M\rangle,0^t$.

Choose $k$ to be sufficiently large so that for every $t$ in the interval $1+f(k-1),...,f(k)$ the above property is true.

Now we can see that $M$ accepts $(\langle M\rangle,0^{f(k-1)+1})$ if and only if $M$ accepts $(\langle M\rangle,0^{f(k-1)+2})$ if and only if ... if and only if $M$ accepts $(\langle M\rangle,0^{f(k)})$ if and only if $M$ rejects $(\langle M\rangle,0^{f(k-1)+1})$, and we have our contradiction.

Please, no pigs in the subway

2008-01-19T01:46:00.000-08:00

And that includes you!

I could not figure out what's the item on the bottom left.

Incidentally, the recent spike in the price of pork was a major news item.

Mmmm... Dangerously Delicious...

2008-01-13T06:29:00.001-08:00

Pseudorandomness for Polynomials

2008-01-10T22:29:00.000-08:00

I am currently in Hong Kong for my second annual winter break visit to the Chinese University of Hong Kong. If you are around, come to CUHK on Tuesday afternoon for a series of back-to-back talks by Andrej Bogdanov and me.

First, I'd like to link to this article by Gloria Steinem. (It's old but I have been behind with my reading.) I believe this presidential campaign will bring up serious reflections on issues of gender and race, and I look forward to the rest of it.

Secondly, I'd like to talk about pseudorandomness against low-degree polynomials.

Naor and Naor constructed in 1990 a pseudorandom generator whose output is pseudorandom against tests that compute affine functions in $F_2$. Their construction maps a seed of length $O(\log n /\epsilon)$ into an $n$-bit string in $F_2^n$ such that if $L: F_2^n \to F_2$ is an arbitrary affine function, $X$ is the distribution of outputs of the generator, and $U$ is the uniform distribution over $F_2^n$, we have

(1) $ | Pr [ L(X)=1] - Pr [ L(U)=1] | \leq \epsilon $

This has numerous applications, and it is related to other problems. For example, if $C\subseteq F_2^m$ is a linear error-correcting code with $2^k$ codewords, and if it is such that any two codewords differ in at least a $\frac 12 - \epsilon$ fraction of coordinates, and in at most a $\frac 12 + \epsilon$ fraction, then one can derive from the code a Naor-Naor generator mapping a seed of length $\log m$ into an output of length $k$. (It is a very interesting exercise to figure out how.) Here is another connection: Let $S$ be the (multi)set of outputs of a Naor-Naor generator over all possible seeds, and consider the Cayley graph constructed over the additive group of $F_2^n$ using $S$ as a set of generators. (That is, take the graph that has a vertex for every element of $\{0,1\}^n$, and edge between $u$ and $u+s$ for every $s\in S$, where operations are mod 2 and componentwise.) Then this graph is an expander: the largest eigenvalue is $|S|$, the degree, and all other eigenvalues are at most $\epsilon |S|$ in absolute value. (Here too it's worth figuring out the details by oneself. The hint is that in a Cayley graph the eigenvectors are always the characters, regardless of what generators are chosen.) In turn this means that if we pick $X$ uniformly and $Y$ according to a Naor-Naor distribution, and if $A\subseteq F_2^n$ is a reasonably large set, then the events $X\in A$ and $X+Y \in A$ are nearly independent. This wouldn't be easy to argue directly from the definition (1), and it is an example of the advantages of this connection.

There is more. If $f: \{0,1\}^n \rightarrow \{0,1\}$ is such that the sum of the absolute values of the Fourier coefficients is $t$, $X$ is a Naor-Naor distribution, and $U$ is uniform, we have
$ | Pr [ f(X)=1] - Pr [ f(U)=1] | \leq t \epsilon |$
and so a Naor-Naor distribution is pseudorandom against $f$ too, if $t$ is not too large. This has a number of applications: Naor-Naor distribution are pseudorandom against tests that look only at a bounded number of bits, it is pseudorandom against functions computable by read-once branching programs of width 2, and so on.

Given all these wonderful properties, it is natural to ask whether we can construct generators that are pseudorandom against quadratic polynomials over $F_2^n$, and, in general, low-degree polynomials. This question has been open for a long time. Luby, Velickovic, and Wigderson constructed such a generator with seed length $2^{(\log n)^{1/2}}$, using the Nisan-Wigderson methodology, and this was not improved upon for more than ten years.

When dealing with polynomials, several difficulties arise that are not present when dealing with linear functions. One is the correspondence between pseudorandomness against linear functions and Fourier analysis; until the development of Gowers uniformity there was no analogous analytical tool to reason about pseudorandomness against polynomials (and even Gowers uniformity is unsuitable to reason about very small sets). Another difference is that, in Equation (1), we know that $Pr [L(U)=1] = \frac 12$, except for the constant function (against which, pseudorandomness is trivial). This means that in order to prove (1) it suffices to show that $Pr[L(X)=1] \approx \frac 12$ for every non-constant $L$. When we deal with a quadratic polynomial $p$, the value $Pr [p(U)=1]$ can be all over the place between $1/4$ and $3/4$ (for non-constant polynomials), and so we cannot simply prove that $Pr[p(X)=1]$ is close to a certain known value.

A first breakthrough with this problem came with the work of Bogdanov on the case of large fields. (Above I stated the problem for $F_2$, but it is well defined for every finite field.) I don't completely understand his paper, but one of the ideas is that if $p$ is an absolutely irreducible polynomial (meaning it does not factor even in the algebraic closure of $F$), then $p(U)$ is close to uniform over the field $F$; so to analyze his generator construction in this setting one "just" has to show that $p(X)$ is nearly uniform, where $X$ is the output of his generator. If $p$ factors then somehow one can analyze the construction "factor by factor," or something to this effect. This approach, however, is not promising for the case of small fields, where the absolutely irreducible polynomial $x_1 + x_2 x_3$ has noticeable bias.

The breakthrough for the boolean case came with the recent work of Bogdanov and Viola. Their starting point is the proof that if $X$ and $Y$ are two independent Naor-Naor generators, then $X+Y$ is pseudorandom for quadratic polynomials. To get around the unknown bias problem, they divide the analysis into two cases. First, it is known that, up to affine transformations, a quadratic polynomial can be written as $x_1x_2 + x_3x_4 + \cdots + x_{k-1} x_k$, so, since applying an affine transformation to a Naor-Naor generator gives a Naor-Naor generator, we may assume our polynomial is in this form.

Case 1: if $k$ is small, then the polynomial depends on few variables, and so even just one Naor-Naor distribution is going to be pseudorandom against it;
Case 2: if $k$ is large, then the polynomial has very low bias, that is, $Pr[p(U)] \approx \frac 12$. This means that it is enough to prove that $Pr[p(X+Y)] \approx \frac 12$, which can be done using (i) Cauchy-Schwartz, (ii) the fact that $U$ and $U+X$ are nearly independent if $U$ is uniform and $X$ is Naor-Naor, and (iii) the fact that for fixed $x$ the function $y \rightarrow p(x+y) - p(x)$ is linear.

Now, it would be nice if every degree-3 polynomial could be written, up to affine transformations, as $x_1x_2 x_3 + x_4x_5x_6 + \cdots$, but there is no such characterization, so one has to find the right way to generalize the argument.

In the Bogdanov-Viola paper, they prove

Case 1: if $p$ of degree $d$ is correlated with a degree $d-1$ polynomial, and if $R$ is a distribution that is pseudorandom against degree $d-1$ polynomials, then $R$ is also pseudorandom against $p$;
Case 2: if $p$ of degree $d$ has small Gowers uniformity norm of dimension $d$, then $Pr [p(U)=1] \approx \frac 12$, which was known, and if $R$ is pseudorandom for degree $d-1$ and $X$ is a Naor-Naor distribution, then $Pr[p(R+X)=1] \approx \frac 12$ too.

There is a gap between the two cases, because Case 1 requires correlation with a polynomial of degree $d-1$ and Case 2 requires small Gowers uniformity $U^d$. The Gowers norm inverse conjecture of Green Tao is that a noticeably large $U^d$ norm implies a noticeable correlation with a degree $d-1$ polynomial, and so it fills the gap. The conjecture was proved by Samorodnitsky for $d=3$ in the boolean case and for larger field and $d=3$ by Green and Tao. Assuming the conjecture, the two cases combine to give an inductive proof that if $X_1,\ldots X_d$ are $d$ independent Naor-Naor distributions then $X_1+\ldots+X_d$ is pseudorandom for every degree-$d$ polynomial.

Unfortunately, Green and Tao and Lovett, Meshulam, and Samorodnitsky prove that the Gowers inverse conjecture fails (as stated above) for $d\geq 4$ in the boolean case.

Lovett has given a different argument to prove that the sum of Naor-Naor generators is pseudorandom for low-degree polynomials. His analysis also breaks down in two cases, but the cases are defined based on the largest Fourier coefficient of the polynomial, rather than based on its Gowers uniformity. (Thus, his analysis does not differ from the Bogdanov-Viola analysis for quadratic polynomials, because the dimension-2 Gowers uniformity measures the largest Fourier coefficient, but it differs when $d\geq 3$.) Lovett's analysis only shows that $X_1 +\cdots + X_{2^{d-1}}$ is pseudorandom for degree-$d$ polynomials, where $X_1,\ldots,X_{2^{d-1}}$ are $2^{d-1}$ independent Naor-Naor generators, compared to the $d$ that would have sufficed in the conjectural analysis of Bogdanov and Viola.

The last word on this problem (for now) is this paper by Viola, where he shows that the sum of $d$ independent Naor-Naor generators is indeed pseudorandom for degree-$d$ polynomials.

Again, there is a case analysis, but this time the cases depend on whether or not $Pr [p(U)=1] \approx \frac 12$.

If $p(U)$ is noticeably biased (this corresponds to a small $k$ in the quadratic model case), then it follows from the previous Bogdanov-Viola analysis that a distribution that is pseudorandom against degree $d-1$ polynomials will also be pseudorandom against $p$.

The other case is when $p(U)$ is nearly unbiased, and we want to show
that $p(X_1+\ldots +X_d)$ is nearly unbiased. Note how weak is the assumption, compared to the assumption that $p$ has small dimension-$d$ Gowers norm (in Bogdanov-Viola) or that all Fourier coefficients of $p$ are small (in Lovett). The same three tools that work in the quadratic case, however, work here too, in a surprisingly short proof.

Don Knuth is 70

2008-01-10T01:00:00.000-08:00

Alonzo Church and Alan Turing imagined programming languages and computing machines, and studied their limitations, in the 1930s; computers started appearing in the 1940s; but it took until the 1960s for computer science to become its own discipline, and to provide a common place for the logicians, combinatorialists, electrical engineers, operations researchers, and others, who had been studying the uses and limitations of computers. That was a time when giants were roaming the Earth, and when results that we now see as timeless classics were discovered.

Don Knuth is one of the most revered of the great researchers of that time. A sort of pop-culture icon to a certain geek set (see for example these two xkcd comics here and here, and this story). Beyond his monumental accomplishments, his eccentricities, and humor are the stuff of legends. (Like, say, the fact that he does not use email, or how he optmized the layout of his kitchen.)

As a member of a community whose life is punctuated by twice-yearly conferences, what I find most inspiring about Knuth is his dedication to perfection, whatever time it might take to achieve it.

As the well known story goes, more than forty years ago Knuth was asked to write a book about compilers. As initial drafts started to run into the thousands of pages, it was decided the "book" would become a seven-volume series, The Art of Computer Programming, the first three of which appeared between 1968 and 1973. An unparalleled in-depth treatment of algorithms and data structures, the books defined the field of analysis of algorithms.

At this point Knuth became frustrated with the quality of electronic typesetting systems, and decided he had to take matters in his own hands. In 1977 he started working on what would become TeX and METAFONT, a development that was completed only in 1989. Starting from scratch, he created a complete document preparation system (TeX) which became the universal standard for writing documents with mathematical content, along the way devising new algorithms for formatting paragraphs of texts. To generate the fonts to go with it, he created METAFONT, which is a system that converts a geometric description of a character into a bit-map representation usable by TeX. (New algorithmic work arose from METAFONT too.) And since he was not satisfied with the existing tools available to write a large program involving several non-trivial algorithms, he came up with the notion of "literate programming" and wrote an environment to support it. It is really too bad that he was satisfied enough with the operating system he was using.

One now takes TeX for granted, but try to imagine a world without it. One shudders at the thought. We would probably be writing scientific articles in Word, and I would have probably spent the last month reading STOC submissions written in Comic Sans.

Knuth has made mathematical exposition his life work. We may never see again a work of the breadth, ambition, and success of The Art of Computer Programming, but as theoretical computer science broadens and deepens, it is vital that each generation cherishes the work of accumulating, elaborating, systematizing and synthesizing knowledge, so that we may preserve the unity of our field.

Don Knuth turns 70 tomorrow. I would send him my best wishes by email, but that wouldn't work...

[This post is part of a "blogfest" conceived and coordinated by Jeff Shallit, with posts by Jeff, Scott Aaronson, Mark Chu-Carroll, David Eppstein, Bill Gasarch, Suresh Venkatasubramanian, and Doron Zeilberger.]

Math is for boys, but not in Italy

2007-12-29T12:35:00.000-08:00

Why are women so under-represented in computer science research in the United States? And what can we do about it?

The conventional wisdom is that most of the damage is done in kindergarten or earlier, when parents teach their young sons to play chess, but not their young daughters, when a competitive and aggressive attitude is encouraged in boys and repressed in girls, and so on.

I do subscribe to this theory, but how do I reconcile it with the fact that, as observed by Luca Aceto, women are well represented in the Italian computer science academia? It's not like Italy is a post-gendered feminist utopia, after all.

As someone who has not lived in Italy in 11 years, and who has no training in social sciences, I'd like to offer my uninformed opinions.

For starters, although Italian society can appear shockingly sexist to one used to American political correctness, in practice things are more complex. I have heard Italian women in position of authority complain that they are not treated with the same respect as their male colleagues (an issue that is not very critical in hierarchy-free academia), but I have rarely, if ever, heard an Italian woman say that men are afraid of highly educated, smart women, an issue that seems to come up a lot here in the US. That is, although it may not be considered "feminine" in Italy to be a manager, it is ok to be smart and have a PhD (to the extent that people have any idea what a PhD is).

I'd like my people to take credit for this, but there is actually a "darker" side to this attitude. In Italy, academic research is chocked by a perennial funding crisis. Salaries are very low, and promotions are slow and unpredictable, because of frequent hiring freezes. It is common for a prospective academic to be in his or her mid-30s and still not be in the equivalent of a tenure-track position.

And so, I suspect, academia is something of a "woman's job," because it is ok for a woman to be in a career that is uncertain and does not pay well, but that moves on slowly, allows for maternity leaves, and is personally fulfilling. It is a bit like being an artist, or a writer. A man, however, has to provide for the family and so this is not so good for him.

My spaghetti-sociology may be completely off, but I think it's possible that the representation of women in computer science (and math) in Italy is indeed happening for all the wrong reasons. (A case of two wrongs making a right.)

If I am right, what lessons could we take about attracting more talented women to math, science and engineering in the short term, without having to wait for the revolution to come and for gender roles to be abolished or at least more fairly re-shuffled? Decreasing salaries and abolishing tenure could work, but I would rather not advocate such steps. Some of the proposals that have been around for a while, however, seem entirely reasonable: make the tenure clock more flexible, allow for longer parental leaves, and recognize that the current system, which puts a lot of pressure on people when they are in their late 20s to mid-30s puts a great strain on people who want to have, and actively rear, children before they are in their late 30s. (And that, in the current pre-revolutionary times, this is a concern that hits women disproportionately more than man.) In addition, whatever can be done to decrease a perception of math, science and engineering as "boys' subjects" should be done. I understand that CMU's spectacularly successful initiative to increase women's representation in undergraduate computer science education started from a similar, if more sophisticated, premise.

The Princeton Workshop on Women in Theory

2007-12-20T07:09:00.000-08:00

[I'd like to pass along the following announcement from Tal Rabin. Spread the word. -L.]

We will have a "Women in Theory" student workshop in Princeton on June 14-18, 2008. The goal is to have a great technical program and a chance for the (far too few) women in TCS to get together. Female graduate students are encouraged to apply - we also have a few slots for outstanding CS/math undergraduates and may be able to offer travel support. See http://www.cs.princeton.edu/theory/index.php/Main/WIT08
for more details and list of confirmed speakers.

Italian Professors to Blockade Highways Next Year

2007-12-20T06:52:00.000-08:00

It's never a good sign when the New York Times has an article about Italy. Though they rarely get as bad as the one about the Lady Chatterly of Calitri, there is always a sense that one would get more acute social analysis from a Lonely Planet guide.

Last week's article by Ian Fisher on the Italian malaise was not bad. It starts, inauspiciously, with "[Italy] is the place [...] where people still debate [...] what, really, the red in a stoplight might mean," while, ever since the point system for driver's licenses was introduced, everybody stops at red lights. It is what a stop sign means at an intersection which is a matter of debate. (The debate being on whether or not one should slow down before cutting into incoming traffic.) But the rest of the article competently reports on a series of worrying signs about Italian society, economy, and politics.

In an embarrassing show of provincialism, this has been enough to create the mother of all media storms. For the past seven days, talk shows, newspapers, politicians, and "intellectuals" have done little more than discuss and rebut what "The New York Times Says" about Italy's supposed funk.

I do get myself into a funk when I come to Italy and read newspapers every day. Most of the stories, apart from the one about What The New York Times Says, are too complicated for me to try and summarize, but there is one that has great symbolic value. For several days last week, truck drivers have been on strike, have blocked highways and stopped delivery of gasoline and some food items. In the last round of shuffle of the budget law before it was to be voted by the House (which, amusingly, is called the Room of Representative in Italy) and the Senate, the government added 30 million euros for provisions that benefited truck drivers. This, and a few last-minute other expenses, where compensated by a series of cuts. Research and universities lost 90 million euros. This despite the fact that the Italian government signed a European agreement that sets for all states a goal of spending 3% of their GDP on universities and research, and Italy is currently spending around 1%. This is why, next year, Italian professors should take to highways on their scooters and do a blockade.

On the positive side, the European Research Council has started operations. This is an NSF-like grant-making institution that is going through its first round of funding this year. Italy, at the time of Berlusconi's government, was one of the states who opposed the creation of the ERC, on the grounds that, if I may rephrase, the ERC was going to take money from member states and assign it on the basis of quality, which is something for which the Italian government would not stand. Italian researchers, meanwhile, did very well on this first round of funding, showing that despite all the best efforts of governments of both political sides, quality has not yet been eradicated from Italian universities.

New York in Grainy Pictures

2007-12-14T13:28:00.000-08:00

My three months in New York are over, so no more xiaolongbao at Yeah Shanghai, long rides on the New Jersey Transit trains, seminars on additive combinatorics, and hot pot at Minni's Shabu Shabu for me.

The other night, the traffic information board on 110th and Amsterdam was saying "CCCOOORRR... FFFFFF... AAAUUUU" which is how I too felt about the weather.

This is probably meant to lure in Italian tourists

The Apple store on 5th avenue open at 2:40am (and through the night), because it's never too late (or too early) to buy an iPhone

In the Canal stop of the N-Q-R-W. There were no signs in other languages.

I agree, it's good.

Happy Belated Birthday!

2007-12-11T18:33:00.000-08:00

I just discovered, via CNN, that the Commodore 64 turned 25 last summer.

I received a Commodore 64 as a much appreciated gift for my confirmation, when I was in my first year of high school (9th grade). It was named after its then remarkable 64kB of memory; its operating system and its Basic interpreter fit into an additional 32kB of ROM. It had a graphic and a music processor that were not bad for the time, and it was endlessly fun to play with it. Its Basic language had instructions to read (peek) and write (poke) directly onto memory locations, and this was how pretty much everything was done. To draw on the screen one would set a certain bit of a certain memory location to a certain value to switch to a graphic mode, and then one would directly write on the bitmap. Similarly one could play a note on a certain channel, with a certain waveform for a certain amount of time by setting certain other memory locations. In 6th to 8th grade (middle school) we studied music, which consisted in part of learning how to play a recorder. The least said about my recorder-playing skills the better, but I left 8th grade with a stack of very simplified music scores of famous songs, which I then proceeded to translate into the numerical codes required by the C=64 music card so that I could make it play the songs. I also amused myself with more complicated projects, usually involving the drawing of 3-dimensional objects on the screen.

People that have met me later in life may be surprised to learn that I spent long hours programming for fun. Not that I need to be defensive or anything, and I certainly did not know so then, but, at the time, programming, even in the very basic Basic that came with the computer, was the closest thing I could do to math. Certainly, it was much closer than the "math" I was getting in school, which consisted in learning how to run certain numerical and algebraic algorithms by hand. Indeed I don't think I encountered anything closer to math than programming until the first year of college, when the whole notion of axioms, theorems, proofs, and ``playing a game with meaningless symbols'' was unloaded on me in a course innocuously termed ``Geometry.'' (Nominally a course on linear algebra, the course was a parody of Bourbakism as a teaching style. In the first class the professor came in and said, a vector space is a set with two operations that satisfy the following nine axioms. Now I should like to prove the following proposition... I am not joking when I say that the fact that the elements of a $k$-dimensional vector space are $k$-tuples of numbers came as a revelation near the very end of the course.)

The fact that the ``type'' of a program is similar to a statement and the
implementation of a program is similar to a proof should be familiar to anybody who has written both. In both cases, one needs to break down an idea into basic steps, be very precise about how each step is realized, if a sequence of steps is repeated twice in a similar way one should abstract the similarity, write the abstracted version separately, and then use the abstracted version twice, and so on. The Curry-Howard isomorphism establishes this connection in a formal way, between a certain way of writing proof (say, Gentzen proof system with no cut in intuitionistic logic) and a certain way of writing programs (say, typed $\lambda$-calculus). I know because I once took a course based on the totally awesome book Proofs and Types by Girard, which is out of print but available for free on the web.

But we were talking about the Commodore 64. There was something amazing about a functional computer with an operating system fitting into a few kilobytes, and many people could understand it inside out. One could buy magazines that were in good part devoted to Basic programs that one could copy, typically video games. Naturally, one would then be able to change the game and to see what a reasonably non-trivial program would look like. The operating system I am using now has a source code that is probably millions of lines long, there is probably no person that has a complete understanding of it, and it sometimes does mysterious things. It is also able to handle more than one program running at a time. It was fun to turn on a computer, instantly get a prompt, type 10 PRINT "HELLO WORLD" and then RUN, while now one has to do this. Of course riding a bike is simpler than driving a car which is simpler than piloting an airplane, but they have different ranges.

Under the Curry-Howard isomorphism, programming in the modern sense is more like Algebraic Geometry. One has to spend a lot of time learning how to use an expansive set of libraries, and in one's lifetime it would be impossible to reconstruct how everything works from first principles, but then one has really powerful tools. I prefer the hands-on ethos of Combinatorics, where the big results are not general theorems, but rather principles, or ways of doing things, that one learns by reading other people's papers, and replicating their arguments to apply them to new settings, changing them as needed.

And before I get distracted once more away from what is nominally the subject of this post, happy birthday to the Commodore 64 and to whoever is turning 30 tomorrow.

Time to go back to California?

2007-12-02T14:06:00.000-08:00

Why Mathematics?

2007-11-28T16:10:00.000-08:00

Terry Tao points to a beautiful article written by Michael Harris for the Princeton Companion to Mathematics, titled Why Mathematics, You Might Ask.

The titular question is the point of departure for a fascinating discussion on the foundations of mathematics, on the philosophy of mathematics, on post-modernism, on the "anthropology" approach to social science studies of mathematics, and on what mathematicians think they are doing, and why.

In general, I find articles on philosophical issues in mathematics to be more readable and enlightening when written by mathematicians. Perhaps it's just that they lack the sophistication of the working philosopher, a sophistication which I mistake for unreadability. But I also find that mathematicians tend to bring up issues that matter more to me.

For example, the metaphysical discussions on the "reality" of mathematical objects and the "truth" of theorems are all well and good, but the really interesting questions seem to be different ones.

The formalist view of mathematics, for example, according to which mathematics is the derivation of theorems from axioms via formal proofs, or as Hilbert apparently put it, "a game played according to certain simple rules with meaningless marks on paper," does not begin to capture what mathematics, just as "writing one sentence after another" does not capture what poetry is. (The analogy is due to Giancarlo Rota.) Indeed one of the main fallacies that follow by taking the extreme formalist position as anything more than a self-deprecating joke is to consider mathematical work as tautological. That is, to see a mathematical theorem as implicit in the axioms and so its proof as not a discovery. (Some of the comments in this thread relate to this point.) Plus, the view does not account for the difference between "recreational" mathematics and "real" mathematics, a difference that I don't find it easy to explain in a few words, probably because I don't have a coherent view of what mathematics really is.

It's not quite related, but I am reminded of a conversation I had a long time ago with Professor X about faculty candidate Y.

[Not an actual transcript, but close enough]

X: so what do you think of theory candidate Y?
Me: he is not a theory candidate.
X: but his results have no conceivable application.
Me: there is more to doing theory than proving useless theorems.
X: that's interesting! Tell me more

I enjoyed Harris's suggestion that "ideas" are the basic units of mathematical work, and his semi-serious discussion of whether ideas "exist" and on their importance.

There are indeed a number of philosophical questions about mathematics that I think are extremely interesting and do not seem to figure prominently in the social studies of mathematics.

For example, and totally randomly:

When are two proofs essentially the same, and when are they genuinely different?
What makes a problem interesting? What is the role of connections in this determination?
What makes a theorem deep?
What does it mean when mathematicians say that a certain proof explains something, or when they say that it does not?

Terminology

2007-11-27T20:51:00.000-08:00

Different communities have different traditions for terminology. Mathematicians appropriate common words, like ring, field, scheme, ideal,... and the modern usage of the term bears no connection with the everyday meaning of the word. Physicists have a lot of fun with their sparticles and their strangeness and charm and so on. Theoretical computer scientists, like the military, and NASA, prefer acronyms.

We have some isolated examples of felicitous naming. Expander, for example, is great: it sounds right and it is suggestive of the technical meaning. Extractor is my favorite, combining a suggestion of the meaning with a vaguely threatening sound. I think it's too bad that seedless extractor has come to pass, because it evokes some kind of device to get grape juice. (I was on the losing side that supported deterministic extractor.)

Unfortunate namings are of course more common. Not only is the complexity class PP embarrassing to pronounce, but its name, derived from Probabilistic Polynomial time, is a poor description of it. By analogy with #P and $\oplus$P, it should be called MajP.

I heard the story of a famous (and famously argumentative) computer scientist complaining to one of the authors of the PCP theorem about the term PCP, which stands for Probabilistically Checkable Proof. "I too can define a probabilistic checker for SAT certificates," he supposedly said, "with probability half check the certificate, with probability half accept without looking at it." The point being that the terminology emphasizes a shortcoming of the construction (the probabilistic verification) instead of the revolutionary feature (the constant query complexity). Personally, I would prefer Locally Testable Proof.

Of course we will never change the name of PP or PCP, and the seedless extractors are here to stay, but there is one terminology change for which I'd like to start a campaign.

Naor and Naor constructed in 1990 a pseudorandom generator whose output is secure against linear tests. They called such a generator $\epsilon$-biased if the distinguishing probability of every linear test is at most $\epsilon$. Such generators have proved to be extremely useful in a variety of applications, most recently in the Bogdanov-Viola construction of pseudorandom generators again degree-2 polynomials.

Shall we start calling such generators $\epsilon$-unbiased? Seeing as it is the near lack of bias, rather than its presence, which is the defining feature of such generators?

(I know the reason for the Naor-Naor terminology: zero-bias generator makes perfect sense, while zero-unbiased makes no sense. But how about the fact that it is technically correct to say that the uniform distribution is $\frac {1}{10}$-biased?)

[Update: earlier posts on the same topic here and here]

Impagliazzo Hard-Core Sets via "Finitary Ergodic-Theory"

2007-11-12T12:53:00.000-08:00

In the Impagliazzo hard-core set theorem we are a given a function $g:\{ 0, 1 \}^n \rightarrow \{ 0,1\}$ such that every algorithm in a certain class makes errors at least a $\delta$ fraction of the times when given a random input. We think of $\delta$ as small, and so of $g$ as exhibiting a weak form of average-case complexity. We want to find a large set $H\subseteq \{ 0,1 \}^n$ such that $g$ is average-case hard in a stronger sense when restricted to $H$. This stronger form of average-case complexity will be that no efficient algorithm can make noticeably fewer errors while computing $g$ on $H$ than a trivial algorithm that always outputs the same value regardless of the input. The formal statement of what we are trying to do (see also the discussion in this previous post) is:

Impagliazzo Hard-Core Set Theorem, "Constructive Version"
Let $g:\{0,1\}^n \rightarrow \{0,1\}$ be a boolean function, $s$ be a size parameter, $\epsilon,\delta>0$ be given. Then there is a size parameter $s' = poly(1/\epsilon,1/\delta) \cdot s + exp(poly(1/\epsilon,1/\delta))$ such that the following happens.

Suppose that for every function $f:\{0,1\}^n \rightarrow \{0,1\}$ computable by a circuit of size $s'$ we have

$Pr_{x \in \{0,1\}^n} [ f(x) = g(x) ] \leq 1-\delta$

Then there is a set $H$ such that: (i) $H$ is recognizable by circuits of size $\leq s'$; (ii) $|H| \geq \delta 2^n$, and in fact the number of $x$ in $H$ such that $g(x)=0$ is at least $\frac 12 \delta 2^n$, and so is the number of $x$ in $H$ such that $g(x)=1$; and (iii) for every $f$ computable by a circuit of size $\leq s$,

$Pr_{x\in H} [ g(x) = f(x) ] \leq max \{ Pr_{x\in H}[ g(x) = 0] , Pr_{x\in H} [g(x)=1] \} + \epsilon$

Our approach will be to look for a "regular partition" of $\{0,1\}^n$. We shall construct a partition $P= (B_1,\ldots,B_m)$ of $\{0,1\}^n$ such that: (i) given $x$, we can efficiently compute what is the block $B_i$ that $x$ belongs to; (ii) the number $m$ of blocks does not depend on $n$; (iii) $g$ restricted to most blocks $B_i$ behaves like a random function of the same density. (By "density" of a function we mean the fraction of inputs on which the function evaluates to one.)

In particular, we will use the following form of (iii): for almost all the blocks $B_i$, no algorithm has advantage more than $\epsilon$ over a constant predictor in computing $g$ in $B_i$.

Let $M_0$ be the union of all majority-0 blocks (that is, of blocks $B_i$ such that $g$ takes the value 0 on a majority of elements of $B_i$) and let $M_1$ be the union of all majority-1 blocks.

I want to claim that no algorithm can do noticeably better on $M_0$ than the constant algorithm that always outputs 0. Indeed, we know that within (almost) all of the blocks that compose $M_0$ no algorithm can do noticeably better than the always-0 algorithm, so this must be true for a stronger reason for the union. The same is true for $M_1$, with reference to the constant algorithm that always outputs 1. Also, if the partition is efficiently computable, then(in a non-uniform setting) $M_0$ and $M_1$ are efficiently recognizable. It remains to argue that either $M_0$ or $M_1$ is large and not completely unbalanced.

Recalling that we are in a non-uniform setting (where by "algorithms" we mean "circuits") and that the partition is efficiently computable, the following is a well defined efficient algorithm for attempting to compute $g$:

Algorithm. Local Majority
On input $x$:
determine the block $B_i$ that $x$ belongs to;
output $1$ if $Pr_{z\in B_i} [g(z)=1] \geq \frac 12$;
otherwise output $0$

(The majority values of $g$ in the various blocks are just a set of $m$ bits that can be hard-wired into the circuit.)

We assumed that every efficient algorithm must make at least a $\delta$ fraction of errors. The set of $\geq \delta 2^n$ inputs where the Local Majority algorithm makes mistakes is the union, over all blocks $B_i$, of the "minority inputs" of the block $B_i$. (If $b$ is the majority value of $g$ in a block $B$, then the "minority inputs" of $B$ are the set of inputs $x$ such that $g(x) = 1-b$.)

Let $E_0$ be the set of minority inputs (those where our algorithm makes a mistake) in $M_0$ and $E_1$ be the set of minority inputs in $M_1$. Then at least one of $E_0$ and $E_1$ must have size at least $\frac {\delta}{2} 2^n$, because the size of their union is at least $\delta 2^n$. If $E_b$ has size at least $\frac {\delta}{2} 2^n$, then $M_b$ has all the properties of the set $H$ we are looking for.

It remains to construct the partition. We describe an iterative process to construct it. We begin with the trivial partition $P = (B_1)$ where $B_1 = \{ 0,1\}^n$. At a generic step of the construction, we have a partition $P = (B_1,\ldots,B_m)$, and we consider $M_0, M_1,E_0,E_1$ as above. Let $b$ be such that $E_b \geq \frac 12 \delta 2^n$. If there is no algorithm that has noticeable advantage in computing $g$ over $M_b$, we are done. Otherwise, if there is such an algorithm $f$, we refine the partition by splitting each block according to the values that $f$ takes on the elements of the block.

After $k$ steps of this process, the partition has the following form: there are $k$ functions $f_1,\ldots,f_k$ and each of the (at most) $2^k$ blocks of the partition corresponds to a bit string $b_1,\ldots,b_k$ and it contains all inputs $x$ such that $f_1(x)=b_1,\ldots,f_k(x)=b_k$. In particular, the partition is efficiently computable.

We need to argue that this process terminates with $k=poly(1/\epsilon,1/\delta)$. To this end, we define a potential function that measures the "imbalance" of $g$ inside the blocks the partition

$\Psi(B_1,\ldots,B_m) := \sum_{i=1}^m \frac {|B_i|}{2^n} \left( Pr_{x\in B_i} [g(x) = 1] \right)^2 $

and we can show that this potential function increases by at least $poly(\epsilon,\delta)$ at each step of the iteration. Since the potential function can be at most 1, the bound on the number of iterations follows.

A reader familiar with the proof of the Szemeredi Regularity Lemma will recognize the main ideas of iterative partitioning, of using a "counterexample" to the regularity property required of the final partition to do a refinement step, and of using a potential function argument to bound the number of refinement steps.

In which way can we see them as "finitary ergodic theoretic" techniques? As somebody who does not know anything about ergodic theory, I may not be in an ideal position to answer this question. But this kind of difficulty has not stopped me before, so I may attempt to answer this question in a future post.

The December Issue of the Notices of the AMS

2007-11-09T13:53:00.000-08:00

The December issue of the Notices of the AMS is now available online, and it includes letters written by Oded Goldreich, Boaz Barak, Jonathan Katz, and Hugo Krawczyk in response to Neal Koblitz's article which appeared in the September issue.

Despite this, the readers of the Notices remain the losers in this "controversy." Koblitz's petty personal attacks and straw man arguments appeared in the same space that is usually reserved, in the Notices, for expository articles and obituaries of mathematicians. It is from those pages that I learned about the Kakeya problem and about the life of Grothendieck (who, I should clarify, is not dead, except perhaps in Erdos' use of the word).

I find it strange enough that Koblitz would submit his piece to such a venue, but I find it as mind-boggling that the editors would run his piece as if they had commissioned Grothendieck's biographical article to a disgruntled ex-lover, who would focus most of the article on fabricated claims about his personal hygiene.

I can only hope that the editors will soon run on those pages one or more expository articles on modern cryptography, not as rebuttals to Koblitz's piece (which has already been discussed more than enough), but as a service to the readers.

And while I am on the subject of Notices article, let me move on to this article on how to write papers.

All beginning graduate students find the process of doing research mystifying, and I do remember feeling that way. (Not that such feelings have changed much in the intervening years.) One begins with a sense of hopelessness, how am I going to solve a problem that people who know much more than I do and who are smarter than me have not been able to solve?; then a breakthrough comes, out of nowhere, and one wonders, how is this ever going to happen again? Finally it's time to write up the results, and mathematical proofs definitely don't write themselves, not to mention coherent and compelling introductory sections. I think it's great when more experienced scholars take time to write advice pieces that can help students navigate these difficulties. And the number of atrociously badly written papers in circulation suggests that such pieces are good not just for students, but for many other scholars as well.

But I find that advice on "how to publish," rather than "how to write well" (like advice on "how to get a job" rather than "how to do research") misses the point (I am thinking of one of the few times I thought Lance Fortnow gave bad advice). For this reason, I found the first section of the Notices article jarring, and the following line (even if it was meant as a joke) made me cringe

I have written more than 150 articles myself. (...) I have never written an article and then been unable to publish it.

I think that this calls for an Umeshism in response.

The Impagliazzo Hard-Core-Set Theorem

2007-11-06T13:45:00.001-08:00

The Impagliazzo hard-core set theorem is one of the bits of magic of complexity theory. Say you have a function $g:\{ 0, 1 \}^n \rightarrow \{ 0,1\}$ such that every efficient algorithm makes errors at least $1%$ of the times when computing $g$ on a random input. (We'll think of $g$ as exhibiting a weak form of average-case complexity.) Clearly, different algorithms will fail on a different $1%$ of the inputs, and it seems that, intuitively, there should be functions for which no particular input is harder than any particular other input, per se. It's just that whenever you try to come up with an algorithm, some set of mistakes, dependent on the algorithmic technique, will arise.

As a good example, think of the process of generating $g$ at random, by deciding for every input $x$ to set $g(x)=1$ with probability $99%$ and $g(x)=0$ with probability $1%$. (Make the choices independently for different inputs.) With very high probability, every efficient algorithm fails with probability at least about $1%$, but, if we look at every efficiently recognizable large set $H$, we see that $g$ takes the value 1 on approximately $99%$ of the elements of $H$, and so the trivial algorithm that always outputs 1 has a pretty good success probability.

Consider, however, the set $H$ of size $\frac {2}{100} 2^n$ that you get by taking the $\approx \frac{1}{100} 2^n$ inputs $x$ such that $g(x)=0$ plus a random sample of $\frac{1}{100} 2^n$ inputs $x$ such that $g(x)=1$. Then we can see that no efficient algorithm can compute $g$ on much better than $50%$ of the inputs of $H$. This is the highest form of average-case complexity for a boolean function: on such a set $H$ no algorithm does much better in computing $g$ than an algorithm that makes a random guess.

The Impagliazzo hard-core theorem states that it is always possible to find such a set $H$ where the average-case hardness is "concentrated." Specifically, it states that if every efficient algorithm fails to compute $g$ on a $\geq \delta$ fraction of inputs, then there is a set $H$ of size $\geq \delta 2^n$ such that every efficient algorithm fails to compute $g$ on at least a $\frac 12 - \epsilon$ fraction of the elements of $H$. This is true for every $\epsilon,\delta$, and if "efficient" is quantified as "circuits of size $s$" in the premise, then "efficient" is quantified as "circuits of size $poly(\epsilon,\delta) \cdot s$" in the conclusion.

The example of the biased random function given above implies that, if one wants to prove the theorem for arbitrary $g$, then the set $H$ cannot be efficiently computable itself. (The example does not forbid, however, that $H$ be efficiently computable given oracle access to $g$, or that a random element of $H$ be samplable given a sampler for the distribution $(x,g(x))$ for uniform $x$.)

A number of proofs of the hard core theorem are known, and connections have been found with the process of boosting in learning theory and with the construction and the decoding of certain error-correcting codes. Here is a precise statement.

Impagliazzo Hard-Core Set Theorem
Let $g:\{0,1\}^n \rightarrow \{0,1\}$ be a boolean function, $s$ be a size parameter, $\epsilon,\delta>0$ be given. Then there is a $c(\epsilon,\delta) = poly(1/\epsilon,1/\delta)$ such that the following happens.

Suppose that for every function $f:\{0,1\}^n \rightarrow \{0,1\}$ computable by a circuit of size $\leq c\cdot s$ we have

$Pr_{x \in \{0,1\}^n} [ f(x) = g(x) ] \leq 1-\delta$

Then there is a set $H$ of size $\geq \delta 2^n$ such that for every function $f$ computable by a circuit of size $\leq s$ we have

$Pr_{x\in H} [ f(x) = g(x) ] \leq \frac 12 + \epsilon$

Using the "finitary ergodic theoretic" approach of iterative partitioning, we (Omer Reingold, Madhur Tulsiani, Salil Vadhan and I) are able to prove the following variant.

Impagliazzo Hard-Core Set Theorem, "Constructive Version"
Let $g:\{0,1\}^n \rightarrow \{0,1\}$ be a boolean function, $s$ be a size parameter, $\epsilon,\delta>0$ be given. Then there is a $c(\epsilon,\delta) = exp(poly(1/\epsilon,1/\delta))$ such that the following happens.

Suppose that for every function $f:\{0,1\}^n \rightarrow \{0,1\}$ computable by a circuit of size $\leq c\cdot s$ we have

$Pr_{x \in \{0,1\}^n} [ f(x) = g(x) ] \leq 1-\delta$

Then there is a set $H$ such that: (i) $H$ is recognizable by circuits of size $\leq c\cdot s$; (ii) $|H| \geq \delta 2^n$, and in fact the number of $x$ in $H$ such that $g(x)=0$ is at least $\frac 12 \delta 2^n$, and so is the number of $x$ in $H$ such that $g(x)=1$; and (iii) for every $f$ computable by a circuit of size $\leq s$,

$Pr_{x\in H} [ g(x) = f(x) ] \leq max \{ Pr_{x\in H}[ g(x) = 0] , Pr_{x\in H} [g(x)=1] \} + \epsilon$

The difference is that $H$ is now an efficiently recognizable set (which is good), but we are not able to derive the same strong average-case complexity of $g$ in $H$ (which, as discussed as the beginning, is impossible in general). Instead of proving that a "random guess algorithm" is near-optimal on $H$, we prove that a "fixed answer algorithm" is near-optimal on $H$. That is, instead of saying that no algorithm can do better than a random guess, we say that no algorithm can do better than either always outputting 0 or always outputting 1. Note that this conclusion is meaningless if $g$ is, say, always equal to 1 on $H$, but in our construction we have that $g$ is not exceedingly biased on $H$, and if $\epsilon < \delta/2$, say, then the conclusion is quite non-trivial.

One can also find a set $H'$ with the same type of average-case complexity as in the original Impagliazzo result by putting into $H'$ a $\frac 12 \delta 2^n$ size sample of elements $x$ of $H$ such that $g(x)=0$ and an equal size sample of elements of $H$ such that $g$ equals 1. (Alternatively, put in $H'$ all the elements of $H$ on which $g$ achieves the minority value of $g$ in $H$, then add a random sample of as many elements achieving the majority value.) Then we recover the original statement except that $c(\epsilon,\delta)$ is exponential instead of polynomial.

Coming up next, the proof of the "constructive hard core set theorem" and my attempt at explaining what the techniques have to do with "finitary ergodic theory."

Harder, Better, Faster, Stronger

2007-11-03T14:58:00.000-07:00

An amazing video to Daft Punk's Harder, Better, Faster, Stronger

Don't be discouraged by the slow first minute; it does get better, faster, and harder.

Doing the same with a different Daft Punk song, however, can be less impressive.

The "Complexity Theory" Proof of a Theorem of Green-Tao-Ziegler

2007-11-01T10:51:00.000-07:00

We want to prove that a dense subset of a pseudorandom set is indistinguishable from a truly dense set.

Here is an example of what this implies: take a pseudorandom generator of output length $n$, choose in an arbitrary way a 1% fraction of the possible seeds of the generator, and run the generator on a random seed from this restricted set; then the output of the generator is indistinguishable from being a random element of a set of size $\frac 1 {100} \cdot 2^n$.

(Technically, the theorem states the existence of a distribution of min-entropy $n - \log_2 100$, but one can also get the above statement by standard "rounding" techniques.)

As a slightly more general example, if you have a generator $G$ mapping a length-$t$ seed into an output of length $n$, and $Z$ is a distribution of seeds of min-entropy at least $t-d$, then $G(Z)$ is indistinguishable from a distribution of min-entropy $n-d$. (This, however, works only if $d = O(\log n)$.)

It's time to give a formal statement. Recall that we say that a distribution $D$ is $\delta$-dense in a distribution $R$ if

$\forall x. Pr[R=x] \geq \delta \cdot Pr [D=x]$

(Of course I should say "random variable" instead of "distribution," or write things differently, but we are between friends here.)

We want to say that if $F$ is a class of tests, $R$ is pseudorandom according to a moderately larger class $F'$, and $D$ is $\delta$-dense in $R$, then there is a distribution $M$ that is indistinguishable from $D$ according to $F$ and that is $\delta$-dense in the uniform distribution.

The Green-Tao-Ziegler proof of this result becomes slightly easier in our setting of interest (where $F$ contains boolean functions) and gives the following statement:

Theorem (Green-Tao-Ziegler, Boolean Case)
Let $\Sigma$ be a finite set, $F$ be a class of functions $f:\Sigma \to \{0,1\}$, $R$ be a distribution over $\Sigma$, $D$ be a $\delta$-dense distribution in $R$, $\epsilon>0$ be given.

Suppose that for every $M$ that is $\delta$-dense in $U_\Sigma$ there is an $f\in F$ such that
$| Pr[f(D)=1] - Pr[f(M)] = 1| >\epsilon$

Then there is a function $h:\Sigma \rightarrow \{0,1\}$ of the form $h(x) = g(f_1(x),\ldots,f_k(x))$ where $k = poly(1/\epsilon,1/\delta)$ and $f_i \in F$ such that
$| Pr [h(R)=1] - Pr [ h(U_\Sigma) =1] | > poly(\epsilon,\delta)$

Readers should take a moment to convince themselves that the above statement is indeed saying that if $R$ is pseudorandom then $D$ has a model $M$, by equivalently saying that if no model $M$ exists then $R$ is not pseudorandom.

The problem with the above statement is that $g$ can be arbitrary and, in particular, it can have circuit complexity exponential in $k$, and hence in $1/\epsilon$.

In our proof, instead, $g$ is a linear threshold function, realizable by a $O(k)$ size circuit. Another improvement is that $k=poly(1/\epsilon,\log 1/\delta)$.

Here is the proof by Omer Reingold, Madhur Tulsiani, Salil Vadhan, and me. Assume $F$ is closed under complement (otherwise work with the closure of $F$), then the assumption of the theorem can be restated without absolute values

for every $M$ that is $\delta$-dense in $U_\Sigma$ there is an $f\in F$ such that
$Pr[f(D)=1] - Pr[f(M) = 1] >\epsilon$

We begin by finding a "universal distinguisher."

Claim
There is a function $\bar f:\Sigma \rightarrow [0,1]$ which is a convex combination of functions from $F$ and such that that for every $M$ that is $\delta$-dense in $U_\Sigma$,
$E[\bar f(D)] - E[\bar f(M)] >\epsilon$

This can be proved via the min-max theorem for two-players games, or, equivalently, via linearity of linear programming, or, like an analyst would say, via the Hahn-Banach theorem.

Let now $S$ be the set of $\delta |\Sigma|$ elements of $\Sigma$ where $\bar f$ is largest. We must have
(1) $E[\bar f(D)] - E[\bar f(U_S)] >\epsilon$
which implies that there must be a threshold $t$ such that
(2) $Pr[\bar f(D)\geq t] - Pr[\bar f(U_S) \geq t] >\epsilon$
So we have found a boolean distinguisher between $D$ and $U_S$. Next,
we claim that the same distinguisher works between $R$ and $U_\Sigma$.

By the density assumption, we have
$Pr[\bar f(R)\geq t] \geq \delta \cdot Pr[\bar f(D) \geq t]$

and since $S$ contains exactly a $\delta$ fraction of $\Sigma$, and since the condition $\bar f(x) \geq t$ always fails outside of $S$ (why?), we then have
$Pr[\bar f(U_\Sigma)\geq t] = \delta \cdot Pr[\bar f(U_S) \geq t]$
and so
(3) $Pr[\bar f(R)\geq t] - Pr[\bar f(U_\Sigma) \geq t] >\delta \epsilon $

Now, it's not clear what the complexity of $\bar f$ is: it could be a convex combination involving all the functions in $F$. However, by Chernoff bounds, there must be functions $f_1,\ldots,f_k$ with $k=poly(1/\epsilon,\log 1/\delta)$ such that $\bar f(x)$ is well approximated by $\sum_i f_i(x) / k$ for all $x$ but for an exceptional set having density less that, say, $\delta\epsilon/10$, according to both $R$ and $U_\Sigma$.

Now $R$ and $U_\Sigma$ are distinguished by the predicate $\sum_{i=1}^k f_i(x) \geq tk$, which is just a linear threshold function applied to a small set of functions from $F$, as promised.

Actually I have skipped an important step: outside of the exceptional set, $\sum_i f_i(x)/k$ is going to be close to $\bar f(x)$ but not identical, and this could lead to problems. For example, in (3) $\bar f(R)$ might typically be larger than $t$ only by a tiny amount, and $\sum_i f_i(x)/k$ might consistently underestimate $\bar f$ in $R$. If so, $Pr [ \sum_{i=1}^k f_i(R) \geq tk ]$ could be a completely different quantity from $Pr [\bar f(R)\geq t]$.

To remedy this problem, we note that, from (1), we can also derive the more "robust" distinguishing statement
(2') $Pr[\bar f(D)\geq t+\epsilon/2] - Pr[\bar f(U_S) \geq t] >\epsilon/2$
from which we get
(3') $Pr[\bar f(R)\geq t+\epsilon/2] - Pr[\bar f(U_\Sigma) \geq t] >\delta \epsilon/2 $

And now we can be confident that even replacing $\bar f$ with an approximation we still get a distinguisher.

The statement needed in number-theoretic applications is stronger in a couple of ways. One is that we would like $F$ to contain bounded functions $f:\Sigma \rightarrow [0,1]$ rather than boolean-valued functions. Looking back at our proof, this makes no difference. The other is that we would like $h(x)$ to be a function of the form $h(x) = \Pi_{i=1}^k f_i(x)$ rather than a general composition of functions $f_i$. This we can achieve by approximating a threshold function by a polynomial of degree $poly(1/\epsilon,1/\delta)$ using the Weierstrass theorem, and then choose the most distinguishing monomial. This gives a proof of the following statement, which is equivalent to Theorem 7.1 in the Tao-Ziegler paper.

Theorem (Green-Tao-Ziegler, General Case)
Let $\Sigma$ be a finite set, $F$ be a class of functions $f:\Sigma \to [0,1]$, $R$ be a distribution over $\Sigma$, $D$ be a $\delta$-dense distribution in $R$, $\epsilon>0$ be given.

Suppose that for every $M$ that is $\delta$-dense in $U_\Sigma$ there is an $f\in F$ such that
$| Pr[f(D)=1] - Pr[f(M)] = 1| >\epsilon$

Then there is a function $h:\Sigma \rightarrow \{0,1\}$ of the form $h(x) = \Pi_{i=1}^k f_i(x)$ where $k = poly(1/\epsilon,1/\delta)$ and $f_i \in F$ such that
$| Pr [f(R)=1] - Pr [ f(U_\Sigma) =1] | > exp(-poly(1/\epsilon,1/\delta))$

In this case, we too lose an exponential factor. Our proof, however, has some interest even in the number-theoretic setting because it is somewhat simpler than and genuinely different from the original one.

Dense Subsets of Pseudorandom Sets

2007-10-30T18:39:00.000-07:00

The Green-Tao theorem states that the primes contain arbitrarily long arithmetic progressions; its proof can be, somewhat inaccurately, broken up into the following two steps:

Thm1: Every constant-density subset of a pseudorandom set of integers contains arbitrarily long arithmetic progressions.

Thm2: The primes have constant density inside a pseudorandom set.

Of those, the main contribution of the paper is the first theorem, a "relative" version of Szemeredi's theorem. In turn, its proof can be (even more inaccurately) broken up as

Thm 1.1: For every constant density subset D of a pseudorandom set there is a "model" set M that has constant density among the integers and is indistinguishable from D.

Thm 1.2 (Szemeredi) Every constant density subset of the integers contains arbitrarily long arithmetic progressions, and many of them.

Thm 1.3 A set with many long arithmetic progressions cannot be indistinguishable from a set with none.

Following this scheme is, of course, easier said than done. One wants to work with a definition of pseudorandomness that is weak enough that (2) is provable, but strong enough that the notion of indistinguishability implied by (1.1) is in turn strong enough that (1.3) holds. From now on I will focus on (1.1), which is a key step in the proof, though not the hardest.

Recently, Tao and Ziegler proved that the primes contain arbitrarily long "polynomial progressions" (progressions where the increments are given by polynomials rather than linear functions, as in the case of arithmetic progressions). Their paper contains a very clean formulation of (1.1), which I will now (accurately, this time) describe. (It is Theorem 7.1 in the paper. The language I use below is very different but equivalent.)

We fix a finite universe $\Sigma$; this could be $\{ 0,1\}^n$ in complexity-theoretic applications or $Z/NZ$ in number-theoretic applications. Instead of working with subsets of $\Sigma$, it will be more convenient to refer to probability distributions over $\Sigma$; if $S$ is a set, then $U_S$ is the uniform distribution over $S$. We also fix a family $F$ of "easy" function $f: \Sigma \rightarrow [0,1]$. In a complexity-theoretic applications, this could be the set of boolean functions computed by circuits of bounded size. We think of two distributions $X,Y$ as being $\epsilon$-indistinguishable according to $F$ if for every function $f\in F$ we have

$| E [f(X)] - E[f(Y)] | \leq \epsilon$

and we think of a distribution as pseudorandom if it is indistinguishable from the uniform distribution $U_\Sigma$. (This is all standard in cryptography and complexity theory.)

Now let's define the natural analog of "dense subset" for distributions. We say that a distribution $A$ is $\delta$-dense in $B$ if for every $x\in \Sigma$ we have

$Pr [ B=x] \geq \delta Pr [A=x]$

Note that if $B=U_T$ and $A=U_S$ for some sets $S,T$, then $A$ is $\delta$-dense in $B$ if and only if $S\subseteq T$ and $|S| \geq \delta |T|$.

So we want to prove the following:

Theorem (Green, Tao, Ziegler)
Fix a family $F$ of tests and an $\epsilon>0$; then there is a "slightly larger" family $F'$ and an $\epsilon'>0$ such that if $R$ is an $\epsilon'$-pseudorandom distribution according to $F'$ and $D$ is $\delta$-dense in $R$, then there is a distribution $M$ that is $\delta$-dense in $U_\Sigma$ and that is $\epsilon$-indistinguishable from $D$ according to $F$.

[The reader may want to go back to (1.1) and check that this is a meaningful formalization of it, up to working with arbitrary distributions rather than sets. This is in fact the "inaccuracy" that I referred to above.]

In a complexity-theoretic setting, we would like to say that if $F$ is defined as all functions computable by circuits of size at most $s$, then $\epsilon'$ should be $poly (\epsilon,\delta)$ and $F'$ should contain only functions computable by circuits of size $s\cdot poly(1/\epsilon,1/\delta)$. Unfortunately, if one follows the proof and makes some simplifications asuming $F$ contains only boolean functions, one sees that $F'$ contains functions of the form $g(x) = h(f_1(x),\ldots,f_k(x))$, where $f_i \in F$, $k = poly(1/\epsilon,1/\delta)$, and $h$ could be arbitrary and, in general, have circuit complexity exponential in $1/\epsilon$ and $1/\delta$. Alternatively one may approximate $h()$ as a low-degree polynomial and take the "most distinguishing monomial." This will give a version of the Theorem (which leads to the actual statement of Thm 7.1 in the Tao-Ziegler paper) where $F'$ contains only functions of the form $\Pi_{i=1}^k f_i(x)$, but then $\epsilon'$ will be exponentially small in $1/\epsilon$ and $1/\delta$. This means that one cannot apply the theorem to "cryptographically strong" notions of pseudorandomness and indistinguishability, and in general to any setting where $1/\epsilon$ and $1/\delta$ are super-logarithmic (not to mention super-linear).

This seems like an unavoidable consequence of the "finitary ergodic theoretic" technique of iterative partitioning and energy increment used in the proof, which always yields at least a singly exponential complexity.

Omer Reingold, Madhur Tulsiani, Salil Vadhan and I have recently come up with a different proof where both $\epsilon'$ and the complexity of $F'$ are polynomial. This gives, for example, a new characterization of the notion of pseudoentropy. Our proof is quite in the spirit of Nisan's proof of Impagliazzo's hard-core set theorem, and it is relatively simple. We can also deduce a version of the theorem where, as in Green-Tao-Ziegler, $F'$ contains only bounded products of functions in $F$. In doing so, however, we too incur an exponential loss, but the proof is somewhat simpler and demonstrates the applicability of complexity-theoretic techniques in arithmetic combinatorics.

Since we can use (ideas from) a proof of the hard core set theorem to prove the Green-Tao-Ziegler result, one may wonder whether one can use the "finitary ergodic theory" techniques of iterative partitioning and energy increment to prove the hard-core set theorem. Indeed, we do this too. In our proof, the reduction loses a factor that is exponential in certain parameters (while other proofs are polynomial), but one also gets a more "constructive" result.

If readers can stomach it, a forthcoming post will describe the complexity-theory-style proof of the Green-Tao-Ziegler result as well as the ergodic-theory-style proof of the Impagliazzo hard core set theorem.

Discovering the Cyber-Transformations

2007-10-25T10:40:00.000-07:00

If memory serves me well, I have attended all STOC and FOCS conferences since STOC 1997 in El Paso, except STOC 2002 in Montreal (for visa problems), which should add up to 21 conferences. In most of those conferences I have also attended the "business meeting." This is a time when attendees convene after dinner, have beer, the local organizers talk about their local organization, the program committee chair talks about how they put the program together ("papers were submitted, then we reviewed them, finally we accepted some of those. Let me show you twenty slides of meaningless statistics about said papers"), organizers of future conferences talk about their ongoing organizing, David Johnson raises issues to be discussed, and so on. The SODA drinking game gives a good idea of what goes on.

A fixture of business meetings is also a presentation of the state of National Science Foundation (NSF) funding for theory in the US. In the first several conferences I attended, the NSF program director for theory would take the podium, show a series of incomprehensible slides, and go something like "there is no money; you should submit a lot of grant applications; I will reject all applications because there is no money, but low acceptance rates could bring us more money in future years; you should apply to non-theory programs, because there is no money in theory, but don't make it clear you are doing theory, otherwise they'll send your proposal to me, and I have no money. In conclusion, I have no money and we are all doomed."

Things hit rock bottom around 2004, when several issues (DARPA abandoning basic research, the end of the NSF ITR program, a general tightening of the NSF budget at a time of increased student tuition, a change in NSF accounting system requiring multi-year grants to be funded entirely from the budget of the year of the award, ....) conspired to create a disastrous funding season. At that point several people in the community, with Sanjeev Arora playing a leading role, realized that something had to be done to turn things around. A SIGACT committee was formed to understand what had gone wrong and how to repair it.

I don't know if it is an accurate way of putting it, but my understanding is that our community had done a very bad job in publicizing its results to a broader audience. Indeed I remember, in my job interviews, a conversation that went like "What do you do?" "Complexity theory" "Structural complexity or descriptive complexity?" "??". (I also got a "What complexity classes do you study?") And I understand that whenever people from the SIGACT committee went to talk to NSF higher-ups about theory, everybody was interested and the attitude was almost "why haven't you told us about this stuff before?"

For various reasons, it is easier at NSF to put funding into a new initiative than to increase funding of an existing one, and an idea that came up early on was to fund an initiative on "theory as a lens for the sciences," to explore work in economics, quantum mechanics, biology, statistical physics, etc., where the conceptual tools of theoretical computer science are useful to even phrase the right questions, as well as work towards their solution. This idea took on a life of its own, grew much more broad than initially envisioned (so that the lens thing is now a small part of it), received an appropriately cringe-inducing name, and is now the Cyber-Enabled Discovery and Innovation (CDI) program, that is soon accepting its first round of submissions.

Thanks to the work that Bill Steiger put in as program director in the last year and a half, and to the efforts of the SIGACT committee, the outlook for theory funding is now much optimistic.

At the FOCS 2007 business meeting last Monday, Bill talked about the increase in funding that happened under his watch, Sanjeev Arora talked about the work of the committee and the new funding opportunities (of which CDI is only one). In addition, as happened a few times in the last couple of years, Mike Foster from NSF gave his own, generally theory-friendly, presentation. Mike is a mid-level director at NSF (one or two levels above the theory program), and the regular presence of people in his position at STOC and FOCS is, I think, without precedent before 2005. (Or at least between 1997 and 2004.)

The NSF is relatively lean, efficient and competent for being a federal bureaucracy, but it is still a federal bureaucracy, with its quirks.

A few years ago, it started a much loathed requirement to explicitly state the "broader impact" of any proposed grant. I actually don't mind this requirement: it does not ask to talk about "applications," but rather of all the important research work that is not just establishing technical result. Disseminating results, for example, writing notes, expository work, and surveys and making them available, bringing research-level material to freshmen in a new format, doing outreach, doing something to increase representation of women and minority, and so on.

As reported by Sanjeev Arora in his presentation, however, NSF is now requiring to state how the research in a given proposal is "transformative." (I just got a spelling warning after typing it.) I am not sure this makes any sense. The person sitting next to me commented, "Oh no, the goal of my research is always to maintain the status quo."

The Next Viral Videos

2007-10-25T10:30:00.000-07:00

Back in August, Boaz Barak and Moses Charikar organized a two-day course on additive combinatorics for computer scientists in Princeton. Boaz and Avi Wigderson spoke on sum-product theorems and their applications, and I spoke on techniques in the proofs of Szemeredi's theorem and their applications. As an Australian model might say, that's interesting!

Videos of the talks are now online. The quality of the audio and video is quite good, you'll have to decide for yourself on the quality of the lectures. The schedule of the event was grueling, and in my last two lectures (on Gowers uniformity and applications) I am not very lucid. In earlier lectures, however, I am merely sleep deprived -- I can be seen falling asleep in front of the board a few times. Boaz's and Avi's lectures, however, are flawless.

Best Tutorials Ever

2007-10-21T10:51:00.000-07:00

FOCS 2007 started yesterday in Providence with a series of tutorials.

Terry Tao gave a talk similar to the one he gave in Madrid, discussing the duality between pseudorandomness and efficiency which is a way to give a unified view of techniques coming from analysis, combinatorics and ergodic theory.

In typical such results, one has a set $F$ of ``simple'' functions (for example linear, or low-degree polynomials, or, in conceivable complexity-theoretic applications, functions of low circuit complexity) and one wants to write an arbitrary function $g$ as

$ g(x) = g_{pr} (x) + g_{str} (x) + g_{err} (x) $

where $g_{pr}$ is pseudorandom with respect to the ``distinguishers'' in $F$, $g_{str}$ is a ``simple combination'' of functions from $\cal F$, and $g_{err}$ accounts for a possible small approximation error. There are a number of ways to instantiate this general template, as can be seen on the accompanying notes, and it is nice to see how even the Szemeredi regularity lemma can be fit into this template. (The ``functions'' are adjacency matrices of graphs, and the ``efficient'' functions are complete bipartite subgraphs.)

Dan Boneh spoke on pairing-based cryptography, an idea that has grown into a whole, rich, area, with specialized conferences and, according to Google Scholar, 1,200+ papers published so far. In this setting one has a group $G$ (for example points on an elliptic curve) such that there is a mapping $e: G X G \rightarrow G_T$ that takes pairs of elements of $G$ into an element of another group $G_T$ satisfying a bilinearity condition. (Such a mapping is a ``pairing,'' hence the name of the area.) Although such mapping can lead to attacks on the discrete log problem in $G$, if the mapping is chosen carefully one may still assume intractability of discrete log in $G$, and the pairing can be very useful in constructing cryptographic protocols and proving their security. In particular, one can get ``identity-based encryption,'' a type of public key cryptography where a user's public key can be her own name (or email address, or any deterministically chosen name), which in turn can be used as a primitive in other applications.

Dan Spielman spoke on spectral graph theory, focusing on results and problems that aren't quite studied enough by theoreticians. He showed some remarkable of example of graph drawings obtained by simply plotting a vertex $i$ to the point $(v(i),w(i))$, where $v$ and $w$ are the second largest and third largest eigenvalues of the laplacian of the adjacency matrix. The sparse cut promised by Cheeger inequality is, in such a drawing, just the cut given by a vertical line across the drawing, and there are nice algebraic explanations for why the drawing looks intuitively ``nice'' for many graphs but not for all. Spectral partitioning has been very successful for image segmentation problems, but it has some drawbacks and it would be nice to find theoretically justified algorithms that would do better.

Typically, I don't go to an Italian restaurant in the US unless I have been there before and liked it, a rule that runs into certain circularity problems. I was happy that yesterday I made an exception to go to Al Forno, which proved to be truly exceptional.

Hillary Clinton voted in support of burning the flags of veterans' children

2007-10-07T21:13:00.000-07:00

Or at least she cannot sue a rival campaign if it makes such a claim.

The Washington State Supreme Court has found that politicians have a constitutional right to lie.

(It is still illegal to libel, but libel is defined extremely narrowly in the US. It is not enough to make a false statement of fact, it is not even enough if this is done with malice. It must, in addition, cause harm to the reputation of the victim.)

Dumplings, zeppole, and "vegetables"

2007-09-26T15:45:00.000-07:00

Yesterday, Gowers was in Princeton to give a fascinating talk about quadratic Fourier analysis, an event that it would be worth reporting on. And on Monday Ahmadinejad was at Columbia to deliver his comic routine, not quite managing to keep a straight face when, asked about the death penalty for homosexuality in Iran, he said "we don't have homosexuals in Iran, I don't know who told you that" (go to 3:40 in the video).

But that's not what I am going to talk about, because I realize I haven't written in a while about the favorite topic of most readers.

Last Sunday I was on my third trip to Chinatown for xiao long bao (above) and it happened to be the last day of the Feast of San Gennaro in nearby Little Italy. San Gennaro is the patron saint of Naples, known for "The Miracle." A vial supposedly containing the dried blood of the saint is kept in the Naples cathedral, and brought out a few times a year, when it usually liquefies during the mass. The phenomenon has been replicated with various substances, but it's unclear what exactly is in the vial.

In New York, the San Gennaro festivities run for nearly two weeks, and close off several blocks of Mulberry street.

Many stands sold zeppole (fried dough), which looked appetizing, if not sanitary. Other stands sold stuff that looked neither appetizing nor sanitary.

Here is the border of Chinatown and Little Italy. Note the "Birra Moretti" umbrellas in front of the store with the yellow awning.

Finally, as an illustration of the difference between the "for all" and the "there exists" quantification, here is an excerpt from the menu of the Indonesian restaurant next to the Birra Moretti place.

The long-distance commuter

2007-09-18T16:06:00.001-07:00

I am spending this semester as a member of the Institute for Advanced Study and a visiting professor at Princeton University, while living in New York and planning to spend some time at NYU and Columbia as well. Though this has no relation to my case, a friend once explained to me that the key to not having to do any work is to have (at least) two affiliations and two offices. When you are not at one place, people will think you are working at the other place and vice versa.

I haven't been to New York much ever since moving out about seven years ago, and I am sure much has changed, most dramatically in the East Village. Hopefully, even as I work very, very hard, I will have time to explore the city again.

Meanwhile, night and weekend repairs in the 1-2-3 lines cause bizarrely complicated (and largely unannounced) schedule changes. To take a local uptown train from 14th street, for example, one goes to the uptown express track (there is no sign to this effect, only word of mouth). Apparently (I haven't tested it) if one wants to go from Columbia to, say, South Ferry, one starts by going on a train that has a sign on the side that says "South Ferry." Then one changes to the 2 or 3 express line before 14th street, while, of course, waiting for it on the local track. Then one gets down at Chambers, from which one finds a shuttle bus that will do all the stops of the 1 train until South Ferry. (Reminds me of the instructions given in the first minute of this hilarious Monty Python sketch -- Note: after the first minute, the sketch keeps being famously funny, but is not, as they say, "work safe.")

Once one finds the right train, it's always impress how full the subway can be, and how safe it feels, at 3am or even 4am (to be fair, the MUNI too, in San Francisco, would probably be full around 2-2:30am, if it didn't stop running at midnight).

Yesterday I found my way to Princeton and attended Scott's talk on "algebrizing" proofs. The proof of a complexity result is algebrizing if it satisfies a certain property, all known non-relativizing and non-natural lower bound proofs are algebrizing, and an algebrizing proof cannot settles the P versus NP question.

Long ago, Goldreich, Micali and Wigderson proved that the existence of commitment schemes implies that every problem in NP has a computational zero knowledge interactive proofs. (I'll refer to this result as the GMW theorem.)

Among the issues raised during and after Scott's talk was the fact that the GMW theorem does not relativize, nor, probably, does it "algebrize." Indeed, it seems impossible to abstract the known proofs of the GMW theorem to any model except one in which NP witnesses can be verified via a series of "local" checks, and, essentially, this property characterizes NP in the real world. (Similar issues arise when thinking about the PCP theorem, see this paper for an exploration of the issue of local checkability in non-relativizing proofs.) So one goes back to a question that has surfaced every now and then in the past twenty years: is there a model or a class of proofs where one can prove that commitment schemes imply NP is in CZK, but in which the P versus NP question cannot be settled?

Relative to a PSPACE oracle, the statement of the GMW theorem is vacuously true (because commitment schemes do not exist) and P=NP (so that P$\neq$NP is unprovable), so one cannot just use the statement of the GMW theorem plus relativizing techniques to prove $P\neq NP$, but this is quite far from a satisfactory answer.

Open Access Publishing is Censorship

2007-09-07T13:14:00.000-07:00

To take a break from controversies, let's talk about something we can all agree about: Elsevier is evil.

Consider the following business model: people make a product for free (sometimes even contributing money to it) and said product is then sold to them. This is like Kramer's idea of the make-your-own-pizza pizzeria, which actually wasn't so crazy - I certainly like to cook my own meat in a Korean barbecue place or in a restaurant that offer Beijing hot pot - mmh... Beijing hot pot ... - but I am being led astray by the thought of food, and, back to my point, it is also how for-profit publishing of academic journals works. It used to be that academic publishers performed a number of useful tasks, such as typesetting the articles, but now typsetting is done by the authors themselves, and all the work that goes into producing an academic journal, the editing, the peer-reviewing, and of course the actual research and writing-up, are done for free by the academic community. To add insult to injury, it was common for authors to have to give up all rights about their work to the publisher, so that the authors cannot even legally keep a copy of the paper posted on their page except as a link to the publisher's version, often not freely available. (Such policies have changed at many journals because of the increased restlessness of the acadmic community.)

A few years ago, Don Knuth conducted a thourough analysis of the subscription rates of academic journals, and invited fellow editors of the Journal of Algorithms, published by Elsevier, to resign en masse and to create a new journal, the ACM Transactions on Algorithms that, while not free, is published by a not-for-profit professional society and has considerably lower subscription rates. Earlier, the editors of Kuwler's Machine Learning Journal similarly resigned en masse to join a new journal with friendlier policies toward the community. Such actions have become more and more common.

Within theoretical computer science, Elsevier's journal have been often targeted as the worse offenders, with reactions ranging from the mentioned killing of the Journal of Algorithms to the decision to stop publishing special issues of STOC, FOCS and CCC in Elsevier's Journal of Computer and System Sciences. Elsevier's reaction to the community's backlash was also disappointing, with proposals to introduce compensations for editors and reviewers, rather than to reduce subscription fees and to open the online archives. (Except tentatively, like the "experimental" opening of the Information and Computation archives.)

Then there was Elsevier's participation in the international arm trade, which is going to end this year after a strong campaign initiated in the health sciences. (See for example the open letter of the editors of Elsevier's Lancet.)

Now I read that a group of publishers, which includes Elsevier, has hired PR consultant Eric Dezenhall who, according to his wikipedia biography, helped Exxon have Greenpeace audited by the IRS, and helped Enron discredit the initial whistleblower. One of his talking points about for-profit publishing will be that open access publishing equals government censorship. How, exactly? Read the Nature article.

The Swift-Boating of Modern Cryptography

2007-08-28T10:44:00.000-07:00

The September issue of the Notices of the AMS is out, and it contains an article by Neal Koblitz on modern cryptography, exposing themes he wrote about in previous articles.

Before I get to Koblitz's thesis I should describe the context, as I see it.

Cryptography underwent two major revolutions in the 1970s and 1980s.

The notion of public key cryptography, invented by Diffie and Hellman (and earlier, but only in classified documents that didn't enter the public domain for decades, by Ellis, Cocks, and Williamson) and made possible by Rivest, Shamir and Adleman, allowed parties that had never met in advance to share a secret key to communicate over an unsafe channel. Without this technology, buying and selling things online would be extremely inconvenient and companies like amazon and ebay would probably not exist.

The other revolution, started by the 1982 series of papers by Blum, Goldwasser, Micali and Yao, was the discovery that one could provide formal definitions of security for cryptographic problems, and that such definitions were achievable under complexity assumptions, albeit, initially, via slow constructions.

Indeed, the importance of the new definitions cannot be overstated, and, possibly for lack of accessible expositions, it has not been completely digested by all the security community. I remember, not too long ago, reading a paper on electronic elections, listing seven or more requirements that an election protocol should satisfy, and it was clear that the list was unwieldy, redundant, and, most importantly, incomplete. The modern definitional approach is instead to begin with a description of an ideal setting (where every person votes in a secret ballot, then all ballots are counted and the total tally is the only information that anybody gets) and then require that a protocol be such that anything an adversary can do in the protocol to alter the outcome or gain information, can also be done in the ideal setting. In particular, whatever outcome or information an attacker cannot gain in the ideal setting, it cannot be gained in the protocol either.

Some constructions developed by theoreticians and coming with a formal analysis are too inefficient to be used, but their development often leads to the discovery of general design principles such that, for example, public key encryption algorithms must be randomized, and should be designed so that it is not possible to construct a valid ciphertext in any other way than applying the encryption algorithm to a known message.

Indeed modern cryptography is the area of computer science where the distance between theory and practice is the least: one finds theoreticians who spend most of their time on impractical constructions designed to be "plausibility results" but who also sit on standards bodies and help create and assess widely used systems, whereas one is less likely to see the algorist preoccupied with $O(log n)$ approximation algorithms also working on commercial optimization packages. The important difference is that optimization algorithms can be validated in practice in a way that is impossible for cryptographic protocols, where one cannot anticipate what attacks will be used, and hence one should strive for security against all possible attacks which is possible, within an attack model, only via a formal analysis and reductions.

Koblitz points out that sometimes proofs contain mistakes, and that there can be attacks not covered by standard models. His reaction, however, is not that the community should be very careful about formal correctness, and explore (as is being done) new models that take into account timing attacks and other "grey box" accesses to the computations of the parties. Rather, he suggests doing away with proofs, and relying more on intuition. This is discussed in the second part of the paper (the first part is devoted to encryption schemes and factoring algorithms via elliptic curves, the "good" interaction between math and cryptography), through such rhetorical devices as non sequiturs, personal attacks, and petulance. The CRYPTO community's typesetting abilities are not spared, nor is Oded Goldreich's spelling.

It would seem hard to defend the idea that one is more likely to make a correct statement if the statement has no proof compared to having a proof, or that one can be secure against a wider class of attacks by relying on intuition rather than defining a class of attacks and establishing the security guarantee. It would be like having a draft-dodger compete in an election against a war hero, and having the latter be on the defensive about his military service, but sometimes strange things do happen.

(For the Italian readers, a better reference would be from Nanni Moretti's Aprile: "Di qualcosa, D'Alema rispondi. Non ti far mettere in mezzo sulla giustizia proprio da Berlusconi! D'Alema, dì una cosa di sinistra, dì una cosa anche non di sinistra, di civiltà!")

Update 9/1/07: you can now read letters to the editors by Oded Goldreich, Boaz Barak, and Jon Katz, and there are more online comments [here] and [here]

Update 9/5/07: Hugo Krawczyk has also written a letter to the editors of the Notices. The interested reader can compare what Koblitz said about Hugo's work on HMQV to the actual HMQV paper.

Zack Kim

2007-08-21T12:59:00.000-07:00

See also Fur Elise, and more at his website.

More ways to prove unsatisfiability of random k-SAT

2007-08-20T17:09:00.000-07:00

Earlier, here and here, we discussed the following problem: we pick at random a k-CNF formula with $n$ variables and $m$ clauses; if $m$ is at least $c_k n$, for a constant $c_k$, then we know that with high probability the formula is unsatisfiable; is there an algorithmic way of certifying this unsatisfiability?

One approach we discussed is a reduction to 2SAT, which works provided $m$ is at least of the order of $n^{k-1}$. What about sparser formulas?

Here is another possible reduction. Starting from the formula, construct an hypergraph that has 2n vertices and m hyperedges as follows. For every variable $x_i$ we have the two vertices $[x_i=0]$ and $[x_i=1]$, and, for every clause with $k$ variables, we have the hyperedge that connects the $k$ vertices corresponding to the unique assignment to those $k$ variables that contradicts the clause. For example, the clause
$(x_3 \vee \neg x_5 \vee x_6)$
corresponds to the hyperedge
$([x_3=0],[x_5=1],[x_6=0])$.

Now, if the formula is random, we have a random hypergraph. Also, if the formula is satisfiable we have an independent set of size $n$; half as big as the total number of vertices: just take the vertices consistent with the assignment. (An independent set is a set of vertices such that no hyperedge is completely contained in the set.) Certifying unsatisfiability of a random formula now reduces to certifying that a given random hypergraph has no large independent set.

Unfortunately, we don't know of any algorithm for this problem, except for the case of graphs. As I may discuss in a future post, spectral methods allow us to certify that a given random graph with $n$ vertices and average degree $d$ has no independent set larger than about $n/O(\sqrt{d})$. By this, I mean that there is a definition of certificate that, when existing, always correctly proves such an upper bound, and when we pick at random a graph of average degree $d$ there is a high probability that a certificate proving an upper bound of $n/O(sqrt{d})$ to the size of the largest independent set exists and can be found efficiently.

It is too bad that the above reduction produces a graph only when we start from 2SAT, a problem for which we already know how to decide (and hence certify) satisfiability in polynomial time.

But, and here is a great idea of Goerdt and Krivelevich from 2000, we can reduce the problem of certifying non-existence of large independent sets in random hypergraps to the problem of certifying non-existence of large independent sets in random graphs.

Suppose we have an hypergraph with n vertices and m hyperedges, each involving 4 vertices. Construct now a graph with $n^2$ vertices, one for every pairs of vertices in the hypergraph, and for every hyperedge $(a,b,c,d)$ in the hypergraph create the edge $([a,b],[c,d])$ in the graph. (Assume for now that we choose the ordering of vertices at random, even if this means that we only achieve a randomized reduction. There are ways to make the reduction deterministic.) Now, if the hypergraph has an independent set of size $\geq t$ then clearly the graph has an independent set of size $\geq t^2$. Furthermore, if we started from a random hypergraph then we are getting a random graph. So if $m$ is of the order of $n^2$ we are able to refute the claim that there is an independent set of size $n/2$ in the hypergraph (by refuting the claim that there is an independent of size $n^2 /4$ in the graph).

In general, for even $k$, these ideas give a way of refuting a random $k$-SAT instance with $n$ variables and $n^{k/2}$ clauses.

(The original paper of Goerdt and Kirvelevich had an extra polylog term needed to make the spectral techniques work. But later more sophisticated analyses have removed the polylog bound, either by using slightly different reductions or by directly improving the bounds on the sparsity of random graphs for which one can certify the non-existence of large independent sets. See this paper by Feige and Ofek for the latter approach.)

Instead of thinking in terms of reductions to graph and hypergraph problems, one may directly see the method as associating a matrix to the formula and proving that certain properties of the matrix imply the unsatisfiability of the formula.

A generalization of this way of seeing the argument has led to an algorithm by Friedman, Goerdt and Krivelevich that certifies unsatisfiability of random kSAT instances with about $n^{k/2}$ clauses even if $k$ is odd. I think it would be interesting to have a combinatorial view of what happens in that algorithm.

This is the state of the art for algorithms that find certificates of unsatisfiability.

There is also some intuition for why $n^{1.5}$ is a natural barrier. The algorithmic techniques described so far are "no more powerful" than semidefinite programming: the standard semidefinite relaxation of Max 2SAT proves that a given 2SAT formula is unsatisfiable, whenever it is the case, and a standard semidefinite programming relaxation of independent set (the Lovasz theta function) proves with high probability that a random graph has no large independent set. It is conjectured, however, that no "simple" reduction of random 3SAT to a semidefinite programming problem yelds a refutation if the number of clauses is less than $n^{1.5}$. This has been verified by Feige and Ofek for a natural reduction.

Recently, Feige, Kim and Ofek have defined a new type of witness of unsatisfiability that is verifiable in polynomial time and that exists with high probability for formulas with about $n^{1.4}$ clauses. (It is not known, however, how to construct such witnesses in polynomial time given a formula.) As could be expected, their witness-verification algorithm employs something that we know how to do in polynomial time but that is very hard for semidefinite programs: verifying the unsatisfiability of a given linear system over GF(2).

Lies, Damn LIes, and the Number of Sexual Partners

2007-08-16T16:19:00.001-07:00

A few days ago, Gina Kolata reported in the New York Times on the paradox of studies on sexual behavior consistently reporting (heterosexual) men having more sexual partners than women, with a recent US study reporting men having a median number of 7 partners and women a median number of 4. Contrary to what's stated in the paper, this is not mathematically impossible (key word: median). It is however quite implausible, requiring a relatively small number of women to account for a large fraction of all men's partners.

An answer to this paradox can be found in Truth and consequences: using the bogus pipeline to examine sex differences in self-reported sexuality, by Michele Alexander and Terry Fisher, Jorunal of Sex Research 40(1), February 2003.

In their study, a sample of men and women are each divided into three groups and asked to fill a survey on sexual behavior. People in one group filled the survey alone in a room with an open door, a researcher sitting outside, and after being told the study was not anonymous; people in a second group filled the survey in a room with a closed door and an explicit assurance of anonymity; people in a third group filled the survey attached to what they believe to be a working ``lie detector.''

In the first group, women reported on average 2.6 partners, men 3.7. In the second group, it was women 3.4 and men 4.2. In the third group, it was women 4.4 and men 4.0.

(The study looks at several other quantities, and some of them have even wider variance in the three settings.)

So, not surprisingly given the sexual double standards in our culture, men and women lie about their sexual behavior (men overstate, women understate), and do less so in an anonymous setting or when the lie is likely to be discovered.

Here is the reporting of the first group put to music:

[Update 8/18/07: so many people must have emailed her about the median versus average issue in the article that Gina Kolata wrote a clarification. Strangely, she does not explain, for the rest of the readers, what the difference is and why it is possible, if unlikely, to have very different medians for men and women. The claim in the clarification, by the way, is still wrong: those 9.4% of women with 15 or more partners could be accounting for all the missing sex.]

Atle Selberg

2007-08-09T14:09:00.000-07:00

Number theorist Atle Selberg died in Princeton on Monday, at age 90. One of his major results was the "Selberg formula" that led to an elementary proof of the prime number theorem, a Fields medal in 1950, and a famous controversy with Paul Erdos.

Code Monkey

2007-08-02T13:48:00.000-07:00

The unreasonable effectiveness of additive combinatorics in computer science

2007-07-19T18:19:00.000-07:00

As I have written several times on these pages, techniques from additive combinatorics seem to be very well suited to attack problems in computer science, and already a good amount of applications have been found. For example, "sum-product theorems" originally developed in a combinatorial approach to the Kakeya problem have been extremely valuable in recent constructions of randomness extractors. The central theorem of additive combinatorics, Szemeredi's theorem, has now four quite different proofs, one based on graph theory and Ramsey theory, one based on analytical methods, one based on ergodic theory and one based on hypergraph theory. The first proof introduced the Szemeredi regularity lemma, which is a fixture of algorithmic work on property testing. The analytical proof of Gowers introduced the notion of Gowers uniformity that, so far, has found application in PCP constructions, communication complexity , and pseudorandomness. There is also work in progress on complexity-theoretic applications of some of the ergodic-theoretic techniques.

Why is it the case that techniques developed to study the presence of arithmetic progressions in certain sets are so useful to study such unrelated notions as sub-linear time algorithms, PCP systems, pseudorandom generators, and multi-party protocols? This remains, in part, a mystery. A unifying theme in the recent advances in additive combinatorics is the notion that every large combinatorial object can be ``decomposed'' into a ``pseudorandom'' part and a ``small-description'' part, and that many questions that we might be interested in are easy to answer, at least approximately, on pseudorandom and on small-description objects. Since computer scientists almost always deal with worst-case scenario, and are typically comfortable with approximations, it is reasonable that we can take advantage of techniques that reduce the analysis of arbitrary worst cases to the analysis of much simpler scenarios.

Whatever the reason for their effectiveness, it is worthwhile for any theoretical computer scientist to learn more about this fascinating area of math. One of the tutorials in FOCS 2007 will be on additive combinatorics, with a celebrity speaker. More modestly, following Random-Approx 2007, in Princeton, there will be a course on additive combinatorics for (and by) computer scientists. (If you want to go, you have to register by August 1 and reserve the hotel by this weekend.)

Teamwork

2007-06-08T07:26:00.000-07:00

Watch it through the end, there are a couple of plot twists.

(via Unfogged and Jane Galt.)

Evolution

2007-05-31T17:58:00.001-07:00

If you read these two essays out of context, would you know which one is (ostensibly) serious and which one is satire?

I Believe In Evolution, Except For The Whole Triassic Period

What I Think About Evolution

Lies, damn lies, and a Dutch trial

2007-05-17T19:07:00.000-07:00

In CS70, the Berkeley freshman/sophomore class on discrete mathematics and probability for computer scientists, we conclude the section on probability with a class on how to lie with statistics. The idea is not to teach the students how to lie, but rather how not to be lied to. The lecture focuses on the correlation versus causation fallacy and on Simpson's paradox.

My favorite way of explaining the correlation versus causation fallacy is to note that there is a high correlation between being sick and having visited a health care professional in the recent past. Hence we should prevent people from seeing doctors in order to make people healthier. Some HMOs in the US are already following this approach.

Today, a post in a New York Times science blog tells the story of a gross misuse of statistics in a Dutch trial that has now become a high-profile case. In the Dutch case two other, and common, fallacies have come up. One is, roughly speaking, neglecting to take a union bound. This is the fallacy of saying 'I just saw the license plate California 3TDA614, what are the chances of that!' The other is the computation of probabilities by making unwarranted independence assumptions.

Feynman has written eloquently about both, but I don't have the references at hand. In particular, when he wrote on his Space Shuttle investigation committee work, he remarked that official documents had given exceedingly low probabilities of a major accident (of the order of one millionth per flight or less), even though past events have shown this probability to be more of the order of 1%. The low number was obtained by summing the probabilities of various scenarios, and the probability of each scenario was obtained by multiplying estimates for the probabilities that the various things that had to go wrong for that scenario to occur would indeed go wrong.

Christos Papadimitriou has the most delightful story on this fallacy. He mentioned in a lecture the Faloutsos-Faloutsos-Faloutsos paper on power law distributions in the Internet graph. One student remarked, wow, what are the chances of all the authors of a paper being called Faloutsos!

Proving unsatisfiability of random kSAT

2007-05-15T18:45:00.000-07:00

In the previous random kSAT post we saw that for every $k$ there is a constant $c_k$ such that

A random kSAT formula with $n$ variables and $m$ clauses is conjectured to be almost surely satisfiable when $m/n < c_k - \epsilon$ and almost surely unsatisfiable when $m/n > c_k + \epsilon$;
There is an algorithm that is conjectured to find satisfying assignments with high probability when given a random kSAT formula with $n$ variables and fewer than $(c_k - \epsilon) n$ clauses.

So, conjecturally, the probability of satisfiability of a random kSAT formula has a sudden jump at a certain threshold value of the ratio of clauses to variables, and in the regime where the formula is likely to be satisfiable, the kSAT problem is easy-on-average.

What about the regime where the formula is likely to be unsatisfiable? Is the problem still easy on average? And what would that exactly mean? The natural question about average-case complexity is: is there an efficient algorithm that, in the unsatisfiable regime, finds with high probability a certifiably correct answer? In other words, is there an algorithm that efficiently delivers a proof of unsatisfiability given a random formula with $m$ clauses and $n$ variables, $m> (c_k + \epsilon) n$?

Some non-trivial algorithms, that I am going to describe shortly, find such unsatisfiability proofs but only in regimes of fairly high density. It is also known that certain broad classes of algorithms fail for all constant densities. It is plausible that finding unsatisfiability proofs for random kSAT formulas with any constant density is an intractable problem. If so, its intractability has a number of interesting consequences, as shown by Feige.

A first observation is that if we have an unsatisfiable 2SAT formula then we can easily prove its unsatisfiability, and so we may try to come with some kind of reduction from 3SAT to 2SAT. In general, this is of course hopeless. But consider a random 3SAT formula $\phi$ with $n$ variables and $10 n^2$ clauses. Now, set $x_1 \leftarrow 0$ in $\phi$, and consider the resulting formula $\phi'$. The variable $x_1$ occurred in about $30 n$ clauses, positively in about $15 n$ of them (which have now become 2SAT clauses in $\phi'$) and negatively in about $15 n$ clauses, that have now disappeared in $\phi'$. Let's look at the 2SAT clauses of $\phi'$: there are about $15 n$ such clauses, they are random, so they are extremely likely to be unsatisfiable, and, if so, we can easily prove that they are. If the 2SAT subset of $\phi'$ is unsatisfiable, then so is $\phi'$, and so we have a proof of unsatisfiability for $\phi'$.

Now set $x_1 \leftarrow 1$ in $\phi$, thus constructing a new formula $\phi''$. As before, the 2SAT part of $\phi''$ is likely to be unsatisfiable, and, if so, its unsatisfiability is easily provable in polynomial time.

Overall, we have that we can prove that $\phi$ is unsatisfiable when setting $x_1 \leftarrow 0$, and also unsatisfiable when setting $x_1\leftarrow 1$, and so $\phi$ is unsatisfiable.

This works when $m$ is about $n^2$ for 3SAT, and when $m$ is about $n^{k-1}$ for kSAT. By fixing $O(\log n)$ at a time it is possible to shave another polylog factor. These idea is due to Beame, Karp, Pitassi, and Saks.

A limitation of this approach is that it produces polynomial-size resolution proofs of unsatisfiability and, in fact tree-like resolution proofs. It is known that polynomial-size resolution proofs do not exist for random 3SAT formulas with fewer than $n^{1.5-\epsilon}$ clauses, and tree-like resolution proofs do not exist even when the number of clauses is just less than $n^{2-\epsilon}$. This is a limitation that afflicts all backtracking algorithms, and so all approaches of the form ``let's fix some variables, then apply the 2SAT algorithm.'' So something really different is needed to make further progress.

Besides the 2SAT algorithm, what other algorithms do we have to prove that no solution exists for a given problem? There are algorithms for linear and semidefinite programming, and there is Gaussian elimination. We'll see how they can be applied to random kSAT in the next theory post.

Slump? What slump?

2007-05-08T18:50:00.000-07:00

One bedroom, one million, no parking. It's the `price reduced' part in the description that gets me.

Random kSAT

2007-05-07T11:50:00.000-07:00

Pick a random instance of 3SAT by picking at random $m$ of the possible $8 {n\choose 3}$ clauses that can be constructed over $n$ variables. It is easy to see that if one sets $m=cn$, for a sufficiently large constant $c$, then the formula will be unsatisfiable with very high probability (at least $1-2^n \cdot (7/8)^m$), and it is also possible (but less easy) to see that if $c$ is a sufficiently small constant, then the formula is satisfiable with very high probability.

A number of questions come to mind:

If I plot, for large $n$, the probability that a random 3SAT formula with $n$ variables and $cn$ clauses is satisfiable, against the density $c$, what does the graph look like? We just said the probability is going to be close to 1 for small $c$ and close to $0$ for large $c$, but does it go down smoothly or sharply?

Here the conjecture, supported by experimental evidence, is that the graph looks like a step function: that there is a constant $c_3$ such that the probability of satisfiability is $1-o_n(1)$ for density $< c_3$ and it is $o_n(1)$ for density $>c_3$. A similar behavior is conjectured for kSAT for all $k$, with the threshold value $c_k$ being dependent on $k$.

Friedgut proved a result that comes quite close to establishing the conjecture.

For, say, 3SAT, the statement of the conjecture is that there is a value $c_3$ such that for every interval size $\epsilon$, every confidence $\delta$ and every sufficiently large $n$, if you pick a 3SAT formula with $(c_3+\epsilon)n$ clauses and $n$ variables, the probability of satisfiability is at most $\delta$, but if you pick a formula with $(c_3-\epsilon)n$ clauses then the probability of satisfiability is at least $1-\delta$.

Friedgut proved that for every $n$ there is a density $c_{3,n}$, such that for every interval size $\epsilon$, every confidence $\delta$ and every sufficiently large $n$, if you pick a 3SAT formula with $(c_{3,n}+\epsilon)n$ clauses and $n$ variables, the probability of satisfiability is at most $\delta$, but if you pick a formula with $(c_{3,n}-\epsilon)n$ clauses then the probability of satisfiability is at least $1-\delta$.

So, for larger and larger $n$, the graph of proability of satisfiability versus density does look more and more like a step function, but Friedgut's proof does not guarantee that the location of the step stays the same. Of course the location is not going to move, but nobody has been able to prove that yet.

Semi-rigorous methods (by which I mean, methods where you make things up as you go along) from statistical physics predict the truth of the conjecture and predict a specific value for $c_3$ (and for $c_k$ for each $k$) that agrees with experiments. It remains a long-term challenge to turn these arguments into a rigorous proof.

For large $k$, work by Achlioptas, Moore, and Peres shows almost matching upper and lower bounds on $c_k$ by a second moment approach. They show that if you pick a random kSAT formula for large $k$ the variance of the number of satisfying assignments of the formula is quite small, and so the formula is likely to be unsatisfiable when the average number of assignments is close to zero (which actually just follows from Markov's inequality), but also the formula is likely to be satisfiable when the average number of assignments is large. Their methods, however, do not improve previous results for 3SAT. Indeed, it is known that the variance is quite large for 3SAT, and the conjectured location of $c_3$ is not the place where the average number of assignments goes from being small to being large. (The conjectured value of $c_3$ is smaller.)
Pick a random formula with a density that makes it very likely that the formula is satisfiable: is this a distribution of inputs that makes 3SAT hard-on-average?

Before addressing the question we need to better specify what we mean by hard-on-average (and, complementarily, easy-on-average) in this case. For example, the algorithm that always says "satisfiable" works quite well; over the random choice of the formula, the error probability of the algorithm is extremely small. In such settings, however, what one would like from an algorithm is to produce an actual satisfying assignment. So far, all known lower bounds for $c_3$ are algorithmic, so in the density range in which we rigorously know that a random 3SAT formula is likely to be satisfiable we also know how to produce, with high probability, a satisfying assignment in polynomial time. The results for large $k$, however, are non-constructive and it remains an open question to match them with an algorithmic approach.

The statistical physics methods that suggest the existence of sharp thresholds also inspired an algorithm (the survey propagation algorithm) that, in experiments, efficiently finds satisfying assignments in the full range of density in which 3SAT formulas are believed to be satisfiable with high probability. It is an exciting, but very difficult, question to rigorously analyze the behavior of this algorithm.
Pick a random formula with a density that makes it very likely that the formula is unsatisfiable: is this a distribution of inputs that makes 3SAT hard-on-average?

Again, an algorithm that simply says "unsatisfiable" works with high probability. The interesting question, however, is whether there is an algorithm that efficiently and with high probability delivers certificates of unsatisfiability. (Just like the survey propagation algorithm delivers certificates of satisfiability in the density range in which they exist, or so it is conjectured.) This will be the topic of the next post.

You Too Can Be in a Boy Band

2007-04-30T14:00:00.000-07:00

The San Francisco International Film Festival is under way, and they are showing, today and on Wednesday, Il Caimano, Nanni Moretti's latest movie. It's a movie-within-a-movie story about Berlusconi's ascent to power and the inability of contemporary Italian left-leaning moviemakers to make movies with political content, unlike the earlier generation of, say, Elio Petri (the director of Indagine su un cittadino al di sopra di ogni sospetto).

Last weekend there was the North American premiere of The Heavenly Kings, by Bay Area's own Daniel Wu. Part mockumentary part Borat-style guerilla filmmaking, the movie follows four Hong Kong actors in their 30s as they form a "boy" band despite their inability to sing or dance, trick the Hong Kong press into believing they are for real, and eventually deliver a series of three concerts in Hong Kong, Taipei, and Shanghai. They came in person to the screenings for Q&A sessions, to the delight of a group of camera-wielding women sitting in the first rows.

Indagine su un cittadino al di sopra di ogni sospetto

2007-04-20T21:31:00.000-07:00

If you live in the San Francisco Bay Area, don't miss this movie playing at the Castro this Tuesday at seven. One of my favorite movies ever, it has an unforgettable soundtrack by Ennio Morricone, a stunning performance by Gian Maria Volonte', and a very clever, and perfectly executed, premise.

In practice

2007-04-17T20:00:00.000-07:00

One benefit of writing In Theory is the abundance of unsolicited information I have gotten from the comments. I have learned that you say "30-year old" and "80-page paper", not "30-years old" and "80-pages paper," that Michael Chabon has written a most beautiful and insightful essay about Berkeley, that the noun of "to pronounce" is "pronunciation," and much more.

Now I am going to try and see how it works with solicited information. Google analytics tells me that a lot of you readers use windows (for shame!) and I am sure that many of you have cell phones. So, what is a good piece of software to connect a phone to a windows computer via bluetooth?

Here "good" would include sending text messages and reading received ones through the computer, editing and "sync-ing" contacts, moving files to (ringtones) and from (pictures) the phone, and having a decent interface. Bluephone for Mac does all this, plus lots of cute things, such as pausing iTunes and showing a notice when there is an incoming call.

Synccell moves files, "syncs" contacts and sends text messages, but it cannot read text messages, and the interface is disastrous. Mobiledit supposedly does all the basic things, but it can't read the file system of my phone (and their forum is full of users having various complaints about upload and download).

These are such commonly useful functionalities, there has to be a program that does it well. Isn't there? In fact I am surprised that Google hasn't come up with a beautifully designed application that integrates with Google Calendar, Google Talk, GMail, and so on.

[Theory post to follow soon.]

2007-04-04T22:32:00.000-07:00

I feel like I am living inside an Apple commercial.

I have just bought a bluetooth "dongle" (who comes up with these terms?) for my laptop, and it came with a booklet of installation instructions. There are 7 1/2 pages of instructions for Windows users (like me). They are followed by the instructions for OS X users that, rephrasing slightly, amount to "stick it in."

Most of the complications, by the way, arise from the fact that when you connect the device, Windows thinks it knows what it's doing, and it installs the wrong drivers. The installation program then has to run a script to uninstall them and re-install the right ones (the whole thing takes a while). This is actually an improvement over the previous installation program. I hope the 12-inch macbook pro comes out soon.

Not that it has anything to do with anything, but this is cute. (via cosmic variance.

And then the president pro-tempore of the Senate

2007-04-02T22:18:00.000-07:00

After more than four years of service to the theory community, and beyond, Lance Fortnow has retired from his computational complexity blog, the first and most succesful of its kind. Bill Gasarch, however, will keep that hallowed green space alive. Donald Knuth is rumored to be next in the line of succession, after Bill tires of it.

User interfaces

2007-03-27T00:26:00.000-07:00

I have just bought a new food processor, and I am in awe of its user interface. On the front there are two HUGE buttons, one marked ON, one marked OFF.

That's it!

If I want to watch TV, however, I need to use two of these four remotes, depending on what exactly I am watching.

and that's only because I have lost the fifth remote, the one of the sound system. The four surviving remotes have a total of 174 keys (45 + 47 + 44 + 38)...

I can easily reconstruct from memory Hastad's proof that Max 3SAT is hard to approximate within $\frac 78 - \epsilon$, but every time the sound system gets disconnected from the power, I struggle to remember the particular sequence and duration of key presses needed to set the time. Now it just shows noon, it's not worth it. And I have seen more than one computer science Ph.D. (not theoreticians!) turn the TV off while trying to turn the cable box on (if you get cable from Comcast you know what I am talking about).

What bothers me is that these interfaces are designed by people whose job is to design them. There must be a person who decides how the time is set and a person who decides what keys you press to turn the TV on or the cable on, or how many keys to put on the remote and how big and so on. Why would they do something that is so obviously wrong? "Let's see, first the user has to press `clock' for three seconds, then time will start flashing, at that point he first presses 'FM', then 'volume up' and then ..."

What made Google so successful was certainly the math and the fact that it worked and that it was the first commercial search engine to return relevant answers instead of random ones. But having such a clean and pleasant design, at a time when the notion of a "portal" was popular also played a role, and the design has been widely copied afterwards. And usability and design are probably the main reasons why the iPod has become so popular.

There is an unfortunate tendency among computer scientists, not just among theoreticians, to look down on HCI work. We do so at our own risk. Including the risk that a disgruntled designer, with an evil smirk, thinks to himself "Let's see who is laughing when you have to press the 'aux' key with the 'seek' key until it beeps, and then press the 'grft' key while..."

2007-03-22T00:05:00.000-07:00

The April issue of the Notices of the AMS is out, and there is an article that was quite fascinating to read even though, at the end, it wasn't quite clear to me what it was all about.

Meanwhile, I am very happy to know that I am doing my part towards understanding the global regularity of the Navier-Stokes equations.

The Mozart of Math

2007-03-13T02:14:00.000-07:00

The Science section of the New York Times has a profile of Terence Tao. And if you have been following the links on the right, you know he has a blog.

The sex appeal of brainy women

2007-02-27T12:45:00.000-08:00

This is yesterday's news (last week's news, actually), but perhaps you haven't heard the story about the Delta Zeta sorority at DePauw University, in Indiana. A review conducted by the sorority's central organization found that 23 of the 35 sisters were insufficiently committed to recruitement, and they were purged from the organization. Coincidentally, those 23 included all the overweight and non-white members. Half of the 12 white and thin survivors were so outraged that they quit. The NYT article has more on the story. (Inlcuding the story of a recruiting event in which thin white sisters were bused in from another university.)

Although the writer means well, the article itself rubs me the wrong way in a couple of places. For example, I can't even begin to count the ways the following paragraph is wrong:

Despite those incidents, the chapter appears to have been home to a diverse community over the years, partly because it has attracted brainy women, including many science and math majors, as well as talented disabled women, without focusing as exclusively as some sororities on potential recruits’ sex appeal.

And then

“I had a sister I could go to a bar with if I had boy problems,” said Erin Swisshelm, a junior biochemistry major who withdrew from the sorority in October. “I had a sister I could talk about religion with. I had a sister I could be nerdy about science with.”

Because, see, what would those nerdy, unappealing, math and science majors have to say about boy problems, or what would possess them to go to a bar?

And this is in an article that decries stereotypes about women.

新年快乐!

2007-02-17T11:28:00.000-08:00

Put. The Candle. Back

2007-02-13T17:20:00.000-08:00

When I was in high school, I watched Young Frankenstein a few times too many, and so did some of my friends. We would sometimes reenact the "Sit down please. No, no, higher" gag at inappropriate times, or say "What a filthy job" when the weather threatened rain, and repeat our favorite lines ("You take the blonde, I'll take the one with the turban," "he is going to be very popular," "A.B. Normal") for no particular reason. Overall, I knew the movie pretty much by heart, in Italian, that is. (In Italy, foreign movies are dubbed, often by famous actors, not subtitled.) And the "quiet dignity and grace" scene is always with me whenever the excitement of the proof of a major result gives way to the realization that the proof has a fatal flaw.

I have never, however, seen the movie on a big screen. That's about to change, because the Castro Theater, that has already delighted me with big-screen showings of Manhattan, The Good, the Bad and the Ugly, Vertigo, 2001: A Space Odissey, The Rear Window, Rashomon, The Seven Samurai, The Discreet Charm of the Bourgeoisie, and several other movies that came out before my time, is showing Young Frankenstein this weekend!

The funniest scenes in the movies are surreal and incongruous, so the context in which the movie is being screened is oddly appropriate. The movie will show on Saturday at midnight, preceded by a show by Heklina (of Trannyshack fame) and Peaches Christ (of Midnight Mass). What do drag queens have got to do with a nerd cult classic that, as far as I can see, is not camp at all? And then, the whole thing is somehow part of the International Bear Rendezvous of 2007. The bigger (and fatter, and hairer) question then being what do bears have got to do with drag queens and Mel Brooks?

All I can say is that this is the kind of thing that in New York, for all the superior choice of several art movie houses, cannot be found. Score one for San Francisco!

And The Seventh Seal is going to play next week! Now if only they would show The Blues Brothers...

[Update 2/19. I stand corrected. Now I see that every good comedy ought to be preceded by a drag show and to be seen with more than a thousand roaring bears.]

What Is Good Mathematics?

2007-02-12T21:36:00.000-08:00

A very interesting "opinion piece" by Terry Tao. I liked the list of five "hypothetical" ways in which a mathematical field can lose its ways. And the story of Szemeredi's theorem, used as a case study of good mathematics, is so beautiful that it's always good to hear it told.

The Runaway Brains

2007-02-10T17:17:00.000-08:00

The runaway brains

Two symptoms that all not is not well with the Italian research and university system are the number of Italian researchers who move abroad (noticeable) and the number of foreigners who move to Italian universities and research institutions (nearly zero).

Substantial, and expensive, structural changes would be needed to make good use of the talent that abounds in Italian universities. Instead, like in a mismanaged company, every few years there is a "reform" (it would be called a "reorganization" in a company) that is not accompanied by any additional funding, and whose effect is typically to just add to the misery, until, that is, the next reform a few years later.

Anyways, a few years ago, it was decided that something had to be done about Italian researchers moving abroad. This brain drain problem is more colorfully called fuga dei cervelli in Italian, which means, more or less, runaway brains.

The return of the brains

The response was the following zany scheme. A special fund was created to support visiting positions of Italians (or, actually, foreigners as well) employed by foreign research institutions. The fund would pay for a visit of length between three and five years at an Italian university.

The plan was called "rientro dei cervelli." The official English translation is "brain gain," but it actually means "the return of the brains."

Notice that the three year minimum seemed to have been cleverly chosen so that one had to give up one's job in order to take the position. One can be away for one year, by taking a sabbatical or a leave, possibly two years by combining a sabbatical or a leave, but few places would let you away for three years.

After five years, however, it's unclear what the "returned brain" is supposed to do.

The cheated brains

The program started in 2001, and the first positions have been expiring last year. Supposedly, people were expected to apply for jobs at Italian universities, but for the last few years a scandalous underfunding has created a complete freeze in hiring. Within the larger tragedy of a whole generation of researchers who have not been able to find jobs, lied the smaller farce of the "returned brains" that had no job openings to apply to.

Finally, another special fund was set apart to create tenured positions for the "returned brain" people, so that they could stay in Italy, as in the spirit of the whole thing.

But not so quickly. Each appointment of a "returned brain" to one of those positions had to be approved by the CUN, the National Council of Universities. This union-like outfit interpreted the regulations so that people could only be appointed to positions lower than or equal to those from which they quit five years ago in order to go back to Italy. So if someone was a postdoc abroad at the time she went back to Italy, well, no job for her, even though in the intervening five years she has led a lab and has now sufficient experience to be an associate professor.

Things weren't too bad for Aldo Colleoni, however. According to news report, he was able to secure a tenured professorship at the University of Macerata in light of the fact that he was previously a professor at the Zokhiomj University in Ulaanbaatar, Mongolia. Indeed, such university does not seem to exist, and Professor Colleoni does not appear to have ever worked outside of Italy. As the honorary counsel of Mongolia, however, he was able to authenticate his documents himself when he applied for the Italian position. (If the news reporting is accurate, this might be the most brazen case of resume-padding ever.)

Nature has an article that valiantly tries to explain the whole mess (thanks to Luca Aceto for the link). There are also online comments.

The Adopted Brother

2007-02-09T21:15:00.000-08:00

Yesterday's exchange between Stephen Colbert and Debra Dickerson on the subject of the "blackness" of Barak Obama was priceless.

(video via The Raw Story)

Lies, Damn Lies, and National Review (Part II)

2007-02-07T21:45:00.000-08:00

Some time ago, the New York Times reported on census data that shows that only a minority of American women are married and living with their husband. Thomas Sowell writes in National Review to complain about the way the Times misleads with statistics. He repeats points made earlier, in the same magazine, by Jennifer Morse. (Namely, that the claim depends on the definition of "woman" and of "living with.")

But this is part of a pattern, Mr. Sowell writes, because,

Innumerable sources have quoted a statistic that half of all marriages end in divorce — another conclusion based on creative manipulation of words, rather than on hard facts.

The statistic is partly based on the fact that, in recent years, there have been about half as many divorces as marriages in any given year. It is of course not quite correct to project that half of the marriages are going to end in divorce: if the number of people getting married increases with time then, all other things being equal, the ratio of divorces to marriages in a given year underestimates the true fraction of marriages ending in divorce. Conversely, if the number of marriages goes down with time, one has an overestimate. I would suppose, however, that demographers take such trends into account in their models.

Sowell's objection is, of course, considerably more creative:

The fact that there may be half as many divorces in a given year as there are marriages in that year does not mean that half of all marriages end in divorce.

It is completely misleading to compare all the divorces in one year — from marriages begun years and even decades earlier — with the number of marriages begun in that one year.

CCC 2007

2007-02-04T17:50:00.000-08:00

The list of accepted papers is online. I am so curious about the Feige-Kindler-O'Donnell paper!

The Italian Dream

2007-02-01T12:30:00.000-08:00

With the new Center-Left government of Romano Prodi, politics in Italy has been back to being boring (which is, by the way, a good thing - Ask a Taiwanese, not to mention an Israeli, if they wouldn't rather prefer their country to have a boring political life) and incomprehensible. There has been much drama about a proposal to create a form of civil unions open both to unmarried opposite-sex couples living together as well as to same-sex couples. As best as I can understand it, the controversy is over whether the new law will protect the rights of the couple, or the rights of the two people who are in the couple. Or perhaps it's the rights of the two people as members of the couple versus the rights of the people as individuals. See? I told you.

Then there is the case of the expansion of the American military base in Vicenza, which has been approved by the government despite widespread, and bipartisan, local opposition. The majority in the Senate presented a motion to have a debate on something about this, but then opposition presented a counter-motion to "approve the decision of the government," and the motion of the opposition passed. Even though they are a minority, but they voted formally in favor of the majority, though it was to spite them...

Anyways, it's not wonder that the New York Times has not been talking about Italian politics for a while. Unlike me, they try to write about things that their readers actually care to read. (Even though, for some reason, Maureen Dowd is still writing in the Op-Ed page.)

Until yesterday, that is, when Veronica Lario, wife of former prime minister Silvio Berlusconi, sent a letter to the editor of Rupubblica, one of the top two Italian newspapers. In the letter, she complains about Silvio flirting with women at an award cerimony for certain TV prizes, sort of the Italian Emmys. The letter was published in the first page, and, as can be imagined, it was widely commented about. In his typical mix of personal, public, and political, Berlusconi wrote a public reply (in which he apologizes and proclaims his eternal love for his wife) that circulated through the press office of Forza Italia (the political party he founded and leads).

Now, this is the stuff that the New York Times likes to write about. Among various cheap shots, the article has the following most insightful quote from Beppe Severgnini:

[Berlusconi] embodies the Italian dream of being everything, of pleasing everyone (and indulging himself in everything), without giving up anything.

Conquering Hearts, Minds, and Bumpers

2007-01-28T20:58:00.000-08:00

In Baghdad.

(via Andrew Sullivan)

The Multi-dimensional Polynomial van der Waerden Theorem

2007-01-25T20:48:00.001-08:00

[This is the second part of Bill Gasarch's guest post on "polynomial" versions of van der Waerden's theorem. -- Luca]

This is a the second of two Guest Postings on the Polynomial VDW Theorem. This one is on the Multi-dimensional Poly VDW Theorem.

Our starting point is VDW's theorem, which is the same starting point Luca had in his postings on Szemeredi's theorem (here, here, here, here, and here) and I had in my first posting.

VDW:
For all $c,k\in N$, for any $c$-coloring $COL:Z \rightarrow [c]$ there exists $a,d\in Z$, $d\ne 0$, such that

$COL(a) = COL(a+d) = COL(a+2d) = \cdots = COL(a+(k-1)d).$

What would a multidimensional version of VDW look like? What would a multidimensional version of Poly VDW look like? Before stating that, we give corollaries to both to provide the flavor.

Corollary of Two-dimensional VDW:
For all $c$, for any $c$-coloring $COL: Z\times Z\rightarrow [c]$, there exists a square with all corners the same color. (Formally there exists $a,b,d$,$d\ne 0$, such that

$COL(a,b)=COL(a+d,b)=COL(a,b+d)=COL(a+d,b+d).$

Think of this as

$COL((a,b)+d(0,0))=COL((a,b)+d(1,0))=$
$COL((a,b)+d(0,1))=COL((a,b)+d(1,1)).$)

Corollary of Two-dimensional Poly VDW:
For all $c$, for any $c$-coloring $COL: Z\times Z\rightarrow [c]$, there exists a rectangle with all corners the same color where the side is the square of its length. (Formally there exists $a,b,d$, $d\ne 0$, such that
$COL(a,b)=COL(a+d,b)=COL(a,b+d^2)=COL(a+d,b+d^2).$
Think of this as
$COL((a,b)+(0,0))=COL((a,b)+d(1,0))=$
$COL((a,b)+d^2(0,1))=COL((a,b)+d(1,0)+d^2(0,1)).$)

In the full Multidimensional theorems the set $\{ (0,0), (0,1), (1,0), (1,1) \}$ will be replaced by an arbitrary finite set.

Multidimensional VDW:
Let $e\in N$. Let $F=\{\overline f_1, \overline f_2, \ldots, \overline f_k\}$ be a finite set of points in $Z^e$ (e.g., $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$ for the square case in the corollary to Multidim VDW). For all $c$, for any $c$-coloring $COL: Z^e\rightarrow [c]$, there exists $\overline a\in Z^e$, $d\in N$, $d\ne0$, such that
$COL(\overline a + d\overline f_1)= COL(\overline a + d\overline f_2) = \cdots =COL(\overline a + d\overline f_k).$

This was proven by Furstenberg and Weiss (Topological dynamics and combinatorial number theory, Journal d'Analyse Mathematique, Vol. 34, 61--85, 1978); however, it was later observed that it follows from the (ordinary) Hales-Jewitt Theorem.

Furstenberg and Katznelson also proved a density version of the Multidimensional VDW Theorem (An ergodic Szemeredi's theorem for commuting transformations, Journal d'Analyse Mathematique, Vol. 34, 275--291, 1978). Roughly speaking, if $A\subseteq Z^d$ is dense enough then there exists $\overline a\in Z^e$, $d\in N$, $d\ne 0$ such that $\{ \overline a+d\overline f \mid f\in F \}\subseteq A$.

Consider the functions

$\overline a + d\overline f_1, \overline a + d\overline f_2, \cdots, \overline a + d\overline f_k.$

One may consider replacing these functions with a more complicated function of $d$ and $\overline f_1, \ldots, \overline f_k$. This leads to the following theorem.

Multidimensional Poly VDW:
Let $e,r\in n$. Let $p: Z^r \rightarrow Z^e$. Let $F=\{\overline f_1, \overline f_2, \ldots, \overline f_s\}$ be a finite set of points in $Z^r$. Let $f_i = (f_{i1},\ldots,f_{ir}).$ For all $c$, for any $c$-coloring $COL: Z^e\rightarrow [c]$, there exists $\overline a\in Z^e$, $d\in Z^r$, $d=(d_1,\ldots,d_r)$, $d\ne \overline 0$, such that

$COL(\overline a + P(d_1f_{11},d_2f_{12},\ldots,d_rf_{1r}))= COL(\overline a + P(d_1f_{21},d_2f_{22},\ldots,d_rf_{2r}))$
$=COL(\overline a + P(d_1f_{31},d_2f_{r2},\ldots,d_rf_{3r}))$
$\vdots$
$COL(\overline a + P(d_1f_{s1},d_2f_{r2},\ldots,d_rf_{sr}))$

This was first proven by Bergelson and Leibman (Polynomial extensions of van der Waerden's and Szemeredi's theorems, Journal of the American Math Society 1996, Vol. 9, 725--753.

They actually proved a density version.

There is an alternative proof by Bergelson and Liebman (Set-polynomials and Polynomial extension of the Hales-Jewett Theorem, Annals of Math, Vol. 150, 1999, 33-75.}

The proof is in two steps

Prove the Poly Hales-Jewett Theorem (henceforth Poly HJ). (This proof is not elementary.)
Prove Multi-dimensional Poly VDW Theorem from Poly HJ. (This part was elementary.)

There is a purely combinatorial proof of the Multi-dimensional Poly VDW Theorem, though it is not stated in the literature:

Walters has a combinatorial proof of Poly HJ in the paper of his mentioned in my last post.
As noted above, Bergelson and Leibman showed how to get from the Poly HJ theorem to the Multi-dimensional Poly VDW theorem.

Putting all this together there is an elementary proof of the Multi-dimensional Poly VDW theorem. There is a general version as well, similar to the Gen Poly VDW from
my last post, but I won't state it here.

These types of theorems have been generalized in Polynomial Szemeredi theorems for countable modules over integral domains and finite fields by Bergelson, Leibman, and McCutcheon, Journal d'Analyse Mathematique, Vol 95, 243--296, 2005.

There has also been some work on restricting what $d$ or $\overline d$ could be in the above theorems. We state the easiest of such theorems. It is derivable from the (ordinary) Hales-Jewitt theorem.

VDW's with $d$ restricted:
Let $C\subseteq N$. Let $D$ be the set of all sums of distinct elements of $C$. For all $c,k\in N$, for any $c$-coloring $COL:Z \rightarrow [c]$ there exists $a\in Z$, $d\in D$, $d\ne 0$, such that

$COL(a) = COL(a+d) = COL(a+2d) = \cdots = COL(a+(k-1)d).$

More complicated versions of this for multidimensional polynomials were proven by Bergelson and McCutcheon (An Ergodic IP Polynomial Szemeredi Theorem by Bergelson and McCutcheon. Memoirs of the American Math Society, Vol 46, 2000.

Open Problems:

Consider the one-dimensional VDW theorem over the reals. Is there an easy analytic proof of this, or of some subcases of it?
If we allow polynomials with constant term what happens. More concretely: For all finite sets $F\subseteq Z[x]$, determine $c$ such that:
- For any $c$-coloring $COL:Z\rightarrow [c]$ there exists $a,d\in Z$, $d\ne 0$, such that $\{ a+p(d) \mid p\in F\}$ is monochromatic.
- There exists a $c+1$-coloring $COL:Z\rightarrow [c]$ such that for all $a,d\in Z$, $d\ne 0$, $\{ a+p(d) \mid p\in F\}$ is not monochromatic.
Everything I've mentioned above except the Poly HJ theorem has a density analoge that is difficult to proof. Find easier proofs. This is not well defined since it depends on how you define `easier'. Combinatorial may be one definition, but those can be rough too.

I would like to thank Alexander Leibman for his help in preparing this post.

But most disturbingly ...

2007-01-24T17:54:00.000-08:00

My new hero is the student in a class of mine who sent me the following email:

There is always a student who shows up 10 minutes late to each of the (...) lectures, carrying a box of takeout food. He proceeds to noisily eat it while you lecture. This is highly distracting [as well as disturbing; this guy doesn't know how to use chopsticks], especially for those of us who chose to follow the rules. Please take some action as to inform students that eating in class is disrespectful not only to you, but distracting to other students who are trying to take notes. Thanks.

See, eating noisily during class is annoying enough. But not knowing how to use chopsticks? That's disturbing!

The Polynomial van der Waerden Theorem

2007-01-19T13:40:00.000-08:00

[Bill Gasarch, known online for his frequent contributions to the Complexity Blog and for his liberal USE of capital LETTERS, has been reading about the "polynomial" and "multi-dimensional" versions of van der Waerden's theorem (the original theorem being "linear" and "one-dimensional") and he is going to tell us about it. Enjoy. -- Luca]

Guest Posting by William Gasarch (gasarch@cs.umd.edu)

This is a one of two Guest Posting on the Polynomial van der Waerden Theorem (henceforth Poly VDW). This posting is on the one-dimensional Poly VDW; however,my next posting will be on the Multidimensional Poly VDW. Throughout this posting `Poly VDW' means `One Dimensional Poly VDW'

Our starting point is VDW's theorem, which is the same starting point Luca had in his postings on Szemeredi's theorem. (here, here, here, here, and here.) But I go in a different direction.

VDW's:
For all $c,k\in N$, for any $c$-coloring $COL:Z \rightarrow [c]$, there exists $a,d\in Z$, $d\ne 0$, such that

$COL(a) = COL(a+d) = COL(a+2d) = \cdots = COL(a+(k-1)d).$

The original proof ofVDW's Theorem was an induction on the following ordering $\omega^2$ on $(k,c)$

$(1,1)<(1,2)<\cdots<(2,1)<(2,2)<\cdots<(3,1)<(3,2)<\cdots.$

For example the proof of $(4,2)$ depends on the theorem being true for $(3,L)$ where $L$ is very large. Shelah (Primitive recursive bounds for van der Waerden numbers, Journal of the American Math Society, Vol 1, 1-15, 1988) has a proof that avoids this type of induction and hence yields a much slower growth rate for the VDW numbers (which we are not discussing here).

Consider the functions

$a, a+d, a+2d, \ldots, a+(k-1)d.$

One may consider replacing $d, 2d, 3d, \ldots, (k-1)d$ with polynomials in $d$. This leads to the following theorem.

Poly VDW:
For all $c\in N$, for all $p_1,\ldots,p_k \in Z[x]$ such that $(\forall i)[p_i(0)=0]$, for any $c$-coloring $COL:Z\rightarrow [c]$ there exists $a,d\in Z$, $d\ne 0$, such that

$COL(a) = COL(a+p_1(d)) = COL(a+p_2(d)) = \cdots = COL(a+p_k(d)).$

The condition $(\forall i)[p_i(0)=0]$ is needed since if the $p_i$'s were constants the theorem would be false. It is an open problem to look at particular sets of polys with constant term.

This was first proven by Bergelson and Leibman (Polynomial extensions of van der Waerden's and Szemeredi's theorems, Journal of the American Math Society, Vol. 9, 1996, 725--753.)

The proof uses ergodic (non-elementary) techniques. They actually proved a density version.

Density Poly VDW:
For all $p_1,\ldots,p_k \in Z[x]$ such that $(\forall i)[p_i(0)=0]$, for all sets $A\subseteq Z$ of positive density, there exists $a,d\in Z$, $d\ne 0$, such that

$a, a+p_1(d), a+p_2(d),\ldots, a+p_k(d)\in A. $

Walters has a purely combinatorial proof of the Poly VDW Theorem (Combinatorial Proofs of the Polynomial van der Waerden Theorem and the Polynomial Hales-Jewitt Theorem Journal of the London Math Society, Vol 61, 2000, 1-12.)

The proof used an $\omega^\omega$ ordering as follows.

For every finite set $F\subseteq Z[x]$ such that $(\forall p\in F)[p(0)=0]$ we associate a tuple $(n_e,\ldots,n_1)$ where the largest degree polynomial in $F$ is degree $e$, and, for all $i$, $1\le i\le e$, $n_i$ is the number of different coefficients of $x^i$ that occur in polynomials of degree $i$ in $F$.

Let $PVDW(n_e,\ldots,n_1)$ mean that Poly VDW holds for all sets of polys $F$ of type $(n_e,\ldots,n_1)$. The ordinary VDW theorem can be viewed as $\bigwedge_{i=1}^\infty PDVW(i)$.

The Poly VDW is proven by induction on the following $\omega^\omega$-ordering. Let $\sigma, \tau \in N^*$.

If $|\sigma| < |\tau|$ then $\sigma \preceq \tau$.
If $|\sigma|=|\tau|$ then order lexicographically. (e.g., $(2,3,4,999,10^{100}) < (2,3,5,1,0,0)$)

Having stated the Poly VDW one can now state a version of VDW over any infinite Commutative Ring $R$ (think Reals).

Gen Poly VDW:
Let $R$ any infinite commutative ring. For all $c\in N$, for all $p_1,\ldots,p_k \in R[x]$ such that $(\forall i)[p_i(0)=0]$, for any $c$-coloring $COL: R\rightarrow [c]$ there exists $a,d\in R$, $d\ne 0$, such that

$COL(a) = COL(a+p_1(d)) = COL(a+p_2(d)) = \cdots = COL(a+p_k(d)).$

This was proven by by Bergelson and Liebman (Set-polynomials and Polynomial extension of the Hales-Jewett Theorem, Annals of Math, Vol. 150, 1999, 33-75.}

The proof is in two steps

Prove the Poly Hales-Jewett Theorem (henceforth Poly HJ). (This proof is not elementary.)
Prove Gen Poly VDW from Poly HJ.
(This part was elementary.)

There is a purely combinatorial proof of the Gen Poly VDW theorem, though it is not stated in the literature:

Walters has a combinatorial proof of the Poly Hales Jewitt Theorem in the paper of his mentioned above.
As noted above, Bergelson and Leibman showed how to get from the Poly HJ Theorem to the Gen Poly VDW Theorem.

Coda 1:
Green and Tao proved that the set of primes has arbitrarily long arithmetic progressions.

More recently, Tao and Ziegler: have shown the following:

For any $p_1,\ldots, p_k \in Z[x]$ such that $(\forall i)[p_i(0)=0]$, there exists $a,d\in Z$, $d\ne 0$, such that

$a, a+p_1(d), a+p_2(d), \cdots a+p_k(d)$ are all prime

Coda 2:
The Maryland Math Olympiad is in two parts. Part I is 25 multiple choice questions (but some are quite hard). If you do well on part I then you can take part II which is 5 problems that need proof. We try to number the problems in order of difficulty. I placed the following problem on the 2006 High School Maryland Math Olympiad, as problem 5:

Let $COL$ be a 3-coloring of $\{1,\ldots,2006\}$. Show that there exists $x,y$ such that $COL(x)=COL(y)$ and $|x-y|$ is a square.

Of the 240 students who took the exam around 180 tried this one. Of those 5 got it right and 10 got partial credit. The proof I had in mind (which is the one the students used who got it right) is not a scaled down version of the proof of the poly VDW. I leave it to the reader to see if they can prove this.

iWant

2007-01-17T23:00:00.000-08:00

The new Prada phone looks good, and it comes with its own Prada leather case, but I'll wait for the iPhone (or whatever it will be called), which is conveniently coming out just before my birthday.

What I am really looking forward to, however, is the iCar. It will cost \$ 50,000, it will do 10 miles to the gallon, of a special gasoline sold only at Apple gas stations, and if there is a small mechanical problem you will have to ship it to Cupertino, where they will replace the whole engine for a convenient \$ 10,000 fee. But, as the first car without a steering wheel, it will be so cool!

2007-01-10T06:27:00.000-08:00

For the last few days Hong Kong has been swept by a cold wave, and one could see people wearing scarves, down jacket, fur-lined coats and so on, and everybody was complaining about the cold. Highs were in the 60s, and lows in the 50s. The fur-lined coats, by the way, are a cheat: the fur is only on the border of the hood and near the zipper, were it can be seen, but not on the inside of the coat.

Public transportation is fantastic. I love the double-decker buses for at least two reasons: it's nice to sit upstairs and look around, and they make me feel tall (the ceiling is just a few inches above my head). A single payment card is accepted by the several different companies that run buses, ferries, subway and trains; in fact, the card is also accepted by vending machines, convenience stores and many retail stores. It's as if in San Francisco one could shop at the Gap and pay with a Bart card.

Hong Kong is crowded, in a most enjoyable way. Not unlike Manhattan, here apartments are very small, so people spend most of their time, and do most of their socializing, outside. Plus, people seem to like to stay up until late. The result is that everywhere there are huge crowds of people who are out and about. After three months in LA, it's a great change of pace. The Chinese University is in the New Territories, which are as out of the way from the center as it sounds. If Hong Kong island is Manhattan, and Kowloon is Brooklyn, here we may as well be in Long Island. And, yet, the mall here in Sha Tin is open until 10pm or later, and it is lively until then every night.

I cannot decide if this is an expensive or a cheap city. Restaurants can be very cheap, but the cover charges in clubs and the cost of drinks in bars are a real scandal. Something should be done about it; perhaps someone should write angrily about such things on the internet.

The earthquake in Taiwan broke a major internet cable, and internet traffic has been slow in the south of China and here as well, so I could not post daily food updates. I apologizes to the countless disappointed readers (so far, Cantonese, dim sum, seafood, dim sum, hot pot, Shanghainese, Vietnamese, Western, Pekinese, dim sum, Cantonese).

The Auspicious Start

2007-01-02T21:28:00.000-08:00

Two days into 2007 and...

Recommendation letters: sent
Getting organized for new courses: done and done
Referee reports: [cough] [cough]
Bags: packed
Talks: prepared
For the 14+ hour flight: got a few books

And how considerate that they would time the Italian Cultural Festival to coincide with my visit, even at the cost of moving the Befana to January 12.

Breaking News!

2006-12-27T22:46:00.000-08:00

You may remember that, in July, Italy won the football Word Cup. No? Best defense ever? Materazzi? Headbutt? 意大利万岁? Anybody?

Anyways, I was in Rome that night, I borrowed a friend's camera, and I took some pictures on the street. I gave the camera back, and he told me he would email me the pictures "in a few days." I got the pictures today, which is what he meant. I suppose anybody who has sent me a paper to referee, only to be assured I would send the review "in a few days," is now nodding knowingly.

I did not know how the settings of the camera worked, it was night, we were never able to stop the car (except in traffic), so the pictures are dark and shaky, then the battery run out just when we got to the center, plus I ran out of gas, I had a flat tire, I didn't have enough money for cab fare, my tux didn't come back from the cleaners, an old friend came in from out of town, someone stole my car, there was an earthquake, a terrible flood, LOCUSTS!

Having dispensed with the excuses, in the interest of timely dissemination here are some of the pictures.

We start driving from Monte Sacro, a neighborhood in the North-East of the city, about 5 miles away from the center. It's less than two hours since the game is over, and a newspaper kiosk is selling day-after newspapers with chronicles of the game.

In this much time they wrote the articles, printed the papers, and got them all over the city, which is, of course, completely gridlocked. This shows that when something is really important, Italians can be efficient. (No, I don't know why there is advertising for Newsweek in a Monte Sacro newspaper kiosk.)

After more than an hour, we get to the Muro Torto, the wide road (with tunnels) that runs along historical walls and goes toward Piazza del Popolo.

Almost all the traffic is, of course, in the direction toward the center, which is where we are trying to go.

This gentleman has "W la fica" writeen on his chest. (Sorry, no translation.)

Since the traffic is not moving, one guy has the time to get out of his car and climb on top of a truck.

Then there is the group of guys running around in tighty whiteys.

This guy, instead, is jumping up and down on a Mercedes S-series. Note that he removed his shoes, so there is not risk of damaging the car.

The friend behind him, instead, his standing on the windshield. The Germans sure know how to make sturdy cars.

Then there is the Zidane coffin.

The lady in the red car is not showing a lot of enthusiasm. Seven people have fit into this small Citroen cabrio.

Note again the serious lady in the red car, and the fact that nobody is driving the Citroen. Carrying open alchoolic beverages in a car is actually legally in Italy. Driving this way, however, is allowed only on special occasions.

This is a Fiat 500, the car on which I learned how to drive. (No, I am not that old, it was a used car!)

This is the closest I got to taking a picture of Piazza del Popolo.

Catenaccio (heavy chain - the kind used to lock a gate) is the term used to define Italy's defense.

Slaughtering the Cow to Get the Butter

2006-12-25T15:16:00.000-08:00

Americans are fond of rankings and lists, and the end of the year is the time when you see top ten this and worst seven that wherever you look.

Media Matters has compiled a list of the 11 most outrageous comments of 2006 by right-wing commentators.

There is, for example, nationally syndacated obese radio host Rush Limbaugh pointing out that obesity is more prevalent in heavily Republican states and least prevalent in heavily Democratic ones, thus showing that obesity is caused by leftist liberal policies. But the best part is when he explains that, in dealing with the poor, the government is not teaching the poor how to slaughter the cow to get the butter, it just gives them the butter. Just listen to it.

Among the honorable mentions, nationally syndacated radio host Neal Boortz commented on the hairstyle of Representative Cynthia McKinney's of Georgia as follows: "She looks like a ghetto slut." Representative McKinney is black.

It is, however, the screen captions on Fox News which are the most hilarious.

Indonesia, Papua New Guinea, and Berkeley

2006-12-24T18:54:00.000-08:00

This is were the notable earthquakes of the last few days have taken place, according to the US geological survey web site. And Berkeley had the distinction of three earthquakes in four days, as reported, among other sources, in the People's Daily.

It must be especially annoying if you happen to be living on a tree.

An associated press article is so very reassuring:

But the minor earthquakes should not be interpreted as omens of a more destructive one to come, said Jessica Sigala, a geophysicist with the National Earthquake Information Center.

"It could mean there’s something coming, it could mean there’s nothing coming," Sigala said.

~~Merry Christmas!~~ Happy Holydays!

[Update 12/27: now that a real earthquake has hit Taiwan, this post sounds especially needless and petulant.]

Characters and Expansion

2006-12-21T19:07:00.000-08:00

In which we look at the representation theory of Abelian groups and at the discrete Fourier transform, we completely understand the eigenvalues and eigenvectors of the Cayley graph of an Abelian group, and we apply this powerful theory to prove that the cycle is a connected graph.

When we talked about group representations, we saw how to map each element of a group into a matrix in such a way that group addition becomes matrix multiplication.

In general, if $G$ is a finite group, then an n-dimensional representation of $G$ is a map

$\rho: G \rightarrow {\mathbb C}^{n\times n}$

such that $\rho$ is a group homomorphism between $G$ and the group of matrices $\rho(G)$. That is, we have that $\rho(g)$ is an invertible matrix for every $g$, $\rho(0)=I$, $\rho(a+b) = \rho(a) \times \rho(b)$ and $\rho(-g) = (\rho(g))^{-1}$.

(Scott will be delighted to know that the theory need not stop at finite matrices, and one may also look at representations mapping group elements into invertible linear transformations over an infinite-dimensional Hilbert space. To study finite groups, however, finite-dimensional representations are good enough.)

Note that $\rho$ need not be injective, and so, for every group, we can always define the 1-dimensional representation $\rho(g) = 1$ for every $g$. Perhaps unsurprisingly, this is usually called the trivial representation. The precise statement of a theorem of Frobenius that we mentioned earlier is that every non-trivial representation of $PSL(2,p)$ has dimension at least $(p-1)/2$.

In an Abelian group, however, there are plenty of 1-dimensional representations, and, in fact, all the information about the group is "encoded" in the set of its 1-dimensional representations. We will call a 1-dimensional representation a character of the group. (This equivalence holds only for finite groups, otherwise we need an extra condition.) Hence a character of a group $G$ is a mapping

$\chi: G \rightarrow {\mathbb C}$

such that $\chi(g) \neq 0$ for every $g$, $\chi(0)=1$, $\chi(a+b) = \chi(a)\cdot \chi(b)$ and $\chi(-g) = (\chi(g))^{-1}$. In a finite group $G$, we always have the property that if we add an element to itself $|G|$ times we get $0$; from this we can deduce that, if $\chi()$ is a character, then $\chi(g)$ must be a $|G|$-th root of 1, that is, it must be a number of the form $e^{2\pi x i/|G|}$ for some $x$. In particular, $|\chi(g)|=1$ for every $g$.

(For general groups, we say that $\chi$ is a character if it is a 1-dimensional representation and it has the property that $|\chi(g)|=1$ for every $g$. While the latter property is a consequence of the former for finite groups and, more generally, for torsion groups, this is not the case for other groups. For example, $\chi(x) := e^{x}$ is a 1-dimensional representation for $\mathbb Z$ but it is not a character.)

At first sight, it might look like a finite group might have an infinite number of characters (or at least that's what I thought when I first saw the definition). There is however a simple argument that shows that a finite group $G$ cannot have more than $|G|$ characters.

Consider the set of all functions of the form $f: G \rightarrow {\mathbb C}$; we can think of it as a $|G|$-dimensional vector space over $\mathbb C$. We have that the characters of $G$ are linearly independent, and so there cannot be more than $|G|$ of them. In fact, even more is true: the characters of $G$ are orthogonal to each other. For two functions $f,h$, define their inner product as

$(f,g) := \frac1 {|G|} \sum_{a\in G} f(a) \overline{g(a)} $

Then, if $\chi$ and $\eta$ are two different characters, we have

$(\chi,\eta) = \frac1 {|G|} \sum_{a\in G} \chi(a) \overline{\eta(a)}=0 $

The normalization in the definition of inner product is convenient because then we also have $(\chi,\chi)=1$ if $\chi$ is a character. (We will not prove these claims, but the proofs are very simple.)

We will now show that the cyclic group ${\mathbb Z}_N$ has indeed $N$ distinct characters $\chi_0,\ldots,\chi_{N-1}$. This means that this set of characters forms an orthonormal basis for the set of functions $f: {\mathbb Z}_N \rightarrow {\mathbb C}$, and that each such function can be written as a linear combination

$f(x) = \sum_{c=0}^{N-1} \hat f(c) \chi_c (x)$ (*)
where the coefficients $\hat f(c)$ can be computed as the inner product
$\hat f(c) = (f,\chi_c)$

(The equation (*) is the Fourier expansion of $f$, and the function $\hat f()$ is called the Fourier transform of $f$.)

Here is how to define the characters $\chi_c$: for each $c$, define $\chi_c(x):= e^{2\pi c x /N}$. It is immediate to verify that each such function is a character, and that, for $c=0,\ldots,N-1$ we are, indeed, defining $N$ different functions. By the previously mentioned results, there is no other function.

Let's see one more example: consider $({\mathbb Z}_2)^n$, that is, $\{0,1\}^n$ with the operation of bit-wise XOR. For each ${\mathbf a} = (a_1,\ldots,a_n)\in \{0,1\}^n$, define the function

$\chi_{\mathbf a} (x_1,\ldots,x_n) := (-1)^{\sum_i a_i x_i }$
We can again verify that all these $2^n$ functions are distinct, that each of them is a character, and so that they include all the characters of $({\mathbb Z}_2)^n$. The reader should be able to see the pattern and to reconstruct the $N_1\times \cdots N_k$ characters of the group
${\mathbb Z}_{N_1} \times \cdots \times {\mathbb Z}_{N_k}$
thus having a complete understanding of the set of characters of any given finite Abelian group.

At long last, we can get to the subject of expansion.

Let $A$ be a finite Abelian group, and $S$ be a set of generators such that if $a\in S$ then $-a\in S$. Definite the Cayley graph $G=(A,E)$ where every element of $A$ is a vertex and where $(a,b)$ is an edge if $a-b\in S$. This is cleary an $|S|$-regular undirected graph. Let $\chi_1,\ldots,\chi_{|A|}$ be the set of characters of $A$. Think of each character $\chi_i$ as an $|A|$-dimensional vector. (The vector that has the value $\chi_i(a)$ in the $a$-th coordinate.) Then these vectors are orthogonal to each other. We claim that they are also eigenvectors for the adjacency matrix of $G$.

Note a surprising fact here: the graph $G$ depends on the group $A$ and on the choice of generators $S$. The eigenvectors of the adjacency matrix, however, depend on $A$ alone. (The eigenvalues, of course, will depend on $S$.)

The proof of the claim is immediate. Let $M$ be the adjacency matrix of $G$, then the $b$-th entry of the vector $\chi_i \times M$ is

$\sum_{a\in A} \chi_i(a) M(a,b) = \sum_{s\in S} \chi_i(b+s) =$
$ \sum_{s\in S} \chi_i(b)\chi_i (s) = \chi_i (b) \sum_{s\in S} \chi_i(s)$
We are done! The vector $\chi_i$ is indeed an eigenvector, of eigenvalue $\sum_{s\in S} \chi_i(s)$. Since we have $|A|$ eigenvectors, and they are linearly independent, we have found all eigenvalues, with multiplicities.

Let's look at the cycle with $N$ vertices. It is the Cayley graph of ${\mathbb Z}_N$ with generators $\{-1,1\}$. We have $N$ eigenvalues, one for each $c=0,\ldots,N$, and we have
$\lambda_c = \chi_c(-1) + \chi_c(1) = e^{-2\pi c i/N} + e^{-2\pi c i/N}$
this may seem to contradict our earlier claim that all eigenvalues were going to be real. But two lines of trigonometry show that, in fact,
$\lambda_c = 2 \cos (2\pi c/N)$
As expected in a 2-regular graph, the largest eigenvalue is $\lambda_0 = 2\cos(0)=2$. The second largest eigenvalue, however, is $2\cos(2\pi /N$, which is $2-\Theta(1/N^2)$. This means that the expansion of the cycle is at least $\Omega(1/N^2)$ and, in particular, the cycle is a connected graph!

(After we are done having a good laugh at the expense of algebraic graph theory, I should add that this calculation, plus some relatively easy facts, implies that a random walk on the cycle mixes in $O(N^2)$ steps. Not only this is the right bound, but it is also something that does not have a completely straightforward alternative proof.)

We do a little better with the hypercube. The hypercube is the Cayley graph of the group $({\mathbb Z}_2)^n$ with the generator set that contains all the vectors that have precisely one 1. Now we have one eigenvalue for each choice of $(a_1,\ldots,a_n)$, and the corresponding eigenvalue is
$\sum_{i=1}^n (-1)^{a_i}$.

The largest eigenvalue, when all the $a_i$ are zero, is $n$, as expected in an $n$-regular graph. The second largest eigenvalue, however, is at most $n-2$. This means that the expansion of the hypercube is at least 1. (As it happens, it is precisely 1, as shown by a dimension cut.)

Applied Philosophy

2006-12-17T17:37:00.000-08:00

This weekend the New York Times magazine has an article by Princeton philosopher Peter Singer, on the subject of philantropy, poverty and ethics.

Singer is known for his position that all human lives have the same value, a position that sounds entirely uncontroversial until one starts to explore its ramifications. Consider for example the case of real estate investor Zell Kravinsky.

Kravinsky gave almost all of his \$45 million real estate fortune to health-related charities, retaining only his modest family home in Jenkintown, near Philadelphia, and enough to meet his family’s ordinary expenses. After learning that thousands of people with failing kidneys die each year while waiting for a transplant, he contacted a Philadelphia hospital and donated one of his kidneys to a complete stranger.

[...] Kravinsky has a mathematical mind — a talent that obviously helped him in deciding what investments would prove profitable — and he says that the chances of dying as a result of donating a kidney are about 1 in 4,000. For him this implies that to withhold a kidney from someone who would otherwise die means valuing one’s own life at 4,000 times that of a stranger, a ratio Kravinsky considers “obscene.”

I have to say that I have never found Utilitarianism convincing (and you don't want to get an Utilitarian started with his mental experiments), even though I admit that there is hardly any known better premise on which to reason about Ethics.

The article has a lot of interesting information, including the following argument, which I had never seen before in these terms:

Thomas Pogge, a philosopher at Columbia University, has argued that at least some of our affluence comes at the expense of the poor. He bases this claim not simply on the usual critique of the barriers that Europe and the United States maintain against agricultural imports from developing countries but also on less familiar aspects of our trade with developing countries. For example, he points out that international corporations are willing to make deals to buy natural resources from any government, no matter how it has come to power. This provides a huge financial incentive for groups to try to overthrow the existing government. Successful rebels are rewarded by being able to sell off the nation’s oil, minerals or timber.

In their dealings with corrupt dictators in developing countries, Pogge asserts, international corporations are morally no better than someone who knowingly buys stolen goods [...]

Zeilberger on why P differs from NP

2006-12-14T18:08:00.000-08:00

Scott Aaronson, Lance Fortnow and Bill Gasarch have discussed the reasons why they believe P differs from NP here, here and here.

Doron Zeilberger, motivated by Avi Wigderson's talk in Madrid devotes his latest opinion to the subject. (Via Luca A.)

His dismissal of the creativity cannot be mechanized argument is based on his long-standing belief (which I share) that human creativity, especially human mathematical creativity can in fact be emulated by algorithms and that, in the long run, algorithms will end up being superior. I think this is a misunderstanding of the argument, whose point is rather that creating something good (by humans and by algorithms) seems to require much more effort than appreciating something good, and that there are levels of "genius" which we would be able to recognize if we saw them but that we are prepared to consider infeasible. In the end, this is the same as the a fool can ask more questions than a wise man can answer argument that Zeilberger himself proposes.

Then there is the issue of whether it is fair to say that "P $\neq$ NP is a statement that affirms its own intractability." Indeed, the P versus NP question is a statement about asymptotics, while proving it is a problem of finite size.

I have two observations.

One is that the "natural proofs" results show that, assuming strong one-way functions exist (an assumption in the "ballpark" of P $\neq$ NP) there are boolean functions that are efficiently computable but have all the efficiently computable properties of random functions. This means that any circuit lower bound proof must work in a way that either would fail when applied to random functions (and there are reasons why it is difficult to come up with such proofs) or would rely on hard-to-compute properties of the function in question. So although the proof is a finite object, it does define an "algorithm" (the one that describes the properties of the function that are used in the proof) and such algorithm cannot be asymptotically efficient.

The other is that, however cleaner our theories are when formulated asymptotically, we should not lose sight of the fact that the ultimate goals of complexity theory are finite results. It will be a historic milestone when we prove that P $\neq$ NP by showing that SAT requires time at least $2^{-300} \cdot n^{(\log n) / 100 }$, but the real deal is to show that there is no circuit of size less than $2^{300}$ that solves SAT on all formulae having 10,000 clauses or fewer. The statements that we care about are indeed finite.

Russian humor

2006-12-13T13:08:00.000-08:00

The January issue of the Notices of the AMS is out, and it contains an article by Anatoly Vershik on the Clay Millenium prize. You may remember a discussion we had on the wisdom of awards in general, in the context of the AMS idea of creating a fellows program and of the pros and cons of having a best paper award at STOC and FOCS.

Vershik returns to some of the standard points in this debate, and makes a few new ones. Although the tone of the article is completely serious, there are hints of deadpan humor (especially in the way he characterizes the opinions of others).

There is really no connection, but I was reminded of Closing the collapse gap, the hilarious presentation by Dmitry Orlov (found via the Peking Duck), in which he argues that when the U.S. economy will collapse, we will be much less prepared than the Russians were, and we will be in much deeper troubles. As stated in the comments at the Peking Duck, when Russians are deadly serious about something, they deal with it through dark humour.

Eigenvalues and expansion

2006-12-12T18:09:00.000-08:00

Before trying to describe how one reasons about the eigenvalues of the adjacency matrix of a Cayley graph, I would like to describe the "easy direction" of the relationships between eigenvalues and expansion.

First, a one-minute summary of linear algebra. If $A$ is an $n\times n$ matrix, then a (column) non-zero vector $x$ is an eigenvector of $A$ provided that, for some scalar $\lambda$, we have $Ax= \lambda x$. If so, then $\lambda$ is an eigenvalue of $A$. A couple of immediate observations:

The equation $Ax=\lambda x$ can be rewritten as $(A-\lambda I)x = 0$, so if $\lambda$ is an eigenvalue of $A$ then the columns of the matrix $A-\lambda I$ are not linearly independent, and so the determinant of $A-\lambda I$ is zero. But we can write $det(A-\lambda I)$ as a degree-$n$ polynomial in the unknown $\lambda$, and a degree-$n$ polynomial cannot have more than $n$ roots.

So, an $n\times n$ matrix has at most $n$ eigenvalues.
If $\lambda$ is an eigenvalue of $A$, then the set of vectors $x$ such that $Ax=\lambda x$ is a linear space. If $\lambda_1$ and $\lambda_2$ are different eigenvalues, then their respective spaces of eigenvectors are independent (they only intersect at $0$).

If $A$ is a symmetric real-valued matrix, then a series of miracles (or obvious things, depending on whether you have studied this material or not) happen:

All the roots of the polynomial $det(A-\lambda I)$ are real; so, counting multiplicities, $A$ has $n$ real eigenvalues.
If $\lambda$ is an eigenvalue of $A$, and it is a root of multiplicity $k$ of $det(A-\lambda I)$, then the space of vectors $x$ such that $Ax=\lambda x$ has dimension $k$.
If $\lambda_1 \neq \lambda_2$ are two different eigenvalues, then their respective spaces of eigenvectors are orthogonal

From this fact, it is easy to conclude that starting from symmetric real matrix $A$ we can find a sequence of $n$ numbers

$\lambda_1\geq \ldots \geq \lambda_n$

and a sequence of $n$ unit vectors $v_1,\ldots,v_n$ such that the $v_i$ are orthogonal to each other and such that $A v_i = \lambda_i v_i$.

Now the claim is that these $n$ numbers and $n$ vectors completely describe $A$. Indeed, suppose that we are given a vector $x$ and that we want to compute $Ax$. First, we can write $x$ as a linear combination of the $v_i$:

$x= \alpha_1 v_1 + \cdots \alpha_n v_n$

and since the $v_i$ are an orthonormal basis, we know what the coefficients $\alpha_i$ are like: each $\alpha_i$ is just the inner product of $x$ and $v_i$.

Now, by linearity, we have

$Ax = \alpha_1 A v_1 + \cdots \alpha_n A v_n$

and, since the $v_i$ are eigenvectors,

$= \alpha_1 \lambda_1 v_1 + \cdots + \alpha_n \lambda_n v_n$

So, once we express vectors in the basis defined by the $v_i$, we see that multiplication by $A$ is just the effect of multiplying coordinate $i$ by the value $\lambda_i$.

But there is more. Recall that $\alpha_i = v_i^T x$ and so we can also write

$Ax = (\lambda_1 v_1^T v_1) x + \cdots + (\lambda_n v_n^T v_n) x$

and so, in particular, matrix $A$ is just

$A = \lambda_1 v_1^T v_1 + \cdots + \lambda_n v_n^T v_n $

a sum of $n$ rank-1 matrices, with the coefficients of the sum being the eigenvalues.

Let now $A$ be the adjacency matrix of a $d$-regular undirected graph (so $A$ is real-valued and symmetric), $\lambda_1\geq \cdots \geq \lambda_n$ be its eigenvalues, and $v_1,\ldots,v_n$ be a corresponding set of orthonormal eigenvectors.

It is not hard to see (no, really, it's two lines, see the bottom of page 2 of these notes) that all eigenvalues are between $d$ and $-d$. Also, $d$ is always an eigenvalue, as shown by the eigenvector $(1,\ldots,1)$. This means that $\lambda_1 = d$ and we can take

$v_1 = \left( \frac 1 {\sqrt n},\cdots, \frac 1 {\sqrt n} \right)$

and we have

$A = (d v_1^T v_1) x + \cdots + (\lambda_n v_n^T v_n) x$

Suppose now that all the other $\lambda_i$, $i=2,\ldots,n$ are much smaller than $d$ in absolute value. Then, intuitively, the sum is going to be dominated by the first term, and $A$ behaves sort of like the matrix $(d v_i^T v_i)$, that is, the matrix that has the value $d/n$ in each entry.

You may be skeptical that such an approximation makes sense, but see where this leads. If our graph is $G=(V,E)$, and $(S,V-S)$ is a cut of the set of vertices into two subsets, let $1_S$ be the $n$-dimensional vector that is 1 in coordinates corresponding to $S$ and 0 in the other coordinates, and define $1_{V-S}$ similarly. Then the number of edges crossing the cut is precisely

$1_S^T A 1_{V-S}$

and if we replace $A$ by the matrix that has $d/n$ in each coordinate we get the approximation $|S|\cdot|V-S|\cdot d /n$, which is the expected number of edges that would cross the cut if we had a random graph of degree $d$. This is pretty much the right result: if $|\lambda_2|,\ldots, |\lambda_n|$ are all much smaller than $d$, and if $|S|$ and $|V-S|$ are at least a constant times $n$, then the number of edges crossing the cut is indeed very close to $|S|\cdot |V-S| \cdot d/n$. This result is known as the Expander Mixing Lemma, and the proof is just a matter of doing the "obvious" calculations. (Write $1_S$ and $1_{V-S}$ in the eigenvector basis, distribute the product, remember that the $v_i$ are orthogonal, use Cauchy-Schwarz ...)

It is perhaps less intuitive that, provided that all other eigenvalues are at least a little bit smaller than $d$, then a reasonably large number of edges crosses the cut. In particular, if $|S| \leq n/2$ and if $\lambda_2 \leq d-\epsilon$, then at least $\epsilon |S|/2$ edges cross the cut. That is, if all eigenvalues except the largest one are at most $d-\epsilon$ then the edge expansion of the graph is at least $\epsilon/2$. (It takes about five lines to prove this, see the beginning of the proof of Thm 1 in these notes.)

To summarize: the adjacency matrix of an undirected graph is symmetric, and so all eigenvalues are real. If the graph is $d$-regular, then $d$ is the largest eigenvalue, and all others are between $d$ and $-d$. If all the others are between $d-\epsilon$ and $-d$, then the graph has edge-expansion $\epsilon/2$ (or better).

Madonna and Letterman (1994)

2006-12-10T12:56:00.000-08:00

As a break from expanders and groups, here is Madonna's 1994 notorious appearence on Letterman's show.

The incident has its own Wikipedia entry, one more piece of evidence that Wikipedia is superior to the Encyclopaedia Britannica.

Group representation

2006-12-08T15:57:00.000-08:00

(As will become clear soon, I am totally out of my depth: Readers who find glaring mistakes, and even small ones, should note them in the comments.)

In the previous post on expanders we left off with the observation that if we want to construct an expanding Cayley graph, then we need to start from a group where all $n$ elements of the group can be obtained by a sum of $O(log n)$ terms chosen, with repetitions, from a set of $O(1)$ generators; this means that a constant root of the $n^{O(1)}$ ways of rearranging such sums must lead to different results. The group, then, has to be non-commutative in a very strong sense.

I will describe a way in which a group used to construct expanders is "very non-commutative." This will not be a sufficient property for the expansion, but it is closely related and it will come up in the paper of Gowers that we will talk about later.

With this objective in mind, let's see the notion of group representation. Let's start from the simplest group, the cyclic group of $N$ elements $Z_N$ with the operation of addition (or $Z/NZ$ as mathematicians write). One can visualize this group as $N$ points equally spaced along a circle in the plane, with element $a$ forming an angle of $2\pi a/ N$ with the $x$ axis. If we want to add an element that forms an angle $\alpha$ to an element that forms an angle $\beta$, that's the same as putting the "two angles next to each other" and we get a point that forms an angle $\alpha+\beta$. More algebraically, we identify an element $a$ with the complex number $e^{2\pi a i/n}$ and we realize group addition as multiplication of complex numbers. There is, however, another way of visualizing the cyclic group on a cycle. We can think of group element $a$ as the operation that takes a point on the cycle and moves it by an angle of $2\pi a/N$. Addition of group elements now corresponds to "composition," that is, corresponds to applying one rotation after the other.

In this view, element $a$ is now the function that maps complex number $x$ into complex number $x\cdot e^{2\pi a i/N}$.

Suppose now that our group is a product $Z_{N_1} \times \cdots \times Z_{N_k}$ of cyclic groups. This means that a group elements if a $k$-tuple of the form $(a_1,\ldots,a_d)$, and that

$(a_1,\ldots,a_d) + (b_1,\ldots,b_d) = (a_1+b_1 \bmod N_1,\ldots,a_k+b_k \bmod N_k)$

It now makes sense to view a group element $(a_1,\ldots,a_d)$ as a "high-dimensional rotation" operation that takes in input $k$ complex numbers $(x_1,\ldots,x_k)$ and outputs the $k$ complex numbers

$(x_1 \cdot e^{2\pi a_1 i /N_1},\ldots, x_k \cdot e^{2\pi a_k i /N_k})$

If we take this view, we have, again, the property that group addition becomes composition of functions. Note, also, that the function that we have associated to each group element is a very simple type of linear function: it is simply multiplication of $x$ times a diagonal matrix that has diagonal

$(e^{2\pi a_1 i /N_1},\ldots, e^{2\pi a_k i /N_k})$

Notice, also, that if $f$ is a function of the form $f(x) = A\cdot x$, where $A$ is a matrix, and $g$ is a function of the form $B\cdot x$ where $B$ is a matrix, then $f(g(x))= A\cdot B\cdot x$. That is, for linear functions, function composition is the same as matrix multiplication.

To summarize, we have started from the group $Z_{N_1} \times \cdots \times Z_{N_k}$, and we have found a way to associate a complex-valued diagonal matrix to each group element in such a way that group addition becomes matrix multiplication.

It is known that all finite Abelian groups can be written as $Z_{N_1} \times \cdots \times Z_{N_k}$, so this type of representation via diagonal matrices is possible for every finite Abelian group.

What about more general groups? If $G$ is an arbitrary finite group, it is possible to associate to each element a block-diagonal matrix in such a way that group addition becomes matrix multiplication.

(It is common to call a group operation "multiplication" when a group is not Abelian, but for consistency with the rest of the post I will keep calling it addition.)

(By the way, it is also possible to represent infinite groups by associating a linear operator to each group element, but we will only discuss finite groups here.)

If the group is Abelian, then the matrices are diagonal, that is, they are block-diagonal matrices with "block size one." So one way of quantifying "how non-Abelian" is a group is to consider how small the blocks can be in such matrix representations. That's the dimension of the representation.

Here is an example of a family of groups whose representations cannot be low-dimensional. Let $p$ be a prime (it could also be a prime power) and let us consider $2 \times 2$ matrices whose entries are integers $\bmod p$. Let us restrict ourselves to matrices whose determinant is 1 modulo $p$, and consider the operation of matrix multiplication (where, also, all operations are mod $p$). This set of matrices forms a group, because the matrices are invertible (the determinant is non-zero) and the set contains the identity matrix and is closed under product. This group is called $SL(2,p)$. The group $SL(2,p)$ contains the tiny subgroup of two elements $\{ I,-I\}$; in the representation of $SL(2,p)$ this shows up as a block of size 1. If we take the quotient of $SL(2,p)$ by $\{ I,-I \}$ then we get another group, which is called $PSL(2,p)$.

It is now a theorem of Frobenius that every representation of $PSL(2,p)$ has dimension at least $(p-1)/2$. This is really large compared to the size of $PSL(2,p)$: the group $SL(2,p)$ has $p(p-1)^2$ elements, and so $PSL(2,p)$ has $p(p-1)^2/2$ elements. The dimension of the representation is thus approximately the cube root of the number of elements of the group.

Going back to representations of Abelian groups, we see that, in that case, not only each block had size one, but also that the entire matrix had size at most logarithmic in the number of elements of the group. This shows that $SL(2,p)$ and $PSL(2,p)$ are, at least in this particular sense, "very non-Abelian," and it is an encouraging sign that they may be useful in constructing expanders and other quasi-random objects.

On his way toward a question about subsets of groups not containing triples of the form $\{ a, b, a+b\}$, Gowers shows that every dense Cayley graph constructed on $PSL(2,p)$ has constant edge expansion. (By dense, we mean that the degree is $\Omega(n)$, where $n$ is the number of vertices.) This is a result that, assuming Frobenius theorem, has a simple proof, which I hope to understand and describe at a later point.

The celebrated Ramanujan graphs of Lubotzky, Phillips and Sarnak are constant-degree Cayley graphs constructed from $PGL(2,p)$, which is the same as $PSL(2,p)$ except that we put no restriction on the determinant. Their relationship between degree and eigenvalue gap is best possible. The analysis of Lubotzky et al. is, unfortunately, completely out of reach.

Expanders and groups

2006-12-06T15:20:00.000-08:00

I have started to read a new paper by Gowers titled Quasi-random groups. "Quasi-random" is the more-or-less standard term used to denote a single object that has some of the typical properties of a random object; this is distinct from the term "pseudo-random" which is more often applied to a distribution that satisfies a certain set of properties with approximately the same probability as the uniform distribution.

(The distinction is sometimes artificial: for example the support of a pseudorandom distribution can also be thought of as a quasi-random set. To add confusion, in older literature on extractors certain high-entropy sources were called "quasi-random" sources.)

Although the paper does not directly talk about expander graphs, it addresses related questions, and it gives an opportunity for a post (or more than one) on expander graph constructions.

Informally, an expander graph is a graph that, while having small bounded degree, is very well-connected. For example, a $\sqrt{n} \times \sqrt{n}$ grid can be disconnected into two equal-size connected components after removing just $\sqrt{n}$ edges. This means that a $\Omega(1)$ fraction of all pairs of vertices can be disconneted while only removing a $o(1)$ fraction of all edges; for this reason, we do not think of a 2-dimensional grid as a good expander. In a graph of degree $O(1)$ it is always possible to cut off $k$ vertices from the rest of the graph by removing $O(k)$ edges; a graph is an expander if this is best possible. That is, a graph is an expander if for every set of $k$ vertices (where $k$ is less than half of the total number of vertices) you need to remove at least $\Omega(k)$ edges to disconnect those vertices from the rest of the graph.

More quantitatively, a $d$-regular graph has edge expansion at least $\epsilon$ if for every set $S$ of vertices there are at least $\epsilon \cdot |S|$ edges going between vertices in $S$ and vertices not in $S$. (Provided $|S|$ is less than half the total number of vertices.)

We have a good construction of expanders if for fixed constants $\epsilon$ and $d$ we are able to construct $\epsilon$-expanders of degree $d$ with any desired number of vertices.

The applications of expander graphs are vast, they are useful to reduce randomness in probabilistic algorithms, they come up in certain constructions of data structures, of randomness extractors, and of error-correcting codes, and they have many applications in complexity theory. Most recently, Dinur's new proof of the PCP Theorem uses expanders. A great set of lecture notes on expanders is here, and not so great one is here (lectures 8-12 are on expanders).

Before the great zig-zag graph product revolution, almost all the good expander graph constructions were Cayley graphs of non-Abelian groups. Let's see what this means and how it helps.

If $G$ is a group and $D\subset G$ is a subset, then $G$ and $D$ define a $|D|$-regular graph with $|G|$ vertices as follows: every element of $G$ is a vertex, and vertices $u$ and $v$ are connected if $u-v \in D$. If we assume that, for every $a\in D$ we also have $-a \in D$, then we can think of the graph as being undirected.

A first trivial observation is that if $D$ is a set of generators, that is, if we can realize every element of $G$ as a sum of elements of $D$, then the graph is connected, otherwise it is disconnected.

Another point, which is true for all graphs, not just Cayley graphs, is that we can approximate the expansion of a graph by computing the eigenvalues of the adjacency matrix and looking at the difference between the largest and the second largest in absolute value. This was a point that I used to find mystifying, until I studied it and realized that it makes perfect sense. I may talk about it in another post, but I want to mention an amusing fact. The connection between eigenvalues and expansion has an easy direction (if there is a large eigenvalue gap then there is large expansion) and a difficult direction (if there large expansion then there must be large eigenvalue gap). The easy direction was "well known," and the difficult direction was discovered around the same time in two distinct communities for opposite reasons.

Alon discovered it while working on constructions of expanders. It was known how to construct graphs with noticeable eigenvalue gap which would then (by the "simple direction") be good expanders. This is because, for the algebraic constructions that we will talk about in a minute, it is easier to reason about the eigenvalues of the adjacency matrix than about the number of edges in a generic cut. Alon, by proving the hard direction, showed that the approach via eigenvalue can be taken "with no loss of generality,"

Others (Aldous and Diaconis? Jerrum and Sinclair? I never get this reference right) discovered the same result working on the problem of bounding the time that it takes for a random walk on certain graphs to converge to the stationary distribution. To answer such questions, one needs to know the eigenvalue gap of the graphs, a quantity that is difficult to estimate directly in important cases. For those graphs, however, it is possible to reason about the size of cuts, and hence, via the difficult connection, obtain results on the eigenvalue gap (and, thus, on the convergence time, or "mixing" time of a random walk).

This "difficult direction" result has also an important algorithmic application. The counterpositive statement is that if largest and second largest eigenvalue are close in value, then the graph is not expanding, so one can cut off a set of vertices by deleting a comparatively small number of vertices. The proof is algorithmic: given the eigenvector of the second largest eigenvalue, this small cut can be found efficiently. This is the principle at work in "spectral partitioning" algorithms, often used in practice (and, occasionally, in theory).

Well, that was a long digression, but it's also an interesting story. Back to our constructions of expander graphs, we want to describe a bounded-degree graph explicitly and prove that there is a noticeable gap between largest and second largest eigenvalue. If the graph is a Cayley graph derived from a group $G$ and set of generators $D$ (and $D$ is chosen properly), it turns out that the eigenvalues of the adjacency matrix of the graph can be explicitly computed by looking at the representations of the group $G$. If $G$ is Abelian (if the group operation is commutative), then the representation theory of $G$ is very simple and it is "just" the theory of Fourier transforms of functions $f: G \rightarrow C$ (where C are the complex numbers), which is much easier than it sounds.

Unfortunately, a Cayley graph based on an Abelian group can never be a good expander. To see why, you'll have to believe my claim that in a good expander with $n$ vertices the diameter is at most $O(\log n)$. Consider now an $n$-vertex Cayley graph of degree $d$. Every vertex $x$ is reachable from vertex $0$ via a path of length $O(\log n)$. That is, $x$ is the sum of $O(\log n)$ elements of the set $D$. Because of commutativity, we can rearrange the sum so that it looks as

$(a_1+ \ldots + a_1) + (a_2 + \ldots + a_2) +\ldots (a_d + \ldots + a_d)$

where $a_1,\ldots,a_d$ are the elements of $D$. We see that the sum is specified just by saying how many time each element of $D$ must be added, and so $x$ is specified by $d$ numbers, each between $1$ and $O(\log n)$. This gives $n \leq O((\log n)^d)$ which is a contradiction.

Indeed, we see that Cayley graphs based on Abelian groups fail very badly to have the required diameter condition: if the degree is $d$, there will be vertices at distance about $n^{1/d}$ from each other, a bound that is met by a $d$-dimensional grid.

Intuitively, then, we can get an expanding bounded-degree Cayley graph only if we start from a "very non-Abelian" group. But how do we quantify the "Abelianity" of a group, and what kind of groups are "very non-Abelian"? This will be the subject of the next post.

Post-modern cryptography

2006-12-04T19:00:00.000-08:00

Oded Goldreich has written an essay in response to two essays on "provable security" by Koblitz and Menezes. Oded says that "Although it feels ridiculous to answer [the claims of Koblitz and Menezes], we undertake to do so in this essay. In particular, we point out some of the fundamental philosophical flaws that underly the said article and some of its misconceptions regarding theoretical research in Cryptography in the last quarter of a century."

Neil Koblitz spoke here at IPAM in October on the somewhat related matter of how to interpret results in the Random Oracle model and in the Generic Group model. There is an audio file of his talk.

It's that time of the year

2006-11-29T21:56:00.000-08:00

By way of sinosplice,

Jingle Bells in Hakka

(Hakka is a family of dialects of Chinese spoken by ethnic Hakka people in some Southern provinces of China and also in Taiwan and Singapore.)

Now, that's radical

2006-11-20T20:39:00.000-08:00

Yesterday the New York Times ran an article on children raised by lesbian couples with the active involvement of a (usually gay) dad/donor (and, sometimes, of the dad's partner too), the arrangement popularized by the TV series Queer as Folk. With about half of marriages ending in divorce, many children are raised with three or four between parents and step-parents, living in different households, so one of the moms is right to protest that there is nothing exceptional about the families profiled in the articles. "We want the same things that every other family wants!" she said, "We shop at Costco; we shop at Wal-Mart; we buy diapers. We’re just average. We’re downright boring!"

One of the fathers, however, had something truly radical to say about what he hopes for a child, that he could become

a great mathematician who goes on to become famous and prove great new theories or something along those lines.

Hear, hear!

Don't taser me, I am a student

2006-11-18T09:48:00.000-08:00

That's the sign that many students were wearing yesterday on their shirts after a rally to protest an incident that happened in the library on Tuesday. A student who was without his ID card was shot four or five times with a "taser" (a device that produces an electric shock), including after being handcuffed.

In better LA news, this afternoon there is some kind of sports event involving a UC Berkeley team and a Los Angeles team. A Berkeley faculty member is organizing a viewing using a big screen TV in his lab (why does a computer science lab need a big screen?). The invitation email explained that "Cal can be conference champion if it wins Saturday, for the first time since 1959" and I can only assume that being conference champion is a good thing. Go Bears!

Call it, already

2006-11-08T21:44:00.000-08:00

Why did the liberal media call Florida for Bush in 2000 on a margin of less than .01%, while some news outlets are still calling Virginia too close to call after all votes are counted and there is a margin of more than .3%?

Finally!

2006-11-08T21:34:00.000-08:00

At long last, we can surrender to the terrorists and destroy the fabric of society. Why does America hate America so much?

On being second

2006-11-07T11:03:00.000-08:00

Of the several things I learned from Jon Kleinberg's talk at FOCS, a simple fact about the shape of the "influence of friends" curve has really been stuck in my mind.

The question is the relation between the number of friends or associates who do something, or believe something, and the likelyhood that we will join them. Jon showed the curves for two, quite unrelated, examples: the number of livejournal friends who belong to a "community" versus the likelyhood of joining the community, and the number of former coauthors who have published in a conference versus the likelyhood of publishing for the first time in that conference. In both cases, after accounting for statistical noise, the curves look roughly monotone (the more friends/ coauthors, the likelier to join the community / publish in the conference) and show a "diminishing return" correlation: each extra friend/ coauthor adds less than the previous one to the likelyhood. There is, however, an exception: the second friend/ coauthor is more influential than the first. The "diminishing returns" start from the third on. This makes intuitive sense: we may discard a rumor heard once, but pay more attention when we hear it again, or dismiss the hobby of one friend as eccentric but start seeing it as a more reasonable when a second friend joins, and so on.

I have been wondering if something similar (but harder to quantify) is true for research problems and research papers. Being the first to introduce a new problem/ direction is an accomplishment that we are all justly used to praise. I am not talking here about being the first to introduce NP-completeness, or Zero-knowledge proofs, but the run-of-the-mill innovative paper that we see every year that brings something fresh to the theory community. Even when a new definition or question is "in the air," it can be difficult to write the first paper about it, because our community typically does not accept a paper made only of definitions and descriptions of open problems. One needs technical results, and so we see many seminal papers that are forever remembered for their definitions, and that are burdened by technical results that are there just so that the paper could make it past the referees. It is thanks to the imaginative people who make it past such difficulties that our field does not get stuck in a rut.

But, in a way, after the first paper on a problem, the barrier for entry is even higher. The community may still be skeptic about the importance of the problem, and the second paper on the subject has no claim of innovation: it must be evaluated solely on its technical content. After a second paper appears, however, the problem becomes an "area," and it becomes considerably more appealing. The most famous example is probably NP-completeness, that really took off after Karp's paper.

But there are plenty of small contemporary examples. For example, Boaz Barak introduced in Random'02 a beautiful type of argument to prove hierarchy theorems for slightly non-uniform versions of probabilistic polynomial time. The question was not revisited for the next two years, until Fortnow and Santhanam proved in Focs'04 that the "slight non-determinism" could be reduced to one bit. The following year and half saw a flurry of activity that lead to five sets of results that coalesced into three papers, the last of which, by van Melkebeek and Pervyshev, is more or less the final word on hierarchy theorems with small advice given current techniques.

It really pleases to me to write in praise of second papers, in part because I have been involved in a few second papers myself. In 1991, Feigenbaum and Fortnow proved (in the Complexity Conference, at the time called the Structure in Complexity Theory conference) that a certain approach (namely, the use of non-adaptive random self-reductions) cannot work in showing that BPP$\neq$NP implies the existence of hard-on-average problems in NP. This was part of a larger research program aimed at understanding random self-reducibility, but it was the only paper to specifically address the question of whether average-case intractability in NP could be proved assuming only worst-case intractability. This fundamental question seems to have been neclected for more than a decade. In the final exam for the complexity class I taught in Fall'02, I added as an extra credit question the problem of proving an incomparable version of the Feigenbaum-Fortnow result (to consider a more general notion of reduction, but restricted to make only one query), and Andrej Bogdanov was the only one to turn in a complete answer. We started working from there, and presented in Focs'03 a proper generalization of Feigenbaum-Fortnow. After that, the question seems to have become popular again. Akavia, Goldreich, Goldwasser and Moshkowitch showed in Stoc'06 how to prove stronger results for the related question of basing one-way functions on BPP$\neq$NP, and Gutfreund, Shaltiel, and Ta-Shma and, more recently, Gutfreund and Ta-Shma have shown that some weak average-case complexity conclusion for NP can be based on worst-case complexity assumptions.

I also wrote the second paper on hardness amplifcation within NP, following up on Ryan O'Donnell brilliant generalization of Yao's XOR Lemma; the second paper (with Mossel and Shpilka) on the question of constructing pseudorandom generators in NC0, a question introduced by Cryan and Bro Miltersen, and more or less resolved by a breakthrough of Applebaum, Ishai, and Kushilevitz; and the second paper on approximation algorithms for unique games, an issue that was quickly revolsed by the work of Gupta and Talwar, Charikar, Makarychev and Makarychev, and Chlamtac, Makarychev and Makarychev.

So, unimaginative theoreticians of the world, unite and pursue problems that have been studied only once. You have nothing to lose but your time.

LA mysteries

2006-11-05T15:40:00.000-08:00

Why are, in this heat, women wearing those formless huge boots that look like moon boots covered in suede? And doesn't it feel odd when their friends are wearing flip-flops?

Why was the invitation to see an advance screening of Borat three weeks ago only valid for people age 17 to 34? The opinions of some 35 year olds can be priceless, however demographically undesirable they may be.

And what possesses people to cruise on a Lamborghini or a Ferrari? Toyota pickup trucks are for cruising. Italian race cars are for racing. If you can spend \$200,000 on a car you can most definitely afford a speeding ticket. And you certainly do not want to drive at 20 mph on the left lane (in a 35mph zone), even if there is a car with good-looking women on the right lane. Not when there are cars behind you that are trying to go somewhere.

Finally, not that it has anything to do with LA, but you must have heard the story of Tedd Haggard, the influential Evangelical pastor who allegedly used crystal meth (an illegal drug) and had a three-year relationship with a 49 year old male prostitute. In an interview (see below), he admits buying meth and meeting with the guy. But: he threw away the meth, each time, after buying it, without consuming it, and he only had massages from the guy. And how did he meet this guy, who advertised on the internet as an escort? Via a referral from a hotel in Denver. What was he doing in Denver? He goes to stay in hotels in Denver to write his books. Then, again, the insurgency in Iraq is on its last throes, so this is not a completely unlikely scenario.

What strikes me in this story is the 49 year old male prostitute. I don't mean to sound ageist, but, seriously, a 35 year old is too old to comment on a movie, but a 49 year old can be paid for sex?

Other people are striken by the fact that Haggard campaigned for a constitutional amendment to ban same-sex marriage. One is remainded of congressman Mark Foley, the former chairman of the House Caucus on Missing and Exploited Children, who was discovered to be quite the exploiter of minors himself.

One may think of such people as hypocrites, unless, that is, one is a reader of national review, where David Frum analyses the matter with rare moral clarity. You have to read the piece by yourselves to believe it but, in short, Frum is saying that it is more moral to live a lie and cheat on your wife than to live the life of an out gay man. The point is, if you really have to be gay, at least have the decency to be miserable about it and, if possible, ruin someone else's life.

Which somehow reminds me that the federal government is going to fund an initiative to promote abstinence among adults age 19 to 29. Twenty-nine! I assume they are recruiting male engineers as motivational speakers and role models.

The hard science of Sociology

2006-10-25T23:45:00.000-07:00

On Monday, the first talk I managed to attend was by Terry Sejnovski, of the Salk Institute, and I only got there towards the end of the talk. Starting from the question of how the brain manages to "do" vision, he talked about fascinating experiments that, among other things, test the rationality of conscious versus unconscious decisions (apparently, in complex decision-making involving lots of variables, "gut feelings" are better than conscious reasoning) and measure the surprisingly good "computational" ability of monkeys.

In the afternoon, Valiant delivered his talk on "accidental algorithms" to a standing-room-only packed audience. His main results are (1) a $\oplus P$-completeness result for $\oplus$-2SAT, even when restricted to planar instances, and (2) a polynomial time algorithm for $mod_7$-2SAT on planar instances. $\oplus P$ is the complexity class of problems that reduce to the question of whether a given non-deterministic Turing machine, on a given input, has an odd number of accepting computations. By the Valiant-Vazirani result, a $\oplus P$-complete problem is also NP-hard under randomized reductions, and, by Toda's theorem, is actually hard for all the levels of the polynomial hierarchy. The $\oplus$-2SAT problem is to determine whether a given 2SAT instance has an odd number of satisfying assignments. Apparently, this is the first natural $\oplus P$-complete problem for which there is a polynomial time algorithm that checks if the number of solutions is zero or non-zero. The $mod_7$-2SAT problem is, given a 2SAT formula, to determine if the number of assignment is or is not a multiple of 7. Valiant's algorithm is based on his earlier work on matchgate computations.

Afterwards, most people moved to Uri Feige's talk in the next room on finding witnesses of unsatisfiability for random 3CNF formulas. Previously, it was known how to find, with high probability, witnesses of unstatisfiability for a given random 3CNF formula with $n$ variables and about $n^{1.5}$ clauses. This new work by Feige, Kim and Ofek shows that witnesses of unsatisfiability exist for most random 3CNF formulas with $n$ variables and about $n^{1.4}$ clauses. (They do not give an efficient algorithm to find such witnesses.)

Nicholas Harvey gave the last talk of the day on his work on reducing the matching problem to matrix multiplication. Previous work had shown that matching can be solved in the same time as matrix multiplication, but the previous reduction was quite complex for general graphs. (And simpler for bipartite graphs.) Harvey gives a considerably more transparent new algorithm that reduces matching in general graphs to matrix multiplication. His talk was very clear and enjoyable, and I am grateful to Moses Charikar for recommending it. (Because of the word "matroid" in the title, I was going to skip to the talk.)

On Tuesday, Jon Kleinberg gave a spectacular invited talk on the kind of radically new results on sociology that one can extract from new datasets (resulting from people using large online retailers, joining online communities such as livejournal and myspace, and so on) and from algorithmic thinking. I did not take notes, and I could not find the slides online, so I can only offer a few snippets that I remember. In one of Jon's most celebrated results, he studied an idealized model of "social networks" made of a mix of "local" connections and of random "long-distance" connections, and he showed that, in the resulting network, people would be able to find short paths among themselves only if the long-distance connections have a probability that is proportional the inverse of the square of the distance between two people. In the model, the local connections are laid out according to a grid, but the same result holds in a more general model where the local connections define a metric space, and the random connections are such that the probability that $i$ and $j$ are connected is proportional to the inverse of the number of people that are closer to $i$ than $j$ is. A study made on livejournal data shows that the "friends" that people make online are distributed in a way that is in spooky agreement with the above distribution.

Why do people make friends with precisely the only distribution that makes it easy to find short paths between themselves? The answer is unclear, but the outstanding thing is that a "law of human nature" seems to have been discovered, which could have never been formulated without thinking in terms of algorithms. Presumably, any explanation of this phenomenon will have to involve an algorithmic model of how people make connections online.

Another interesting question is the effect of "peer pressure" or community involvment. We are more likely to do something if our friends also do it (forgetting for a moment the question of what is the cause and what is the effect, that is whether we make friends with like-minded people, or whether we are influenced by what others do), but what exactly is the dependency between how many friends do something and how likely we are to do the same? Is there a "diminishing returns" curve, the way we are impressed by the first few friends who buy an ipod, and hence more and more likely to buy one ourselves, and then less and less impressed? Or is it a "critical mass" curve, the way skype is useless unless a lot of friends of ours are using it? There has been amusing work studying this question by looking at communities on livejournal and conferences on dblp. One can see how likely is a person to join a livejournal community as a function of the number of friends who are already members of the community, or see how likely is a person to publish for the first time in a conference as a function of former coauthors who have already published in the conference. The two curves are reasonably similar, and both are of "diminishing returns" type.

So one is more likely to, say, start publishing in a conference the more people one knows who are part of the community of that conference. Now, we can ask, given that one knows the same number of people in the community, does it make it more or less likely to start publishing there if the people know each other (say, have published together in the past), or if they do not know each other? To see the same question in other settings, if we hear a rumor, we are more likely to believe it if we hear it from more people. Furthermore, all other things being equal, we are more likely to believe it if we hear it from unrelated people, because it gives some kind of independent confirmation. If we are deciding whether to go to a party, we are also more likely to go the more people we know who are also going. In this case, however, all other things being equal, we are more likely to go if the people that we know who are going also know each other.

In the case of conferences, the former scenario is right. One is more likely to publish in a conference if the former coauthors who are part of the community are unrelated. Similarly, less "densely clustered" communities are the ones that are more likely to grow. There is a cause-and-effect problem here, in the sense that a community where everybody knows everybody else might be a mature and declining one, and being unappealing for such a reason; another explanation is that densely clustered community appear cliquish to outsiders, and are unappealing for such a reason.

There was more and more, in the talk. I have often heard that when Biology will become a "hard science" with a strong mathematical foundation, the mathematics will look familiar to those working in electrical engineering and in algorithms, and that theoretical computer science will be a major contributor to this future theoretical biology. What I did not know is that Sociology itself can become a hard science, and that theoretical computer science can play a major role in this transformation.

In theory, it was a good song

2006-10-24T00:23:00.000-07:00

After the business meeting, we moved to the adjacent room for the concert of Lady X and the Positive Eigenvalues. We were not supposed to bring alcohol in the conference rooms. There was of course beer at the business meeting, but only because Satish had smuggled it in. But there is a hotel security guy in the hallway, and he should not see us walk out of one conference room and then into another with our beer. And so, following directions given by Satish, a group of distinguished theoreticians, plus me, with their unfinished drinks, takes a back door and tries to get to the next room via the kitchens. This is a worthy start for the rest of the night. (The detour is ultimately unsuccessful, because the back door of the other conference room is locked, so we have to wait for the security guy to leave.)

Lady X is the lead singer, and the band, the Positive Eigenvalues, includes Christos Papadimitriou, Mike Jordan, guest star Anna Karlin, and a number of other Berkeleites (for some reason, all Italians).

They play a number of covers of rock songs that everybody but me recognizes. The crowd of theoreticians sings along, gets warmer and warmer, and starts dancing. The program committee chair surveys the room standing on an eponymous.

Then they play Smells like teen spirit, that even I recognize, a theory pogo breaks out, and those pogoing next to James Lee fly off in all directions. I make my way to the opposite side of the stage.

They also have one original song, titled In Theory. It starts

Picture a carpenter of sorts
he has the flu, he has the blues
he burns his oil every night
all night frustrated and confused

and worst of all he can't complain
in theory his job is plain

At the end, the crowd keeps asking for encores, and, by the time the concert ends, it is almost midnight.

(Pictures courtesy of Madhur Tulsiani.)

Off to a good start

2006-10-24T00:21:00.000-07:00

FOCS 2006 is off to a good start with Salil's talk on Sunday morning on realizing statistical Zero-Knowledge arguments for all of NP assuming one-way functions. A zero knowledge proof systems has two important requirements: the proof system must be sound, that is, a cheating prover cannot convince a verifier that a wrong statement is true, and it must be zero knowledge, meaning that a cheating verifier cannot obtain any information by interacting with the prover. Each requirement can come in a statistical version (in which the cheating party can be arbitrarily powerful) or a computational version (in which the requirement holds only for computationally bounded cheating parties).

If both are statistical, we have a Statistical Zero Knowledge proof system, which cannot be achieved for NP-complete problems unless NP is contained in coAM. (Which is about as unlikely as having NP=coNP.) If soundness is statistical but zero knowledge is computational, we have Computational Zero Knowledge proof systems, which exist for all of NP assuming one-way functions.

What if we want computational soundness and statistical zero knowledge? It had been known that one could get such systems for all of NP assuming one-way permutations. Now, with this work of Nguyen, Ong and Vadhan, we finally know that one-way functions suffice for this version as well.

Before lunch, Richard Karp talks about the theme of theoretical computer science as a lens for the sciences. This has been an angle pursued for increased theory funding at NSF, and it is a theme that will recur in all the invited talks. Karp focuses on the case of computational biology. Christos Papadimitriou chairs the session. He says that when he interviewed at MIT, Dertouzos asked him who was his role model, and Christos answered "Dick Karp," an answer that Dertouzos seemed to like. When Karp starts speaking, he says "over time things have switched; now Christos is my role model, and this is why I am wearing black today."

The most enjoyable talk of the day is given by Swastik Kopparty, on joint work with Eli Ben-Sasson and Jaykumar Radhakrishnan. They consider the question of the optimality of the Sudan and Guruswami-Sudan list-decoding algorithms for Reed-Solomon codes. Optimality, that is, in terms of how many errors (or, equivalently, how low agreement) the algorithm can tolerate. The combinatorial question is at which point the size of the list that the algorithm has to compute becomes super-polynomial, precluding any possibility of a polynomial-time algorithm. They vastly improve previous such bounds. In the 20 minutes alloted for the talk, Swastik manages, with contagious enthusiasm, to explain the problem, to fully prove a weaker version of the result, which already slightly improves previous bounds, and to give a good idea of how the general argument looks like.

Xi Chen gives the talk for his paper with Xiaotie Deng on Nash equilibria that won the best paper award. They show that, even for two players, the problem of computing a Nash equilibrium is PPAD-complete, where PPAD includes all search problems in NP where the existence of a solution is guaranteed by a certain "fixed-point argument." In the longer time alloted for the paper award winner, Xi Chen explains the intuition that makes the two-player case seem easier than the case of three or more players, he describes previous results on the complexity of the cases of three or more players, and gives some idea of the new reduction. The talk is really excellent.

After dinner, the business meeting moves along unusually rapidly.

Sanjeev Arora thankfully does without the silly statistics on how many papers were accepted by number of authors and by length of the title, and simply offers the numbers of submissions, acceptance, and attendance. There are only about 220 registered attendants. (Plus a few unregistered ones as well, ehm, ehm.) This is about half the attendance at SODA. Isn't there something wrong going on, suggests Sanjeev? If (now it's me speaking, not Sanjeev) STOC and FOCS have, as a purpose, to be the place where the theory community comes together and we learn abotu results outside our area, but then the community does not come, haven't we lost our purpose?

FOCS 2007 will be in Providence, in a hotel that is currently under renovation, and Alistair Sinclair will be the program committee chair. The bid to hold FOCS 2008 in Philadelphia wins by acclamation against no opponent, despite bidder Sanjeev Khanna pleading not to accept his bid.

Umesh suggests that we move to an online publication of the proceedings and forgo the paper version. After some discussion, we vote for a dizzying array of possibilities. "Would you like to stop publishing proceedings, distribute a CD at the conference, but not do the online publication suggested by Umesh, while continuing the online publication in the IEEE digital library" was one of the options put to vote.

So you are going to FOCS

2006-10-19T00:19:00.000-07:00

FOCS in Berkeley starts in a few days. Here is some unsolicited advice.

The weather is going to be mild and sunny, but you are not going to wear shorts and sandals. And if you plan to go see the Golden Gate bridge, you want to carry some warm clothes with you.

There is no hotel in downtown Berkeley that is large enough to host FOCS, so the conference will be at a hotel by the bay which is somewhat far from the town center. There are places to walk to from the hotel, and there is public transportation, but it is still worth renting a car, because it will make dinner plans simpler.

Before driving to San Francisco, you can check traffic information on 511.org. You can even see the traffic on the highway in real time via webcams. You can also go to San Francisco via the bart, a subway system. The public transportation system in San Francisco is called muni.

The San Francisco Bay Area is known for its food and its coffee shops; have fun trying a different place each night.

Check out sftation.com to see what's going on in the city during the weekend.

Among other events, this weekend will be the third weekend of Open Studios, an opportunity to visit the studios of local artists, which are not otherwise open to the public. And let's not forget the unique opportunity to meet Crispin Glover in person!

San Francisco does not have the museum scene of New York or of a European capital, but it has a number of interesting destinations. Unique to San Francisco is the recently opened Asian Art Museum, the largest such in the West. The De Young museum in Golden Gate park (which is nowhere close to the Golden Gate bridge) reopened last year after a long renovation. The Palace of the Legion of Honor hosts a fine art museum which is all right, but its main attraction is the fantastic view of the bay that you get from the garden. The SF MOMA is hosted in a very beautiful contemporary building.

One of the best parties in town is Popscene, feauturing Brit-pop and "indie" music, but it's on Thursdays. When it comes to San Francisco values, one of my favorite parties is Trannyshack, which is on Tuesdays. At other places, a drag show is often meant to be a man in a dress lip-synching to a Cher song. Nothing like this goes on at Trannyshack, a San Francisco institution that was the subject of a documentary. There, drag is an excuse for perfomances that can be highly conceptual, purely silly, outright offensive, or just bizarre depending on the performer. One night I was there the theme was punk rock, and there was this 6+ foot tall performer dressed like a punk girl singing a song I did not recognize, while the audience was having fun pogoing. At one point the performer tried to stage dive, but everybody just jumped out of his way (he was big), and he landed on the floor face first. This Tuesday night the theme will be vampires.

For more nightlife events, see sfstation.com or here.

The limitations of linear and semidefinite programming

2006-10-18T12:17:00.000-07:00

The fact that Linear Programming (LP) can be solved in polynomial time (and, also, efficiently in practice) and that it has such a rich geometric theory and such remarkable expressive power makes LP a powerful unifying concept in the theory of algorithms. It "explains" the existence of polynomial time algorithms for problems such as Shortest Paths and Min Cut, and if one thinks of the combinatorial algorithms for such problems as algorithms for the corresponding linear programs, one gains additional insights.

When looking for algorithms for a new combinatorial problem, a possible approach is to express the problem as a 0/1 integer program, then relax it to a linear program, by letting variables range between 0 and 1, and then hope for the best. "The best" being the lucky event that the value of the optimum of the relaxation is the same as that of the combinatorial program, or at least a close approximation. If one finds that, instead, the relaxation has optimal fractional solutions of cost very different from the combinatorial optimum, one may try to add further inequalities that are valid for 0/1 solutions and that rule out the problematic fractional solutions.

Many "P=NP" papers follow this approach, usually by presenting a polynomial-size linear programming relaxation of TSP and then "proving" that the optimum of the relaxation is the same as the combinatorial optimum. One can find recent examples here and here.

Similar results were "proved" in a notorious series of paper by Ted Swart in the mid 1980s. After counterexamples were found, he would revise the paper adding more inequalities that would rule out the counterexample.

Finally, Mihalis Yannakakis took matters into his own hands and proved that all "symmetric" relaxations of TSP of sub-exponential size have counterexamples on which the optimum of the relaxation is different from the combinatorial optimum. (All of the LPs suggested by Swart where "symmetric" according to Yannakakis's definition.)

This is actually one of the few known lower bounds that actually applies to a "model of computation" capturing a general (and otherwise promising) class of algorithms.

(I first read about this story in Christos Papadimitriou's complexity book, but I found the above references in Gerhard J Woeginger's P versus NP page.)

In the theory of approximation algorithms, we have plenty of problems that are believed to be intractable but that are not known to be NP-hard, such as approximating Vertex Cover within a factor of 1.9, or approximating Sparsest Cut within a factor of 10. LP and Semidefinite Programming (SDP) approaches are more or less the only promising tools we have to prove that such problems are tractable and, while we wait for NP-hardness result (for now, we only have "Unique-Games-hardness"), it is good to see whether certain candidate LP and SDP algorithms have any chance, or if they admit counterexamples showing large gaps between the optimum of the relaxation and the combinatorial optimum.

The problem with this approach is the nearly endless variety of relaxations that one can consider: what happens when we add triangle inequalities? and pentagonal inequalities? and so on. As in the case of Yannakakis's result, it would be great to have a result that says "all SDP relaxations of Vertex Cover of type X fail to achieve an approximation ratio smaller than 2," where "type X" is a general class of sub-exponential size SDP relaxations that include the type of inequalities that people use "in practice."

Lovasz and Schrijver describe a method, denoted LS+, that starts from an LP relaxation of a problem (actually it can start from any convex relaxation), and then turns it into tighter and tighter SDP relaxations, by adding auxiliary variables and linear and semidefinite constraints. A weaker version of the method, denoted LS, only adds auxiliary variables and linear constraints.

A nice thing about the method is that, after you apply it to your initial relaxation, thus getting a tighter relaxation, you can then apply it again to the tighter one, thus getting an even better relaxation, and so on. Starting from an LP relaxation with $n$ variables and poly($n$) constraints, $k$ applications of the method yield a relaxation solvable in $n^{O(k)}$ time, which is polynomial for all fixed $k$ and sub-exponential for $k=o(n/log n)$. Lovasz and Schrijver prove that, after $k$ applications (or "rounds") the resulting relaxation enforces al inequalities over $k$-tuples of variables that are valid for 0/1 solutions. (In particular, one gets the combinatorial optimum after $n$ rounds.) Typical approaches in the design of approximation algorithms are SDP with local inequalities (triangle inequalities etc.), and this is all captured after a few rounds of LS+.

It would be great to show that no constant (ideally, no sublinear) number of rounds of LS+ starting from the basic LP relaxation gives a $2-\epsilon$ approximation for vertex cover. Arora, ~~and others~~ Bollobas and Lovasz considered related questions in a FOCS 2002 paper that has inspired a considerable amount of later work. (See the introduction of the journal version.) Unfortunately the question remains open evern for two rounds of LS+. After one round, one gets an SDP relaxation equivalent to (number of vertices minus) the Lovasz Theta function, and Goemans and Kleinberg prove that such SDP does not achieve approximation better than 2. Beyond that, it is pretty much terra incognita. Charikar proves that a relaxation with triangle inequalities (which is incomparable with two rounds of LS+ and is weaker than three rounds) does not achieve approximation better than 2. Also, a sublinear number of rounds of LS+ does not achieve approximation better than 7/6. For LS, which, I remind you, generates linear programming relaxations rather than semidefinite programming ones, we know that no sublinear number of rounds leads to an approximation better than 2.

I will illustrate the main idea in the LS and LS+ method using the example of Vertex Cover. In the linear programming formulation, we have variables $x_i$, one for each vertex $i$, and the constraints that $x_i + x_j \geq 1$ for each edge $(i,j)$ and that $0\leq x_i \leq 1$. We would like to add constraints that are only satisfied by 0/1 solutions, and the constraint $x_i^2 = x_i$ would work beautifully except that it is not linear (nor convex). Instead, Lovasz and Schrijver add new variables $y_{i,j}$, one for each pair of vertices, with the idea that we would like to have $y_{i,j}=x_i * x_j$; then they add the requirement $y_{i,i} = x_i$ and various inequalities that make the $y_{i,j}$ be "sort of like" $x_i*x_j$. In particular, we would like to require that if $x_k \neq 0$, then $x_i = y_{i,k}/x_k$. This is again a non-linear constraint, but, at least, we can check whether, for each fixed $k$, $y_{i,k}/x_k$ is a fractional vertex cover: we just need to check the inequalities $y_{i,k} + y_{j,k} \geq x_k$ for each edge $(i,j)$

Similarly, if $x_k \neq 1$, we expect to have $x_i = (x_i-y_{i,k})/(1-x_k)$. We cannot check it directly, but we can check if
$x_i - y_{i,k} + x_j - y_{j,k} \geq 1-x_k$
hold for each edge $(i,j)$. Finally, we obviously want $y_{i,j} = y_{j,i}$. This describe the LS method. For LS+, we add the requirement that the symmetric matrix $(y_{i,j})$ be positive semidefinite. Being positive semidefinite means that there are vectors $b_1,\ldots,b_n$ such that
$y_{i,j} = < b_i , b_j>$
where $<\cdot,\cdot>$ denotes inner product. If $y_{i,j} = x_i *x_j$ then $(y_{i,j})$ is clearly positive semidefinite.

Lies, damn lies, and National Review

2006-10-14T16:53:00.000-07:00

The Lancet has recently published a study of the number of deaths in Iraq caused by the invasion. From the abstract:

Data from 1,849 households that contained 12,801 individuals in 47 clusters was gathered. 1,474 births and 629 deaths were reported during the observation period. Pre-invasion mortality rates were 5.5 per 1000 people per year (95\% CI 4.3–7.1), compared with 13.3 per 1000 people per year (10.9–16.1) in the 40 months post-invasion. We estimate that as of July, 2006, there have been 654,965 (392,979–942,636) excess Iraqi deaths as a consequence of the war, which corresponds to 2.5\% of the population in the study area. Of post-invasion deaths, 601,027 (426,369–793,663) were due to violence, the most common cause being gunfire.

Author Mark Goldblatt notes in an article on National Review that, in these calculations, one should also consider the fact that, before the invasion, Iraq was subject to sanctions that were lifted after the American occupation. By some estimates, the sanctions were causing about 150,000 deaths a year. This means that, since 2003, about 450,000 deaths might have been avoided because of the end of the sanctions.

Considering that one would have expected 450,000 fewer deaths, and one gets instead 650,000 more, the conclusion would be that the extra deaths caused by the occupation would be in excess of a million. Of course, simply adding the two numbers is problematic for a few reasons: some of the effects of the sanctions (for example, on the health care system) may be similar to the effects of the occupation, and hence would be having similar (rather than nearly disjoint) effects. Most importantly, it has been alleged that the estimates on deaths caused by the sanctions were overstated.

Anyways, what is Goldblatt approach? He subtracts one number from the other! You know how this works: I owe you \$20 dollars, now lend me another \$30 and I will give you the \$10 difference tomorrow. If I may suggest an improvement to his methodology, he should also subtract the number of deaths that occurred in Switzerland over the same period of time. I am sure he would get even more accurate estimate.

Update: see also Tim Lambert at scienceblogs.

You too could be the subject of a film festival

2006-10-08T20:11:00.000-07:00

San Francisco is the city of the many film festivals, but this month the programmers of the Castro Theater are having too much fun. This weekend, there was a first annual canine film festival.

At the end of the month, there will be the the first ever Crispin Glover film festival in the world, and, just in time for FOCS, you can catch Crispin Glover in person on October 20, 21 and 22.

And who is Crispin Glover, you may ask? Older readers may remember him from such movies as Back to the Future, where he played George McFly, the nerdy father of Michael J. Fox's character.

Alan Turing tribute

2006-10-06T17:08:00.000-07:00

The November issue of the Notices of the AMS is a tribute to our hero Alan Turing. The timing is odd because such things are typically done when there is a significant anniversary, which does not seem to be the case here. (70 years since the Turing machines paper?)

Unlike the case of the tributes to Grothendieck, not much is said about Turing's life, except in Barry Cooper's article.

Paper Dolls

2006-10-06T10:55:00.000-07:00

Being back in San Francisco for a few days, I had a chance to catch Paper Doll, a documentary profiling a group of Filipino immigrants in Israel, working mostly as caregivers for the elderly.

The Philippines are, for some reason, great exporters of caregivers. Italy has a large such immigrant community, and so do many countries in East Asia. In Taiwan, for example, the exploitation of Filipino maids and caregivers made possible by immigration laws is a cause célèbre of leftist groups. The same legal problems arise in Israel, where a work visa is immediately voided if one is fired, resulting in illegal status and the possibility of deportation. Indeed, the same is true for software engineering on H1B visas in the US, but the difference in class, education, and type of employment (not to mention the possibility of permanent residency) does not quite create the same situation.

The main angle of the movie, however, is that the Filipinos profiled in the documentary are all transgender, and they have formed a group, called Paper Dolls, that performs drag shows at community events.

They are met with acceptance and prejudice in a way that is not always predictable. Their clients, including religious ones, are accepting (even though those working in ultra-orthodox neighborhoods are uncomfortable there). The relation between one of them and the elderly man that she cares for, in particular, is very touching. Their attempt to play their act at a big-name gay club in Tel-Aviv, however, ends in a disaster of cultural insensivity.

Eventually, the group disbands, partly because of the vagaries of the Israeli immigration laws, some of them going back to the Philippines, and some of them moving to London.

The movie does not quite have a point, and its own sensibility oscillates between exploitation and sympathy. If its point was to express this conflict, then it succeeds quite well.

The primes are random except when they are not

2006-10-03T17:34:00.000-07:00

The next issue of the Bulletin of the AMS will have an article by Jaikumar Radhakrishnan and Madhu Sudan on Dinur's proof of the PCP theorem. The article introduces the notion of PCP and its applications, as well as Irit's proof.

There will also be an article on the work of Goldston-Pintz-Yildirim on small gaps between primes. Their main result is that for every eps>0 there are infinitely many pairs of consecutive primes whose difference is less than eps times the average distance between consecutive primes of that magnitude. That is, we can find infinitely many pairs of primes p,p', p' > p such that p'-p < eps log p. This is a step in the direction of proving that there are infinitely many pairs p,p' such that p'-p =2, the twin primes conjecture.

This result is fascinating in various ways. One is the way it was discovered: Goldston and Yildirim had been working on gaps between primes since 1999, and announced the above result in 2003. But then a gap was found in the proof, which seemed to doom the whole approach. They kept working on it for two more years, however, until they made their breakthrough. You can read about it in Daniel Goldston's amusing artcile my 30 minutes of fame.

Technically, their results improve on previous "sieve" techniques whose spirit is to show that the "primes are 'pseudo-random' except in the obvious ways in which they aren't," as Green and Tao more or less put it, a statement that is made precise in the Hardy-Littlewood conjecture. The idea is to start by thinking of the following probabilistic "model" for prime numbers: a number N is "prime" with probability 1/ln N, and to observe that certain properties of the primes (for example, the prime number theorem) hold in this model. Faced with a conjecture, one can check if it is true in the model, and then see if it is true for all sets of integers that have some "pseudorandomness" property and finally verify that the primes have such pseudorandomness property, usually via Fourier analysis. (This would be the "circle method" in number theory.)

The model, of course, has some major shortcomings. For example it predicts infinitely many even numbers to be primes, and infinitely many pairs of primes that differ only by one. We may correct the model by, more realistically, saying that if N>2 is even, then it is never prime, and if it is odd then it is prime with probability 2/ln N. This is already better, and it predicts some true asymptotic properties of the primes, but it still has problems. For example, it predicts inifinitely many triples of primes p,p+2,p+4, while 3,5,7 is the only such triple. (Why?) An even better model is that N>6 is prime with probability 3/ln N if N mod 6 is either 1 or 5, and N is never prime otherwise.

We see we can define a hierarchy of more and more accurate models: in general, for a fixed W, we can look at the distribution that picks a 1/ln N fraction of numbers from 1 to N and that only picks numbers N such that N and W share no common factor. As we pick W to be a product of more and more of the first few primes, we get a more and more accurate model. (This would be the issue of "major arcs" versus "minor arcs" in the circle method.)

Now look at a conjecture about primes, for example the twin primes conjecture, and see what these models predict. They all predict const*N/(ln N)² twin primes between 1 and N, with the constant depending on W; for larger W, the constant tends to a limit c_twin. It is conjectured that there are in fact about c_twinN/(ln N)² twin primes between 1 and N.

More or less, the Hardy-Littlewood conjecture implies that the prediction given by this model is always right for questions that involve "linear equations over primes."

Apparently (I haven't read the papers) Goldston-Pintz-Yildirim approach the pseudorandomness of primes by looking at "higher moments." Green and Tao have been working on a different program based on studying the "Gowers uniformity" of the primes. (Technically, they study the Gowers uniformity of the Mobius function rather than of the characteristic function of the primes, but it's close enough in spirit.)

In the paper Quadratic Uniformity of the Mobius Function they show that the primes have small dimension-3 Gowers uniformity, and, together with their earlier result on Gowers uniformity and polynomials, this is used in a new paper to prove that the predictions of the Hardy-Littlewood conjecture hold for every question about linear equations over primes of "bounded complexity." For example, if you write certain pairs of linear equations over four prime unknowns, then the fraction of solutions will be as predicted by the limit of the random model. This includes the case of length-4 arithmetic progressions over primes, where you look at solutions p1,p2,p3,p4 to the equations p4-p3=p3-p2 and p3-p2=p2-p1.

These results and conjectures are part of an even bigger set of results whose spirit is that "multiplicative structure is pseudorandom with respect to addition," that can be seen in various results that have applications to combinatorial constructions. This comes up most directly in sum-product results in finite fields and over the integers, used to construct extractors, in Weil's result on character sums, which is used to construct eps-biased generators, in certain expander constructions related to Ramanujan graphs, and so on.

It is hard to believe that, until recently, analytic number theory was considered an unfashionable area, what with its quantitative results and its lack of connections to algebraic geometry. For example, I understand that the Berkeley math department, which is quite large, has no analytic number theorist.

Dancers of size

2006-09-30T11:40:00.000-07:00

This week's Bay Guardian has the quintessential San Francisco story. It perfectly captures many of the things I love and hate about this ciry: the political ideals, the attitude towards sex, and the litigiousness.

Crypto Misdemeanor

2006-09-28T21:33:00.000-07:00

I fear that something like this will happen to me before the end of the term at IPAM.

xkcd comic by Randall Munroe

More on Chavez and Thailand

2006-09-23T03:15:00.000-07:00

According to an opinion poll from the Bangkok Post, more than 80% of the population supports the coup in Thailand. Meanwhile, the military junta is sending orders to the troops on the ground: Smile.

In his speech, Chavez expressed regret that he was never able to meet Chomsky before his death. Chomsky, of course, is alive and well, and his book that Chavez brandished at the UN shot up in the best-sellers list.

What's new in the world

2006-09-20T16:45:00.000-07:00

Venezuela President Hugo Chavez spoke at the UN today. He first advertised a book of Chomsky's. Then "The devil was here yesterday," he said referring to President Bush, who had spoken earlier on his vision for the Middle East "it still smells of sulfur." He then made the sign of the cross. There is a video here.

Meanwhile, Thaksin Shinawatra, the Berlusconi of Thailand, was ousted in a surprisingly peaceful military coup. Here is an excellent blog coverage of the events in Bangkok. The highly respected King has endorsed the coup.