Numb3rs Review: "Sabotage"

A nice thrilling episode, with very little math (but see below). As always, major spoiler alert.

Plot summary: Series of trains are derailed. At each site, a paper containing the same set of numbers is left behind. Everyone thinks it's a code, but it actually isn't (at least not in the traditional sense). Some good old sleuthing yields the answer.

It was funny when the NTSB official asks Charlie if he knows any cryptography. Although technically isn't cryptanalysis what the code breakers do ? Larry the loony physicist had some hilarious quotes:

• "Our evening was primal, in the carnal sense, not the mathematical."
• "The math department, the least libidinous place on campus"

The last fact is sadly not too far from the truth, but wait ! Mathematicans are cool (via Mathpuzzle)

The only real math nuggets came at the end, when Charlie was trying to explain to the female FBI agent that math appears in nature. His example: The Fibonacci series ! Bzzttt...

As it turns out, Rudbeckia Hirta just today posted a note about the exaggerated claims concerning the Fibonacci series; that the Greeks referred to the "golden ratio" (no), that the pyramids and the Parthenon somehow magically encode this ratio (only if you round off heavily), and even how the ratio is supposed to be aesthetically pleasing (no evidence). Keith Devlin has more on this.

Oh well: if Dan Brown can do it...

• Next episode review
• Previous episode review

Tags: numb3rs, reviews

p.s I understand that we need some kind of romantic interest to give the series some spice (although CSI and Law and Order manage perfectly well without it), but why on earth are they setting up an advisor-student relationship ? Allegedly at some distant point in the past this used to be fairly common in the humanities, but nowadays ? My only question is: how long before this becomes a "Big Issue" in the academic blogosphere ?

Meta: recent comments

I added a new feature so you can see the recent comments posted on the site (this is handy if you posted a note and are looking to see if there was a response). It's on the left, below the "Previous Posts" section.

Comments were broken for a while because I forgot to update the hack that allows me comments in the first place. They should be working again.

SODA Outtakes: Lloyd's algorithm and analysing heuristics

Uri Feige's invited talk at SODA 05 was on 'Rigorous Analysis of Heuristics for NP-hard Problems'. His main argument (at least in the initial portion of his talk) was that it's a good idea to analyze known heuristics for problems, because they work well in practice, and a rigorous analysis will shed light on why.

[Aside: in the theoryCS community, a "heuristic" usually refers to a procedure that has no provable performance guarantees; this could mean either no clear running time analysis, or no clear quality of optimization guarantee. The term "algorithm" is usually reserved for a procedure that has well-defined steps and ends in a well-defined state after a definite (finite) number of steps. One will occasionally find the term 'algorithm' used to refer to a heuristic in non-theory areas; beware !]

Doing such analysis, although maybe not as "sexy" as coming up with a new algorithm, is important also for "sociological" reasons. Although it might technically be correct to argue that a particular heuristic is not reliable and thus should not be used, the resolute theoretician is often faced with a mountain of empirical evidence in support of said heuristic, compared with the possibly complex and hard-to-understand algorithm that she proposes.

Some of the best known heuristics show up in clustering, especially since this is a problem that transcends many different application domains, including areas that are not as familiar with theoretical algorithmic methods. One of the best known methods for clustering with k centers is Lloyd's algorithm (or the k-means algorithm), which works essentially as a discrete variant of expectation-maximization. The algorithm itself is very simple:

1. Choose k "centers"
2. Assign each point to its nearest center.
3. Compute the k centroids of points assigned to a given center. These are the new k "centers".
4. Go back to step 2.

It is known that Lloyd's algorithm will hit a local minimum fairly quickly (though not a global one: k-means is NP-hard). However, there is no analysis of how quickly this happens. In a SODA 2005 paper, Har-Peled and Sadri examine the complexity of k-means. They show that:

1. In 1D, and in d-D (on the grid), the number of iterations of the k-means algorithm is polynomial in the number of points, the dimension, and the "spread" (the ratio of max distance to min-distance).
   
2. Even in 1D, there are example point sets on which the k-means algorithm takes a linear number of iterations to converge.

What they also show is that slight modifications to the k-means heuristic result in algorithms that converge in time independent of the dimension (and with much better upper bounds). The simpler of their two schemes can be described as follows: in Step 2 of the original approach, merely move one "misclassified" point to its true cluster, rather than all.

They go on to present empirical evidence in support of their claim that these algorithms generate similar quality answers (in similar time) to k-means. This part is still a work in progress: there are very fast implementations of k-means that they don't compare against, (but the data structures might be used to speed up their approach as well).

It is not clear to me that their paper answers to any degree the question of why Lloyd's algorithm works as well as it appears to. However, the fact that they can prove bounds for their alternate algorithms suggests that maybe this is a line of attack to take when analyzing Lloyd's method. These alternates are also quite simple, and so could conceivably be used as k-means replacements if one wished guaranteed running time bounds.

One final point: the authors have their code available online. Would that more would do the same !

CiteULike

Yaroslav Bulatov, who runs one of the new machine learning blogs, points us to CiteULike, a very intriguing site. Some of you may have used web-based bookmark sites like Furl or del.icio.us, and may have even used the "social bookmarking" aspect of these sites.

CiteULike is a similar site, for archiving papers. Here's how it works. If you find a paper you are interested in, you click on a bookmark link, and the paper is added to a web-based collection under your name. However, what makes this unique is that if the paper link is on a "well known" site like the ACM DL, Citeseer, arxiv, or many other places, bibliographic information is automatically added to the entry (this is because the server parses pages etc and extracts the necessary bibliographic information)

Subsequently, when you want to extract bib entries for all these papers, one click gets you a .bib file for all the papers you want. This is very handy (for example) when you are doing a literature search and reading/downloading papers by the dozen.

You can also associate tags with the entries if you choose to. This gets into the "social bookmarking" aspect of CiteULike: the idea being that if you tag a bunch of papers as being related to "artgallery", and so does someone else, you will learn what the other person has found and vice versa. Personally, I am either too oldfashioned or too clueless to have made effective use of this feature, but the archiving/.bib features above are enough for me try it out.

Like any respectable web-based service, there are RSS feeds for any view of the collection (by tag, by person, by personal tag), and there are also watch lists, so if you want to keep track of when a new page (tag or person) adds a new paper, you can do so.

Here's my paper feed. It will be an interesting experiment.

If you think your committee is rough on you...

From Jim Holt's New Yorker article on Einstein and Gödel:

Einstein’s conclusions were the product of pure thought, proceeding from the most austere assumptions about nature. In the century since he derived them, they have been precisely confirmed by experiment after experiment. Yet his June, 1905, paper on relativity was rejected when he submitted it as a dissertation. (He then submitted his April paper, on the size of atoms, which he thought would be less likely to startle the examiners; they accepted it only after he added one sentence to meet the length threshold.)

The article dwells at length on Gödel's interpretation of time (something I had mentioned a while ago). Read the whole thing: it's fascinating.

(HT: Libertarianoid)

Tags: Gödel, Einstein, relativity, time

A great new resource for molecular modelling

From WorldChanging:

ZINC -- which, in the free software tradition of recursive acronyms, stands for ZINC Is Not Commercial -- is a free database of compounds for "virtual screening." That is, ZINC provides 3D models of chemical compounds in a standard "docking" format used in chemistry and biochemistry software, allowing researchers to assemble and test new chemical compositions on their computers.

This is really great. When I was doing my Ph.D, I mucked around with molecular structures for docking and matching purposes, and I had accces only to structures that our collaborators at Pfizer provided us. Having such a large database to play with will really help geometry folks who do molecular modelling, not to mention all the medical researchers who probably already use this.

