Scott complains that “art snobs” want to have it both ways: to assert that the beauty of art is an aesthetic experience, a gut feeling, and, at the same time, that certain tastes are more valid than others. What is this, do they think that their guts are better than ours? That’s certainly not how we do things in complexity theory. Or is it?

When we talk about the “beauty” of a theorem or of a proof, we rarely refer to the literal statement of the theorem, much less to the fact that the proof is correct.

The beauty of a theorem is typically found in the way it fits into the bigger fabric of a theory, how it is explained by, and how it explains, other results. The statement of a theorem can feel comforting, surprising, or even unsettling, or worrisome. In a proof, we appreciate economy, a way of getting to the point in what feels like the “right” way, an unexpected use of techniques, a quick turn and a surprising ending.

If we think of, say, Reingold’s proof that L=SL, we (meaning, I and some other people) appreciate the statement for being a major milestone in the program of derandomization, and we appreciate the proof for the simplicity of its structure and for the cleverness of the way its technical tools are used.

Although, in the end, it is a matter of taste to see that the statement is important and that the proof is beautiful, I don’t think that the taste of the expert in the area is equally valid as the taste of the non-expert who says, oh this is an algorithm for connectivity that runs in n^{100} time and it *does not even work on directed graphs?*

(I am so delighted to have a discussion where one can take the notion of mathematical beauty for granted, and then use it to argue about artistic beauty.)

This wouldn’t be a non-technical *In Theory* post without an unnecessary personal story, so let me conclude with my experience with modern dance.

At one point, a few years ago, I was taken to see several modern dance performances. My first experience was not unlike Woody Allen’s in *Small Time Crooks*. While the sound system was playing annoying and discordant sounds, people on stage were moving around in what looked like a random way. I was convinced that the nearly sold-out audience at Zellerbach (it’s a big theater) was there simply to feel good about themeselves and nobody could *really like* that stuff. There was something that puzzled me, however: at one point, everybody laughed, presumably because something (intentionally) funny happened in the choreography. Everybody got it (except me, of course), so perhaps there was something going on in those random movements, after all. After a few more shows, the experience started to feel less agonizing, and I started to notice that I would like some segments better than others, and that this would agree with what others thought. Finally, one night, I laughed out when a dancer did something really funny on stage, and so did the rest of the audience. Aha, the brainwashing had succeeded! I left the theater feeling good about myself… No, wait, this is so not the point I wanted to make…

Thanks for the interesting perspective and for your personal brainwashing tale!

For me the difference is this: with Reingold’s theorem, even if I didn’t yet understand it at a deep aesthetic level, I’d know (because of what it does at a syntactic level) that there must be

somethingthere to understand. Whereas with the modern dance performance, all I’d have to go on are those laughing people. And if that’s sufficient evidence that there must be something to it — well, what if the crowd also thinks (this is Berkeley we’re talking about) that there’s something to astral projection and chi energy fields? Indeed,youlaughing might be the only thing that convinced me to stay to the end.I agree that the notion of “correctness” in math and the notion of “agreement with experiments” in physics have no analog in the arts.

But, leaving physics aside for a moment, I think that, in math, the process of restricting ourselves to correct proofs is only the very beginning. If you are not an expert and you are confronted with the L=SL statement, you can see that this is something that has been proved and that you would not know how to prove. But suppose somebody shows you a random diophantin equation and tells you that he knows a proof that the equation has a solution in the integers. It might be very hard for you to find a proof of such a statement by yourself, but I don’t see why you would be interested in it.

I realize that this is still better than

nothing, while in the arts, in principle, a performance could be completely based on nothing. (But so is a TV show that I liked a lot…)So there is definitely more space at the bottom for the arts but I think that, at the top, the way we think of certain theorems as beautiful is not unlike the way we think of some art as beautiful.

I also never had a clear idea of what is considered ‘art’. I was speaking one day to an architect, and I asked him…presuming that in their profession, being engineers and artists, they might have some concrete test for art. He replied that there are many views of what can be called art, but his favorite was (and now I paraphrase) that a piece of art is a way for the artist to communicate some discovery he has made about the world or his existence.

So to appreciate or judge art, maybe the viewer must figure out what sort of discovery he thinks the artist made.

This reminds me of what happened right after the announcement of L = SL. I breathlessly gave the news to a colleague that is more on the security side of things, who then proceeded to ask “well, what’s that?” I explained, to receive a polite “oh, that’s nice.” The fact that it had been a longstanding open problem, by itself, didn’t seem to make that much difference.

Part of what makes L = SL important or beautiful, at least for me, is the way in which the question and Reingold’s proof tie into other questions in complexity theory, and the way in which they shed light on how we reason about computation. Will L = SL lead to a proof of L = RL? I don’t know, but I can appreciate how tweaking the definition of RL to obtain SL opens the way to a new theorem. This is even before we get into the issue of beauty in the proof itself, its techniques, etc.

It’s the same reason I find different tweaks to, say, the definition of chosen-ciphertext security for a cryptosystem interesting. Where others may see only a sequence of different, equally arcane definitions, I see an ongoing conversation about how best to reason about this crazy, vulgar, ill-formed notion of “security.”

Getting back to art and dance, my limited understanding is that these fields (sometimes) have ongoing conversations of their own. What seems incomprehensible at first becomes more intelligible given a context. I say this as someone who was also taken to a modern dance performance. Thankfully with the benefit of a guide who was willing to put up with my stupid questions. :)

I think the best example here for Scott is SL = L, but the aspect that no one has been discussing: I would not have been nearly as satisfied (and probably would have thought much less of the paper) if the solution had been based on Vladimir Trifonov’s approach (the guy who got O(log n log log n) at the same time).

His paper is very nice, and it still would have been a breakthrough, but not with the same zest…

I agree that the notion of “correctness” in math does not appear in art. However, one should also keep in mind that art is a process-object-“thing”, which is never based on “nothing” (here a definition of “nothing” would be required). The real success of an artwork is mostly based on how strong is the semantic link created between the object itself and the idea that it tries to communicate. Being out of any formal system one cannot really speak about “how correct the artwork is”, but one can speak about how strong is the semantic link. The stronger is the semantic link, the more “correct” is the artwork. I would be tempted to say that beauty is on the strength of the semantic link, that is in “how much the artwork communicate and with what precision, once fixed the social/cultural/(and so on) context – a sort of formal system for the artwork itself).

Has anybody tried this Hoodia Diet Pills. I heard of the Hoodia Weightloss pills. Here is the Pure Hoodia Diet Pills or the Phentramine diet pill