Things we take for granted..

Richard Hofstadter's classic book Anti-intellectualism in American Life is a fascinating sweep through American history that provides a good answer for those who wail 'How could someone as (apparently) stupid as Bush get elected ?'. Another book, The Development of Academic Freedom in the United States with Walter P. Metzger, should be at the top of my list of reading, based solely on this review by Scott McLemee. An excerpt from the review (emphasis mine):

Condensing 500 pages into five paragraphs is a fool's errand, but here goes anyway.

The belief that only the community of scholars has the final authority to determine what counts as valid research or permissible speech has deep roots in the history of the university, going all the way back to its origins in medieval Europe. But it was extremely slow to develop in colonial and antebellum America, which had few institutions of higher learning that were anything but outgrowths of religious denominations.

How we take certain things for granted...

Numb3rs Review: "Prime Suspect"

This was the most mathematically oriented episode of all: can't get much better than the Riemann Hypothesis ! Scott Aaronson has a review as well: go and read that first !

I agree with much of what Scott says. I think the problem is a little different though: some of the random phrases attributed to mathematicians (which mathematicians refers to an open problem as a "math problem") actually make sense if a non-mathematician uses them, and when Don (the FBI agent) uses them, it doesn't sound incongruous at all. It's just that the writers need to switch gears a little when writing dialogue for the mathematical characters.

They've done a good job getting a sense of the mathematics; just less of a sense of the mathematician.

Plot Summary: Mathematician claims to have proof of Riemann Hypothesis. Hackers kidnap daughter, demanding proof (and algorithm), which they will then use to crack cryptography.

Major beef: there is no direct link between a solution to the Riemann Hypothesis and factoring. It is undoubtedly true that a solution will shed a lot of light on the structure of primes, but it's not the kind of immediate corollary that is commonly implied in the popular press (take this, for example).

But credit goes where credit is due: I was wondering how they would make the conceptual jump from a theorem to an actual algorithm (assuming said connection). At least they tried to make it credible, with Charlie pointing out that an algorithm could take years to develop.

A point that I didn't really consider, but both Scott and my wife noticed, was that by using the Riemann Hypothesis, the plot line introduced the idea of a problem that has remained unsolved for 150 years, and that it's good for people to realize that "math problems" can take a while to solve. In fact, this point is reinforced when Don expects Charlie to solve it in a few hours :).

Trivia note: the mathematician father was played by Neil Patrick Harris, the "original" child prodigy from Doogie Howser, M.D.

• Next episode review
• Previous episode review
  

Tags: numb3rs, review

Erik Demaine and Origami

The NYT has a fabulous article on Erik Demaine and origami. It is worth noting that

• The article has no quotes that make him look like an absent-minded professor.
  
• It does a beautiful job of capturing both the art and the science of origami.
• It has no real clangers in terms of the mathematical descriptions.

SoCG 2005 Results

Are out: 41/140 papers in (no I didn't submit anything).

The entire list is here.

"Laws of Chance"

One would think I would let this pass without comment, but oh well...

A recent /. post links to an article on RedNova News about a "Random Event Generator" that purports to predict world events:

One of these new technologies was a humble-looking black box known was a Random Event Generator (REG). This used computer technology to generate two numbers - a one and a zero - in a totally random sequence, rather like an electronic coin-flipper.

Now it's all very well to generate randomness from a computer, and in fact there have been suggestions that certain kinds of electrical fluctuations on a chip can be recorded and used for randomness generation. But to claim that this is "totally random" by virtue of using the magical "computer technology" is a bit of a stretch.

But wait, it gets worse:

The pattern of ones and noughts - 'heads' and 'tails' as it were - could then be printed out as a graph. The laws of chance dictate that the generators should churn out equal numbers of ones and zeros - which would be represented by a nearly flat line on the graph. Any deviation from this equal number shows up as a gently rising curve.

I presume they mean that they plot |H-T| against n. But as any book on probability will tell you, you do expect to see random fluctuations (this is after all a binomial process), and the standard deviation is around sqrt(N), so bumps are to be expected: a flat line is what would be suspicious.

During the late 1970s, Prof Jahn decided to investigate whether the power of human thought alone could interfere in some way with the machine's usual readings. He hauled strangers off the street and asked them to concentrate their minds on his number generator. In effect, he was asking them to try to make it flip more heads than tails.

It was a preposterous idea at the time. The results, however, were stunning and have never been satisfactorily explained.

Well it sounds like the results haven't been stated either. What exactly were these "stunning" results ? Ah, here we go:

Again and again, entirely ordinary people proved that their minds could influence the machine and produce significant fluctuations on the graph, 'forcing it' to produce unequal numbers of 'heads' or 'tails'.

According to all of the known laws of science, this should not have happened - but it did. And it kept on happening.

"All the known laws of science" can't explain an unequal number of heads and tails. In other words, if I just managed to get a streak of 10 heads with a coin, I'm psychic ?

Aieee......

Theory folks in the press

The NYT has an article about spamblocking in which the 1992 work of Dwork and Naor on junk email is cited:

In a paper titled "Pricing Via Processing, or Combating Junk Mail ," two computer scientists, Cynthia Dwork and Moni Naor, came up with a way to force a sender to pay every time a message was sent - payment not in money, but in time, by applying the computer's resources to a computational puzzle, devised on the fly for that particular message.

[...snip...]

Ms. Dwork and her colleagues have named this the Penny Black Project.

This is remarkably prescient: in 1992 I was grateful to have access to email, let alone worry about junk mail. On an irrelevant note, I am impressed that the NYT has started providing real links in their articles.

Tags: spam, cryptography

SODA Outtakes: Approximation algorithms for metric embeddings.

One of the most exciting areas of algorithms in the past ten years has been the study of metric embeddings. Given two metric spaces, can we "embed" one in the other (which basically means construct an 1-1 map from points in the first to points in the second) so that distances are roughly preserved ? The seminal paper of Linial, London and Rabinovich demonstrated how to use a low-distortion embedding of a metric space into l₁, to determine a good approximation algorithm for the sparsest cut problem (the distortion of the embedding is the approximation ratio achieved).

This set off a flurry of research into questions of the form "What is the best distortion for embedding spaces of type A into spaces of type B". There is no way I can survey all the results in this area; a new CRC book chapter by Indyk and Matoušek should be able to cover most of the terrain, and the excellent book by Deza and Laurent has much of the technical background. Everything started (in a sense) from the result by Bourgain that any metric space can be embedded into l₁ with distortion O(log n) (albeit in log² n dimensions).

Other questions that were studied along the way:

• what is the minimum distortion that one must face when embedding A into B (metrics derived from expanders proved to be useful gadgets in this regard)
• Can one reduce the dimensionality of a space without distorting distances too much ? This question has numerous implications for all kinds of problems in clustering, data mining, database search, you name it...
• Are there general subclasses of metrics that have low-distortion embeddings ? A fundamental open question here involves metrics on planar graphs. It is still open as to whether they can be embedded in l1 with constant distortion (again, this has implications for sparsest cut in planar graphs)
• Metric "Ramsey theory": if I can't embed the entire metric space, can I embed a large fraction of the points/edges with smaller distortion ? Yair Bartal just gave a nice talk at AT&T on partial embeddings (the "edge" variant).
  

A set of questions that is now getting more attention is the "natural " approximation angle. Although we know that any metric can be embedded in an l_p space with distortion log n, what about a particular metric given to us ? Might one not be able to do better ? And can we come up with an algorithm to determine the BEST distortion for this particular metric ?

It was shown early on that one can find the optimal distortion into l₂ (upto additive error) in polynomial time using semi-definite programming. For l₁, the corresponding question is NP-hard. What I have been seeing is a slew of interesting recent papers that explore hardness results and approximation algorithms for embedding problems:

• Kenyon/Rabani/Sinclair (STOC 2004): They consider bijections between two n-point metric spaces, and present a constant factor approximation in the case when the metrics are derived from a line (as long as OPT is small).
  
• Papadimitriou/Safra (SODA 2005): They show that the minimum distortion bijection between two 3D point sets is hard to approximate to within a factor of 3.
  
• Badoiu, Dhamdhere, Gupta, Rabinovich, Raecke, Ravi, and Sidiropoulos (SODA 2005): A collection of results on embedding metrics in 1D and 2D. One main result is an O(sqrt{n})-approximation for embedding a metric on the line.
  
• Badoiu, Chuzhoy, Indyk, Sidiropoulos (STOC 2005): I don't have a copy of the paper, but the title is indicative enough: "Low-Distortion Embeddings of General Metrics Into the Line"

This is not to say that these problems have not been studied earlier. As far back as 1993 for example, Farach-Colton, Kannan and Warnow had looked at embedding a metric into an ultrametric. However, the current focus on such problems is an interesting new direction in the theory of metric embeddings.

---

p.s usual disclaimers apply: this is a blog post, not a survey, and hence is opinionated and far from comprehensive. Pointers to relevant add ons are welcome.

Turing Train Terminal

When I was an undergrad, we were once given an assignment to write out a universal turing machine as a state diagram. I have heard of others being asked to program one (using gturing?).

This is by far a more enjoyable variant.

---

Via BoingBoing.

Numb3rs review: "Structural Corruption"

Bill Gasarch has a second review of the P vs NP episode over at Lance's place. He speculates as to what the characters might have meant by saying that P vs NP is "unsolvable". My favorite:

Charlie was using proofs that naturalize, which won't work because of the results of Razborov and Rudich (Judd Hirsch: So use unnatural techniques)

Last night's episode dealt with calculations involving the structural integrity of a building. Not much actual math shown in this episode, and there were some curious points:

• Charlie is a "professor of applied mathematics", and yet in the first episode crazy string theorist wants his help with some calculations. I guess string theory could be viewed as applied math in some circles...
• When trying to figure out why the dead student had come to him for help with calculations (is he a math prof or a human calculator?), Charlie says "We can only infer that it had something to do with math". Uh, yeah......
• Charlie, "professor of applied math" and string theorist par excellence, can also mock up a structural integrity demo, with GUI, 3D graphics and all, in one night. Sheesh; give him a job at Google, people...

There was one sequence that sounded like a reference to Benford's Law. Charlie finds out worker names and union IDs have been manufactured, by detecting that the numbers on the IDs follow suspicious patterns. This is actually plausible, in that Benford's law has been used to detect fraud and fake accounting.

• Next episode review
• Previous episode review

Tags: numb3rs, reviews

Football and Dynamic Programming.

What's not to like !

On Ph.D Theses

When I was in grad school, it was the conventional "wisdom" that the people who read your Ph.D thesis consist of

• your advisor
• your committee
• your friends (to see if they've been acknowledged)
• your parents (who don't necessarily read it so much as keep it as a trophy/proof that you can now get a "real job".

But the truth is that Ph.D theses can serve a valuable purpose. Over the years, I have come to appreciate a well written thesis in an area that I am new to. Not necessarily because of the results; those I can often dig up from journal papers. What I found most useful is the introduction, because in a well written thesis, the introduction lays out the terrain of the problem: what is known, and what is not. What is folklore and what results follow trivially. What papers are key to understanding the evolution of the area, and what their contributions are. Basically a lot of what a good survey has to offer, but more expansive, more leisurely, and often more useful.

So if there are any graduate students reading this, my recommendation to them is: take the time to expound on your area in an introduction. You are (or should be) an expert on this topic by now, and your voice is authoritative enough, even if you may not feel that way. The reward, of having someone read your work and appreciate it, is something that can be surprisingly elusive.

Using the GPU

GPU (Graphics card) programming is one of my pet projects, and it has been interesting to see the gradual harnessing of the GPU as a fast streaming coprocessor. A new direction is an even tighter coupling with a computer's underlying GUI and window management system.

• OS X: "Quartz Extreme uses a supported graphics card built into your Mac to relieve the main PowerPC chip of on screen calculations. This dramatically improves system performance, making Panther much more responsive."

• Longhorn: "Longhorn will feature a graphics subset called WGF (Windows Graphic Foundation). Its goal is to unify 2D and 3D graphics operation in one and will bring 2D Windows drawing and 3D operations together. Nowadays, 3D is done using a Direct X subset with the current version 9.0c. Longhorn will also use 3D menus and 3D interfaces and will require at least Shader 2.0 compliant cards, so it will make the graphics card an important part of your PC."

• And late to the party, but getting there, Unix/X (via Thane Plambeck): " David Reveman, who became a Novell employee a couple of weeks ago, has been writing a new X server on OpenGL/Glitz called Xgl. Because Xgl is built on GL primitives it naturally gets the benefit of hardware acceleration. For example, window contents get rendered directly into textures (actually they get copied once in video memory for now), and so you get the benefit of the 3d hardware doing the compositing when you move semi-opaque windows or regions around."

Graphics cards will get even cheaper, since everyone will need one. Intel will probably put even more effort into the little joke they call their onboard graphics accelerator. Interesting times....

Heal thyself ?

Adam Buchsbaum observes that although Google Maps is the coolest thing since, I don't know, Google Scholar, there is one thing it doesn't do: if you type an address in the regular Google toolbar, it asks you if you want to plot a map using Mapquest or Yahoo !

C'mon guys, you can do better than that.

p.s take the tour. Try searching for 'free wifi 19130': excellent !!

"To chop a tea kettle"

A while back, Lance and Ernie and I were discussing the relative lack of questions at theory talks (in conferences specially). Having just returned from SODA, I can confirm that questions were few and far between at talks (although the odd talk here and there generated fairly animated discussions).

Scott McLemee at Inside Higher Ed has an interesting column on modern academic interactions, and how they relate to the blogosphere. The article is worth reading in its entirety, (as is the Crooked Timber note that pointed me there), but I couldn't resist excerpting the following, on discussions at conferences:

At conferences, scholars would stand up and read their papers, one by one. Then the audience would "ask questions," as the exercise is formally called. What that often meant, in practice, was people standing up to deliver short lectures on the papers they would have liked to have heard, instead -- and presumably would have delivered, had they been invited.

Hypothetically, if everyone on a panel read one another's papers beforehand, they might be able to get some lively cross-talk going. This does happen in some of the social sciences, but it seems never to occur among humanities scholars. The whole process seems curiously formal, and utterly divorced from any intent to communicate. A routine exercise, or rather perhaps an exercise in routinism. A process streamlined into grim efficiency, yielding one more line on the scholar's vita.

[...snip...]

The inner dynamic of these gatherings is peculiar, but not especially difficult to understand. They are extremely well-regulated versions of what Erving Goffman called "face work" -- an "interaction ritual" through which people lay claim to a given social identity. Thanks to the steady and perhaps irreversible drive to "professionalization," the obligation to perform that ritual now comes very early in a scholar's career.

And so the implicit content of many a conference paper is not, as one might think, "Here is my research." Rather, it is: "Here am I, qualified and capable, performing this role, which all of us here share, and none of us want to question too closely. So let's get it over with, then go out for a drink afterwards.

And the title of my post ? Read the whole article...

Damn !

Unlike some, I prefer to watch the game

Numb3rs Review: "Vector"

This episode had very little math, except a reference to a standard model of disease spread called an SIR model.

I have to say that the writers spent a lot more time getting the math details right than getting the biology right. Why on earth would you compare geometric structures of DNA, when you could just look at the sequence ? My wife the biologist had two comments on this, her first episode.

• "This is not a TV show, it's a horror movie"
• "I've been beaten senseless"

(as an aside, she refused to watch Jurassic Park when it first came out). She also assures me that the pictures of the DNA model are wrong (the alleged differences would be on the inside of the helix, not the outside). They did mumble something about RNA, but RNA wouldn't look like the pictures they had on screen.

There was an amusing incident with the eccentric string theorist where he forgot which way he was headed. I could be wrong, but I think this refers to an anecdote involving Herman Weyl at Princeton.

There was more Numb3rs PR in the math press. Keith Devlin (the Math Guy) had an interesting article on Numb3rs at MAA Online. He does an occasional segment on Weekend Edition with Scott Simon. His interviews make for interesting listening (a recent one was on the continuum hypothesis).

• Next episode review.
• Previous episode review.

Tags: numb3rs, review

And the wrath of God thunders down upon the unbelievers

Ernst Mayr, "leading evolutionary biologist of the 20th century", died today. From the NYT obit:

He was known as an architect of the evolutionary or modern synthesis, an intellectual watershed when modern evolutionary biology was born. The synthesis, which has been described by Dr. Stephen Jay Gould of Harvard as "one of the half-dozen major scientific achievements in our century," revived Darwin's theories of evolution and reconciled them with new findings in laboratory genetics and in field work on animal populations and diversity.

Polynomial hierarchy collapse

Another thing that puzzled me about the Unknotting result was the corollary:

If Unknotting is NP-complete, then PH collapses to the second level.

As it turns out, this is a trivial corollary of an older result by Boppana, Håstad and Zachos that if co-NP has short interactive proofs, then PH collapses. Specifically if Unknotting is NP-complete, then Knotting is co-NP-complete and since it is in AM = IP(2), this implies that co-NP is in IP(2), and everything comes crashing down.

It would be nice if there was some way to augment the Complexity Zoo to make such results easier to find.

Unknotting (proof translation)

Jeff Erickson kindly provides a translation in the comments to my previous post. I reproduce the full comment here, lightly edited for links and with minor corrections/additions marked in italics:

The paper relies on a construction (due to Haken?) of a triangulated 3-dimensional manifold M(K) from a given knot K, such that M(K) is homeomorphic to the 3-sphere if and only if K is unknotted. Specifically, M(K) consists of two copies of S³-T(K), glued along their boundaries (which are toruses), where T(K) is a tubular neighborhood of the knot K.

So one algorithm for deciding whether a knot K is trivial is to construct M(K) and check whether M(K) is the 3-sphere. The 3-sphere recognition problem is in NP. Haas et al. used a slightly different technique to prove that UNKOTTING is in NP, but both NP-proofs rely on something called "normal surface theory" introduced by Kneser in 1929 and used by Haken in the early 1960s to boil everything down to integer programming(!). (For a brief outline of normal surface theory, read the introduction of Benjamin Burton's Ph.D thesis)

Hara, Tani, and Yamamoto describe an interactive proof protocol for KNOTTING based on this characterization, and similar to an interactive protocol for graph non-isomorphism. The prover is trying to convince the verifier that her knot is nontrivial. The verifier constructs two triangulated 3-manifolds—the manifold M(K) described above, and a particular triangulation S(K) of the 3-sphere. After randomly permuting the vertex labels, the verifier presents the prover with a one of the two triangulations, chosen uniformly at random, without telling the prover which it is. The prover then (supposedly) tells the verifier whether his given manifold is the 3-sphere.

(1) If the prover says that S(K) is the 3-sphere, the verifier learns nothing.

(2) If the prover says that S(K) is NOT the 3-sphere, the verifier knows he's lying and assumes the knot is trivial.

(3) If the prover says that M(K) is the 3-sphere, the verifier assumes the knot is trivial.

(4) if the prover says that M(K) is NOT the 3-sphere, the verifier assumes the knot is nontrivial.

If the knot is trivial, then no prover can convince this verifier with probablity better than 1/2. If the knot is nontrivial, an honest prover can convince this verifier with probability 1/2. Running this protocol twice inflates the probabilities to 1/4 and 3/4.

END PROOF

As an aside, the original two-round interactive proof for graph nonisomorphism is a beautiful example of the power of interactive proofs. It was first demonstrated by Goldreich, Micali and Wigderson in 1986, and I reproduce the proof here in full (for definitions, refer to the original paper).

1. Given two graphs G₁, G₂ on n vertices. the verifier randomly picks i ε {1,2} and a random permutation π of [1..n].
2. Verifier then sends π(G_i) to prover
3. Prover returns j ε {1,2}, and verifier accepts iff j = i.

Proof:
If G₁ and G₂ are nonisomorphic, the prover can figure out which is which by comparing the graph sent by the verifier to G₁ and G₂, and thus will always return the correct answer.

If G₁ and G₂ are isomorphic, the prover cannot tell the difference, and thus can "fool" the verifier with probability 1/2.
QED.

Unknotting...

With this I hope to start a series of posts on papers/ideas that I found interesting at SODA 2005. One of the side effects of no wireless access at SODA was that I couldn't comment on talks as they happened, but it (hopefully) meant that I had time to reflect on what I found interesting.

Exhibit 1, in no particular order, is the following result, by Hara, Tani and Yamamoto:

Unknotting is in AM ∩ co-AM

Unknotting is one of the more fundamental problems in knot theory. If we think of a (tame) knot as a (really tangled) loop in three dimensions, then much of simple knot theory focuses on the question: Given two knots, are they equivalent ? (where equivalence is expressed in terms of homeomorphisms).

The trivial knot (or the "unknot") is the simple circle in 3D, and thus the unknotting problem is:

UNKNOTTING: Given a knot, is it equivalent to the unknot ?

It was first shown in 1961 by Haken that Unknotting was decidable. After a brief gap of 36 years, Haas, Lagarias and Pippenger showed that Unknotting was in fact in NP (!), and conjectured that it was in NP ∩ co-NP. Other results along the way showed that Genus (is the genus of a knot less than g) was in PSPACE, and ManifoldGenus (a generalization to a given arbitrary manifold), was NP-Complete.

The new result speaks for itself. Formally, the authors show that Knotting (the complement of Unknotting) is in AM, by presenting a two-round interactive protocol for it. They also mention a corollary that if Unknotting is NP-Complete, then PH collapses to the second level. If I had paid better attention in my complexity class I would have figured out how this follows, but alas... I'd be grateful for any enlightenment. (Update: here it is)

The tragedy for me is that although it is clear that this result is interesting, the proof itself is rather impenetrable, requiring a knowledge of combinatorial topology above and beyond what I can muster up. This is why translators are needed ! (Update: here it is)

Knot theory is a good example of a (relatively arcane) subfield of mathematics that has suddenly become profoundly important in "real life". For more on this, read what well-known theoretical computer scientist John Baez has to say :).

On a more frivolous note, you can do knot art ! Calling our resident mathematical knot knitter...

Frank Harary, 1921-2005.

I wish I had known this earlier. Frank Harary, a graph theory giant most well known for his graph theory textbooks, died on Jan 4, 2005. There is more information at his homepage. (via mathpuzzle.com)

Timothy Gowers and the study of mathematics

When I was in high school I used to watch the Carl Sagan series 'Cosmos', and was fascinated by how he used to bring physics to life. I even remember the episode where he describes the physical consequences of the natural constants being closer to real life (suppose the speed of light was 50 mph, etc).

Ever since then, I've looked for expositors who could extract the same kind of beauty out of mathematics and computer science, distilling its essence in a way that might seem obvious to those of us who practice it, but that allows the core concepts to be revealed to a non-technical audience in a way that captures the imagination.

Timothy Gowers, the Fields Medalist, is well known for his expository articles on a variety of topics. He gave a speech in 2000 in Paris at an event sponsored by the Clay Mathematics Institute. The speech was titled 'The Importance of Mathematics', and I highly encourage watching it.

What struck me the most about this lecture was his eloquent defense of mathematics, and how he conveyed a sense of the aesthetic beauty of the field (why mathematicians refer to a theorem as 'beautiful'). With beautiful examples, he systematically laid out the landscape of a mathematical life, not in terms of topics, but in terms of how mathematical work is done.

He firmly dismissed the idea of mathematics needing to be useful (something we have had our own controversies over in theoryCS), and distinguished between the two statements

(1) Mathematics is not a useful subject
(2) A typical mathematician does not try to be useful.

arguing that (1) is false even though (2) is usually true, and that it should be this way.

A simple way of expressing some of the ideas in his lecture would be:

Mathematics is surprisingly useful, because complexity arises from simplicity and beauty reveals itself to be important.

I just bought his book 'Mathematics: A Very Short Introduction', which brings out these ideas in much more detail, and also puts to rest some of the usual canards associated with mathematics (the 30yr old rule, the lack of women, etc).

To some degree, the description of the daily activities of an algorithms researcher are similar to that of a mathematician, but in many ways they are different. We need a similar exposition for theoryCS !

Scian Melt #7

The latest delectable mix of things scientific and Indian is up.

RSS Feed from IEEE Computer Society

Yes ! Or as Dave Winer would say, "bing!"

---

Via Daniel Lemire

Numb3rs and mathematicians.

Ed Pegg of Mathworld has a nice page describing some of the effort put in by CBS to achieve mathematical versimilitude on Numb3rs. Some of the salient points:

• After CBS finished the pilot, they sent out letters to many mathematicians, asking for help in getting the math right (Ed was one of those who responded).
  
• They previewed the pilot at the 2005 Joint Math Meeting in Atlanta (the first TV pilot shown at a math conference!)
• They have mathematicians as advisors on the show.

I promise not to bore you with more Numb3rs posts (till next Friday at least).

Numb3rs Review: "Pilot" and "Uncertainty"

I only just got around to watching the first two episodes of Numb3rs. My plan (for as long as I can stand it) is to record any mathematical nuggets of interest that are dropped in the show. Overall, the series is decent as a CSI-type action thriller. There is far more action than I had anticipated, which is probably a good thing: makes it more crowd-friendly.

I don't know if it will last very long: the acting is a bit uneven so far, and the writers have introduced plot lines that need to be explored further (the tension between Don and his boss; the (non)romance between Charlie and his "graduate student"...)

Peeve alert: Apparently this grad student is from Madras, and her parents are arranging her marriage with a Hindu banker from Goa. Just Hindu ? Not a Vadama Iyer brahmin of an appropriate gotram ? and from Goa, of all places ? They eat meat there, for crying out loud. In any case, who lives in Goa anyway ? I thought only foreign tourists live there.

So here's the setup. Don is the FBI agent, Charlie is his "math genius almost 30yrold brother" with degrees from MIT and Stanford (not Princeton ?). There are various other irrelevant characters like the Obligatory Female Sidekick (OFS), Token agent of color (TAC), and gruff but caring dad (GCD). I don't expect to mention them much. There is also the crazy string theorist/mentor for Charlie, who for some reason needs help with his math, and has to suffer cracks like "Feynman and Witten did their own math".

WARNING: there will be spoilers; don't read this if you have a problem with that.

1. Pilot:
Plot:
Main plot line revolves around determining from a set of points (locations of murders by a serial killer) the home base of the killer. Much rambling about sprinklers and how from the location of the drops one can reconstruct the location of a rotating sprinkler. The key dramatic element is familiar to anyone who knows clustering:

Make sure you know what the "right" number of cluster centers is !!!

Short story: they thought the killer had one base, but he actually had two.

Mathematical jargon:
Not too bad overall. They even resisted the urge to claim that all mathematicians atrophy after age 30, merely having the mentor point out that Charlie was at the peak of his talents and most mathematicians have only 5-6 good years in them.

There was some good stuff about the difficult of humanly generating true randomness. and the usual bashing of the lottery (Don's boss makes fun of Charlie, but has a lottery ticket in his pocket). A useful mention of Galois (the mentor was worried that Charlie was getting distracted by "unclean" human problems).

One of the writers on the show has been reading blogs. There was a line that looked like it came from Sean Carroll's Preposterous Universe: "Why do we remember the past and not the future"

Charlie allegedly "built a weak force theory" with less than 96% probabillty. Whatever that means...

2. Uncertainty:
If there was any doubt in your mind that you should watch this series, this episode should dispel all of that. This, my friends, is the famous P vs NP episode (earlier than episode 4!)

Plot: Charlie has a new equation that predicts, given a series of bank robberies, where the next one will be. When the episode opens, he is being rather cocky about it. As it turns out he is right about the next location, but the standoff ends in a bloodbath and Don is injured, shocking Charlie so much he goes into a deep depression. As it turns out, the robbers are after something more involved.

Mathematical jargon:
The first inkling of what is to come appears after Charlie returns home, shell-shocked after seeing his brother wounded. He assembles blackboards like a madman in the garage, and as he walks by one board, you see the magic words: "SUBSET SUM". A few minutes later, you see another board covered with VERTEX COVER and COLORING and CLIQUE, with lines connecting them.

Be still, my beating heart....

Mentor dude walks in, and Charlie first states a theorem (the first of the series):

Minesweeper consistency is NP-Complete.

and then mumbles something about 3SAT and coloring algorithms. Finally Don arrives, and the mystery is solved. It turns out that Charlie works on P vs NP whenever he's depressed. As OFS puts it: 'beats binge drinking and strip clubs'. Charlie is apparently so obsessed with this that when his mother was dying of cancer he spent the entire time working on it.

By the end of the episode all are happy and Charlie has realized that instead of working on P vs NP, he will work on problems that he has some hope of solving. Now there's a lesson for researchers everywhere !

What warmed the cockles of my heart was the constant referring to P vs NP as a "famous math problem". Now I would have been a little happier if this had been referred to as a "famous computer science problem", but the thought of "pure" mathematicians everywhere being driven crazy by this statement is good enough for me :)

• Next episode review

Tags: numb3rs, review

Looking out for number one

Most of us are familiar with "Zipfian distributions" or "heavy-tailed" distributions, in which the probability of occurrence of the i^th most frequent element is roughly proportional to 1/i^a, where a is a constant close to 1.

A related "law" is Benford's law, which states that

On a wide variety of statistical data, the first digit is d with the probability log₁₀ ( 1 + 1/d)

An interesting discussion of this law reveals some underlying structure, specifically that if there is any law governing digit distributions, then it is scale invariant iff it is given by Benford's law.

Some other related laws that are more amusing, if less mathematically interesting are:

Lotka's Law:
The number of authors making n contributions is about 1/n^a of those making one contribution, where a is often nearly 2

Bradford's Law:
Journals in a field can be divided into three parts, each with about one-third of all articles: 1) a core of a few journals, 2) a second zone, with more journals, and 3) a third zone, with the bulk of journals. The number of journals is 1:n:n²

Shameless self-promotion

as of today, I now have over 100,000 page views (starting from Mar 31). Phew....

Ah... coffee

The National Geographic Magazine has a spread on coffee, "the world's most popular psychoactive drug". Be sure to check out the multimedia tour of coffee organized by photographer Bob Sacha.
And do the quiz. You'll be surprised at some of the answers.

---

Courtesy Karen Ho.

More visa fiascos

You just can't win: when a conference is in the US, people have a hard time getting into the country, and when it isn't, people have a hard time getting back into the country.

At least one SODA PC member had visa trouble precluding their coming to Vancouver. Moreover, one of the Best Student Paper awardees (Ravikrishna Kolluri) couldn't make it for visa issues: someone else had to give the talk in his place.

The fundamental silliness of all of this...

It's nice to have outsiders peep into our cloistered theory community from time to time. At dinner, I was trying to explain some of the business meeting discussion to John Baez, and the increasingly obvious look of incredulity on his face and my ever-more-convoluted attempts to explain myself soon made it apparent that something was seriously wrong.

Pretty much all of the annual handwringing we do over short/long/submissions/acceptance /quality/reviews/PC load and what have you, would just disappear in a "publish in journal/talk in conference" model. I realize that this is far too radical (though not innovative) an idea to ever be implemented any time soon, but you have to wonder why we in algorithms (and in computer science in general) put ourselves through such misery for no good reason. I have yet to hear a convincing reason why our model is superior to the math model¹.

Admittedly our business meetings would be a lot shorter (not to mention less beer), but I am willing to pay this price :)

---

1The only reason I have heard is that our journals take too long to publish papers, but that assumes that this would not change if we had no conference reviewing.

SODA business meeting redux.

Adam Buchsbaum now has slides for his SODA 2005 business meeting presentation. After opening remarks and some basic statistics, he looked at acceptance rates across topics, and found that overall there is no advantage to be gained by focusing on specific areas. He thankfully skipped the now de rigeur "silly" section of the business meeting, where exotic formulae and elaborate paper titles that optimize acceptance are proposed.

The next section discussed diversity on the PC and in accepted papers, recapping the statistics that I talked about earlier.

Why Are Submissions Going Up ?

Next, he addressed what is a growing concern: increased submission levels and how to deal with them (this has become a serious enough problem that the ACM has a task force investigating the matter). His data comprises submission/acceptance information from 1999 forward (although for 1999 he only had long paper submission/acceptance rates). The most striking fact is the steady increase in submissions over the past 4 years. Note that this is not accounted for by the start of short paper submissions in 1999; current submissions levels are well beyond that.

Most of the increase can be attributed to an increased number of long submissions (but this will be addressed below). The main takeaway from this graph and from the subsequent plots is that the popular hypothesis "submission increases can be explained by the dot-com bust and lots of people returning to academia", is not supported by the data. The increase in new authors (as defined as people who had not submitted before year X) is steady, but not bursty. In fact the increase in paper submissions can be directly attributed to an increase in submitting authors, an increase that comes from both new authors and returning authors. Interestingly, drop-outs (people who never submit after year X) match returning authors quite well.

It does not appear to be the case that people are submitting more; weighted (by number of authors) and normal "papers/author" shows a small increase, but not significant.

Short vs Long

The next part of the presentation is where things get really interesting. Two charts display statistics on the scores of papers. The first one indicates the expected bell-curve like chart. The second chart (suggested by Piotr Indyk) plots score against reverse rank, and shows that except at the top 10% and at the bottom 10% of papers, there is no natural cutoff where an acceptance-rejection line can be drawn. This is significant, because often acceptance rates are claimed to be set by some "natural cutoff": for SODA this year, this appears not to be the case.

What all of this feeds into is a serious debunking of the value of short papers. Adam takes all the reasons that have been proposed for having short papers in the first place, and trashes them one by one:

1) Short papers increase acceptance of discrete math papers
BEEP ! This is not the case. Papers labelled as "discrete math" (which also includes CS papers with a strong discrete math component) in fact were accepted at a higher rate (34.5%) than the overal rate (27%). They also broke down into long and short submission rates the same way as non-DM papers.

2) Short papers provide an anchor for page lengths not at 12 (so that authors don't feel that their 6 page submission is viewed as inferior to a 12 page submission)
PZZT ! Wrong answer. Acceptance rates were not correlated with paper length. In fact many good 7-10 page papers were accepted. Compounding this was the fact that many short submissions had 7 pages of appendices (!).

3) Short papers allow for nascent and inter-disciplinary work.
This is a noble idea, but since we have reached the limit (135) of papers we can accept, any such short paper has to compete directly against a long paper, and invariably loses out. Basically, it is a zero-sum game at this point.

There was much wailing and gnashing of teeth at this point, but IMHO Adam's rather convincing presentation of the data quelled much discussion. After all, it's hard to have a strong opinion when there is clear data that contradicts it.

Will short papers die ? It's not clear. After one of the over 10 billion straw votes that we had, it was decided that the SODA 2006 PC would "take into consideration" the sense of the community, which was:

a) No extra tracks
b) Short papers MUST DIE (err... have problems).

SODA wrap-up

still no paper reviews: wireless access at the conference was limited, and in a way this was a blessing. Instead of lugging my laptop around and fiddling with email in the middle of talks, I actually sat and listened (having to chair sessions helped as well). Not having the proceedings was a mixed blessing: most people felt that having access to the proceedings (or at least abstracts) would have made paper sampling a lot easier. On the other hand, I didn't have the urge to read the proceedings during talks.

Overall it was a nice conference, and Vancouver is a great town. For once, the hotel was quite pleasant, and the meetings rooms/lounging areas were just right.

over the next few days/weeks I will start posting some paper reviews, on whatever inspires me.

John Baez

gave an entertaining talk on loop quantum gravity. He managed to hint at a surprising amount of math without losing the audience, and if the questions at the end were any indication, people enjoyed a rather different talk to the normal SODA fare.

p.s SODA proceedings update: in Montana and moving steadily forward.

SODA business meeting

If I had drunk as much as prescribed, I'd be weaving right now. It almost seemed like people were finally getting tired of the endless discussions. Adam Buchsbaum did a deadly job of killing all feeble attempts to keep short papers alive (death by statistics was the coroner's report), and we shall see what the outcome is.

SODA 2006 will be in Miami (but not in Miami Beach alas). Cliff Stein will be the chair. It appears that SODA 2007 will either be in Monterrey, Mexico or New Orleans. Either way is fine with me :).

Pseudo-triangulations

A pseudo-triangulation is a polygon in the plane with only three convex vertices.

An interesting question about pseudo-triangulations is the following:

Is the number of triangulations of a planar point set at most the number of minimal pseudo-triangulations ?

From what I understand, this is true with equality if the points are in convex position. Herve Bronnimann talked about an experimental approach to validating this conjecture for small values of n.

p.s no wireless connection at the conference alas, so posting will be occasional.

asides...

1. The SODA (and ALENEX) name badge has on its flip side a form that reads:

IN CASE OF EMERGENCY
Name of person to contact

Phone # to reach this person

I didn't realize SODA had become such a heart-stopping adventure. Next thing you know we'll have FBI agents roaming the corridors.

2. The SODA proceedings will not be available at the conference because the train carrying them was derailed in Minnesota.

I kid you not.

p.s If ever we had an argument to reduce the number of papers accepted to SODA...

p.p.s On the bright side, I don't have to throw my back out lugging copies of the proceedings around with me.

ALENEX

So ALENEX started and ended today. The workshop started off with a keynote address by Bernard Moret on the Tree of Life and algorithmic issues in phylogeny. He set out an impressively complex landscape of problems, most of which required some serious algorithm engineering (fitting for ALENEX). One quote that I found rather amusing:

Truth is not part of the vocabulary of algorithm design

This was when discussing how the goal of algorithms (optimization) differs from the goal of biology (scientific truth).

Later on, at the business meeting, we had the customary discussion of mindless statistics (how many papers were written by left-handed dwarfs from the eastern provinces of Transylvania ?). 15/60 papers were accepted, which is an impressive acceptance ratio. The submission rate appears to be relatively stable, and 15 is the maximum number of papers that can fit in a one-day workshop. Another mildly interesting stat was the fraction of papers submitted from Europe - 44.6%. This (to me) appears to be quite high, especially given that the workshop is in the West Coast.

Cathy McGeoch brought out a beautiful poster representing the history of NP-Completeness. It has a top section describing NP-hardness and complexity, and the main area of the poster is taken up by a graph in which vertices are NP-hard problems and edges are reductions. The nodes are colored by their Garey+Johnson classification, and immediately you see how SAT pops out as the source problem of choice for so many reductions.

The poster is being sold for $120 + $15 shipping (it's at least 36'' X 48''), and was designed by an ex-Amherst faculty member who now runs a graphic design company. No web pictures or thumbnails as of yet: I'll update this post when they appear. If you want to order a poster, send mail to Cathy [ ccm at cs dot REMOVEamherstTHIS dot edu ]. [Update: Click here for the poster website and a nifty Flash tool to navigate the poster.]

One of the motivations that Cathy mentioned was the lack of computer science art. It would be cool if we could create a poster for Chad Brewbaker's Complexity Zoo map.

In later postings I will mention some of the talks that I found interesting. I've been blogging from conferences for a while now, and I notice that I often feel the pressure to say something about every paper, for fear that by exclusion, I am making a statement about a talk/paper. Rest assured that this is not the case.

In related news, Lance inspires yet another theorist to start a blog. He is indeed the Blogfather of theory :).

For the 1000th time, Bell Labs != AT&T !!!

I can understand fellow researchers being confused (OK I can't, but I can at least try), but the New York Times ?

With four titles of his own, Mr. Eslambolchi, who also directs Bell Labs and AT&T's network operations, manages engineers, technicians and researchers in 11 divisions and speaks directly to dozens of customers a month to hear what they want

Repeat after me: Bell Labs is Lucent, Shannon Labs is AT&T.

SODA/ALENEX

Am at SODA/ALENEX right now: posting will be slow, but I will attempt to have some kind of summary of the daily activities. If anyone is reading this AND is at SODA AND doesn't have a blog of their own, feel free to email me to post conference updates here.

Betti Numbers

It's been many days now since Afra Zamorodian announced his new monograph 'Topology and Computing'. Now that I finally got a chance to read an excerpt, I am encouraged ! Finally, I am hoping that there is a way to understand Betti numbers without needing an entire year's worth of study :).

Great job, Afra ! Topology is an area that has many intriguing connections with geometry and algorithms in general (Kneser's conjecture, the Kahn-Saks-Sturtevant partial resolution of the evasiveness conjecture), and we need books that can bridge the gap. Another "geometric' text is the wonderful book by Matousek on the Borsuk-Ulam theorem, and a more 'combinatoric' text in this regard is the survey 'Topological Methods' by Björner in the Handbook of Combinatorics.

It's already in the text. It just needs a close reading.

Lett3rs. coming to a screen near you...

Those stinkin' security intellectuals...

This is a cool quote:

We have to nip it in the bud or soon there will be no security left after these intellectuals get through with us.

This is the source: alt.locksmithing

---

Via BB.

p.s Matt Blaze used to work at AT&T Labs.

Tags: locks, cryptography

Teaching...

I'm teaching a class, something that I don't often do, and have been discovering interesting differences (duh!!) between a one-hour talk and a 1.5hr lecture. A recent article on Slate excerpts a new book by Eric Liu called 'Guiding Lights', about teachers in different walks of life, and how they hone their craft. One quote from the article was interesting:

Like any good teacher, Bryan is a master of misdirection: working on a fastball to improve a change-up, using dry work without a ball to sharpen performance with a ball, and talking about how to keep a quiet head when, in fact, we were talking about how to keep a quiet mind.

It's an interesting way of describing the work a teacher does. A review from Publisher's Weekly at the Amazon.com page talks of other techniques, like

receiving before transmitting—that is, tuning in to the student's unique qualities and motivations; unblocking and unlocking—helping students overcome their inner obstacles; and zooming in and out—breaking the subject down and then connecting it other matters.

I'm curious to know what the full-time teachers think of this...

if I were an idle grad student...

Here would be a cool thing to hack:

HubMed is an RSS interface to PubMed (the equivalent of arxiv, but much better, for the bio/medical community). Plug your PubMed search into HubMed, and lo and behold, out pops a search with an RSS feed you can subscribe to. Think of it as a specialized Feedster for PubMed.

The CoRR now has an experimental full text search to go with their category searches. You could always subscribe to RSS feeds for new papers in specific categories. Wouldn't it be neat to have a Feedster-like interface for general text searches, so I could get all new papers that mention "art gallery" for example ?

It seems like it is not hard conceptually: a web form to process requests for searches, and a crawler that queries CoRR (along with some parsing goo to make XML).

What is the Fold ?

"This is your last chance. After this, there is no turning back. You take the blue pill, the story ends, you awake in your bed and cut whatever you want to cut. You take the red pill, you stay in OrigamiLand, and I show you how deep the creases go.

Remember: all I’m offering is the Fold, nothing more."

---

Via emmous

Paper review models

Two approaches:

1. If you are a student.
2. If you have a young child :)

Scian Melt #6

Welcome, one and all, to the Scian Melt #6. The Scian Melt is a carnival of science, with a heavy dose of Indian spices. For a second helping, visit the Scian Melt homepage.

The terrible tsunami is constantly on our minds: Wikipedia has much more information about how a tsunami is formed, as well as links to the latest news on the disaster itself. If you are one of the ten remaining people on the planet who hasn't visited SEA-EAT, please do so, and contribute in whatever way you can.

Tony Denmark has a page of before-and-after scenes of devastation in Sri Lanka and Indonesia. The devastation in Banda Aceh is truly horrifying.

It is a cliche (but still true) that tragedies bring out the best in people, and remind us of the worth of those that we so easily dismiss in calmer times. Anna from sepiamutiny points out that the vast majority of men working to remove bodies in the most affected areas of Tamil Nadu are Dalits, or "untouchables" as they used to be called. Considering how so many others are shying away from dealing with the vast numbers of corpses and the imminent health catastrophe, they deserve our recognition.

In the wake of the disaster, controversy raged over whether the tsunamis could have been predicted, or if anything could have been done to lessen its impact. Janaki Kremmer at the Christian Science Monitor pens an article about how mangrove forests saved hundreds of villagers by forming a natural barrier between villages and the sea.

But along with true science comes the wackos. There are numerous conspiracy theories about the cause of the tsunami, with one of the more popular ones being an Israeli-Indian joint nuclear test. Arm your falsifier guns, folks !

In other news, Atanu Dey laments as to why Indians are prone to both reflexive self-bashing and a blind pride that obscures our true failings. He asks

Does anyone ever ask the question: Why is India the way it is?... When was the last time you ever heard of a conference where serious people with lots of knowledge and understanding got together to examine that question?

Well, as it turns out, the 92nd Indian Science Congress was held last week in Ahmedabad, with discussions on Indian pharmaceuticals, stem cell research, and disease prevention. It turns out that haldi (turmeric) is really really good for you. Research now shows that curcumin (an active ingredient of haldi) can be used to design effective anti-malarial drugs. What's more, curcumin has been shown to help stave off Alzheimer's, as well reduce plaque that may have already built up in the brain. Eat Indian food often, people !

To end this melt here's a nice page summarizing the history of Indian Mathematics (I am after all a computer scientist).

The next Melt will be hosted by MadMan: please send your nominations to melt [at] thescian [dot] com or madman [at] madmanweb [dot] com

Hmmm...

Interesting:

These are organizations that have fired, threatened, disciplined, fined or not hired people because of their blogs:

1.) Delta Air Lines
2.) Wells Fargo
3.) Ragen MacKenzie
4.) Starbucks
5.) Microsoft (some say yay, some say nay)
6.) Friendster
7.) the Houston Chronicle
8.) the St. Louis Post-Dispatch
9.) Nunavut Tourism (Canada)
10.) the Committee on Degrees in Social Studies, Harvard University
11.) Maricopa County Superior Court of Arizona Self Help Center and Library
12.) Mike DeWine, US Senator (R-Ohio)
13.) the Durham Herald-Sun
14.) Kerr-McGee
15.) ESPN
16.) Apple (according to this blog entry AND this article)
17.) Statistical Assessment Service (DC nonprofit)
18.) Minnesota Public Radio
19.) The Hartford Courant
20.) the International Olympic Committee (barred athletes from blogging during the Olympics last summer)
21.) Health Sciences Centre, Winnipeg, Manitoba, Canada (?)
22.) the National Basketball Association (NBA)

This could be a description of my day...

With the hammer being applied by myself :). At least I have a Ph.D !

From PHD

What do you believe is true...

...even if you cannot prove it ? This was the question posed by Edge.org to a number of scientists, intellectuals, and thinkers of various hues. There have been numerous comments on this article, and a spread in the NYT, but what I found interesting was the choice of people interviewed. There were extremely few computer scientists in the bunch, and not a theoretician among them ! John McCarthy thinks that the continuum hypothesis is false...

Any thoughts on what statements we believe to be true, even if we can't prove them ? P ? NP is not included :)

How did I miss this ?

A number of us were fretting about how Numb3rs would caricature mathematicians, while NBC slipped this right under our noses:

NBC's new sitcom, "Committed," a series centered on the romance between Nate (Josh Cooke), an obsessive-compulsive math genius and his nutty girlfriend, Marni (Jennifer Finnigan), makes it clear: psychological disorders are the next big thing.

As for the character 'Nate':

Nate, a math genius whose family makes the Tennenbaums seem like the Partridge family, works in a used-record store and nurses his fixations: he has an obsessive fear of elevators, blocked emergency exits and throwing things out. One episode revolves around Nate's attempts to keep Marni from seeing his apartment, which looks like a cross between the CollyerBrothers' brownstone and the schizophrenic mathematician's garage in "A Beautiful Mind"

The review ends with this rather cruel jab:

Mr. Cooke is appealing in the role of Nate, but he seems a little wholesome for someone who makes Venn diagrams to map out a conversational point.

Hey ! Watch it there ! Us borderline-psychotic obsessive-compulsive math geeks have feelings too.

Not that I am complaining...

But it seems a bit odd that the first link of the google search "soda 2005" is a page from the Geomblog, and even worse, the official SODA 2005 page doesn't appear anywhere in the top 50 links for this search.

On conference loads

The topic of acceptance ratios and PC sizes has been discussed to death, and I will start by saying that I have nothing new to add to this debate :). However, on the issue of reviewer load, one new idea had popped up a while ago:

* To handle the case of recycled papers that go from conference to conference in the hope of finding reviewers that haven't seen them:
- Create a repository where all submitted papers are registered. When a paper is submitted to a conference, a link is set up, and then when reviews return, they are filed with the paper. If the paper is submitted again, the reviews are there to see.

I was reading the Dec issue of CACM (all right, I admit it: I do read the CACM, but ONLY because this issue was on the blogosphere!), and in David Patterson's letter was this nugget:

Perhaps the most novel approach to the whole problem is being taken by the database community under the leadership of SIGMOD. The three large database conferences are going to coordinate their reviewing so that a paper rejected by one conference will be automatically passed along to the next one with the reviews. Should the author decide to revise and resubmit the paper, the original reviewers will read the revision in light of their suggestions. The next program committee would then decide whether or not to accept the revision. Hence, database conferences will take on many of the aspects of journals in their more efficient use of reviewers' efforts in evaluating revisions of a paper.

I assume the three bigs are SIGMOD, PODS and VLDB ? It would be interesting to see how this works out. There are pros and cons in carrying prior reviews along with a paper, and a lab experiment such as this might reveal interesting side effects.

Another interesting chart in this letter was a plot of submissions and acceptance ratios for four major conferences (SIGMOD/STOC/ISCA/PODC) over the past 5 years.

What I find most striking about this graph is that on the one hand, SIGMOD submission counts have gone up (pretty much what one would expect), but the acceptance rate has held roughly steady, implying the conference has grown in size over the years. In STOC, on the other hand, submission counts rose, and then remained steady, but acceptance rates have dropped precipitously ! Seems strange that this would happen.

One of my pet peeves has been hearing a slew of theories trotted out to "explain" the increased submission rate in a variety of conferences (though not STOC); my gripe has been that none of this theories have anything more to back them up than plausible sounding words. Interestingly, Patterson's letter has something to say about this as well:

ACM's research conferences are run by its Special Interest Group (SIGs). I've been working with the SIG Governing Board to help form a task force to study this issue, looking at why submissions are increasing and documenting approaches like those discussed here, and to evaluate their effectiveness. They plan to report back in early 2005. If you have any comments or suggestions, please contact task force chair Alexander L. Wolf (alw@cs.colorado.edu).

A Gallery of Visualization

It appears that art and geometry go well together. Take George Hart's geometric sculptures, or the Voronoi building. I found this intriguing gallery of visualization via del.icio.us/math:

The above picture is a visualization of nodes in a graph evolving by the rule:

A. Move close to friends but not closer than some minimum distance.
B. Distance self from non-friends as much as possible.

Tsunami help

tsunamihelp.blogspot.com has rapidly become the central clearinghouse for information about aid efforts after the disaster. Also, closer to home, D. Sivakumar of IBM Almaden is involved with redroots.org:

Red Roots is a network of compassionate individuals who care about the less fortunate. Our immediate goal is to get a million donations to the American Red Cross disaster relief fund for the Asian Tsunami crisis (through Amazon): Go to Amazon and donate $5 to the American Red Cross. Call, email, or visit 2-4 individuals you know and get them to do likewise (donate $5, sign up more people). The emphasis here is on the million, less on the $5 (or Amazon or Red Cross). If each of us donates and finds two new participants, we can very quickly reach the million mark. If this experiment succeeds, we hope to build a much larger network of compassion whose potential we can only imagine.

Spread the word...