STOC 2004: A Report (Part III)

This is the third post in Chandra Chekuri's STOC 2004 report: Part I and Part II were posted earlier.

---

A Probabilistic Lemma due to Uri Feige

One of the cute results in STOC is the following probabilistic bound due to Feige.

Let X₁, X₂, ..., X_n be independent positive random variables with mean 1. Note that we do not make any assumptions about their distribution and hence their variance can be arbitrary and in particular they are not iid. Let X = X₁ + X₂ + ... + X_n. By linearity of expectation µ, the mean of X, is n.

A typical question in bounding the deviation of sums of random variables is the following.

What is probability that X deviates significantly from its mean?
We have a variety of bounds including the Markov inequality, the Chebyshev inequality and of course the Chernoff-Hoeffding bounds. Of these the Markov inequality is the simplest and pretty much makes no assumptions other than that the rv is non-negative:

Pr[X > t µ] <= 1/t for a non-negative rv X.
Phrasing it in a different form, Pr[X <= t µ] >= 1-1/t.

Cheybyshev inequality is useful when we have a bound on the variance of X but in our case we don't. Chernoff bounds are the most useful for sums of bounded independent random variables. Feige's bound is quite different. He showed that Pr[X <= n+1] > 1/13. In other words there is a constant probability that X deviates by an additive 1 from the expected value. Note that the Markov inequality would give a bound of 1/(n+1) which is very far from the truth in this case.

Feige uses the above bound for an application to estimate the density of a graph but it is not the most compelling one (as he himself states). He anticipates more interesting applications in the future.

An Open Problem:
The bound Feige shows is 1/13 but the worst case example he knows has a bound of 1/e where e is the base of the natural logarithm. It is the obvious one: Each X_i takes on a value of (n+1) with probability 1/(n+1) and 0 otherwise. Therefore the probability that X is at most n+1 tends to 1/e. Feige conjectures that this the right bound. The problem is all yours.

---

Calling India

WARNING: Non-geometry info ahead...

---

Reliance India is now offering 12c/min calling card service to India. This is significantly better than what current calling card operators are giving, and is way better than what the big telcos like AT&T et al are offering (much as it hurts me to say so :)

I just signed up, and so I don't know what the call quality is like, but given that that is a Reliance endeavour, it should be good.

More on loops and strings

Readers of this blog will recognize my unhealthy fascination with loop quantum gravity and string theory. In my browsings of arxiv.org, I discovered a section of the physics area on popular writings in physics (what a concept: why can't we do this in theory CS too?). There's a nice article there by Rüdiger Vaas called 'The Duel: Strings Meet Loops' that explains the conflicts between the two approaches to unifying quantum physics and general relativity.

A related article is a Socratic dialogue between a fictitious professor and student on the pros and cons of string theory and loops. Bear in mind that this was written by Carlo Rovelli, one of the fathers of loop quantum gravity, so it is may be somewhat biased :)

And for those of you who say 'Bah ! Humbug ! Why should I care about such nonsense', I say 'Don't you want to understand John Baez's talk at SODA ?'

Automaton Simulator

Someone emailed me, asking if I knew of any packages that simulated various kinds of automata for visualizing their behaviour. I did some sniffing around, and found this package.

It simulates DFAs, NFAs, DPDAs, and Turing machines. From the interface, it doesn't appear to be that useful for large scale automaton construction, but is easy to play with interactively. Runs in Java.

Blog Page Update

I now have a (long overdue) collection of links to what I call "theory blogs", which I loosely define as pages with RSS feeds that are primarily theory-CS related. It's on the right side of the page, below my user profile. If there are other links I have missed, feel free to inform me (I won't guarantee I'll add them in though :) )

STOC 2004: A Report (Part II)

Chandra Chekuri continues his report on STOC 2004.

---

Todays topic is Jonathan Kelner's paper that won the best student paper at STOC a few days ago.

Many people know about the planar separator theorem: every planar graph has a vertex separator (a set of vertices whose deletion separates the graph into two pieces of roughly equal size) of size O(√n). For a bounded degree planar graph the same theorem also shows that there is a cut of sparsity O(1/√n). These results extend to graphs that can be embedded on a surface of genus g - vertex separators of size O(√(gn)) and cuts of sparsity O(√(g/n)) exist. Gilbert, Hutchinson, and Tarjan showed how to find the separator (cut) if the embedding of the graph in a genus g surface is given as part of the input. The catch is that given a graph G, the problem of finding the genus of the graph is NP-hard. It has been an open problem if one could find the separator and cut without finding an explicit embedding.

Another related question is the following. A popular graph partitioning technique used in practice is that of spectral partitioning. Spielman and Teng showed that this algorithm is also good in theory for planar graphs by demonstrating that the algorithm always yields a cut of ratio O(1/√n). They conjectured that the spectral method also works for higher genus graphs and thus pointed a way to overcome the problem of not knowing the genus explicitly.

Kelner's paper resolves the above two problems by proving that the spectral methods yields a cut of sparsity O(√(g/n)). The high level scheme is from Spielman and Teng. Kelner generalizes the scheme using some nice results from algebraic geometry. This result is beautiful because of the connection between combinatorial objects (graphs) and continuous mathematics (ed: Aha !! ).

Here is a brief description of the method. Spielman and Teng use the Koebe-Andreev-Thurston theorem which shows that planar graphs can be obtained as a contact graph of disjoint circles on the plane (or equivalently on the surface of a sphere in 3 dimensions) where there is an edge between two vertices u and v iff the circles corresponding to u and v touch tangentially.



Using this circle packing theorem, Spielman and Teng show via a simple but clever argument that the second eigenvalue of the Laplacian of the graph is O(1/n).

The result for genus g graphs would follow from the same approach if it can be shown that the graph can be obtained by the adjacency graph of circles touching on the sphere with the proviso that any point on the sphere is contained in at most O(g) circles - in other words we allow overlapping circles now. Unfortunately this cannot be done. To overcome this Kelner uses a theorem of He and Schramm that shows that genus g graphs can be obtained by touching circles where the circles are disjoint and embedded on a Riemannian surface of genus g. The technical part of the proof involves mapping the Riemannian surface back onto the sphere via conformal mappings (mappings that preserve angles). Difficulties arise because the original mapping to the Riemannian surface has branch points which are points of singularity and the mapping from the surface to the sphere does not maintain conformality at these branch points. The number of branch points is however limited to O(g) and by using a fine subdivision of the graph it is shown that these singularities do not play a major role.

The above description is at a very high level. The paper of Kelner is short - it uses several important known results from mathematics in a direct and effective way. It is impressive that he knows enough math to know and put them together - most people in the audience at STOC including myself have limited background in the continuous mathematics that is needed to do this proof. I wish that I had more classes in pure math ...(ed: Amen..)

References:
J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan. A separator theorem for graphs of bounded genus. J. Algorithms, 5:391-407, 1984.

Blogging etiquette

Most blogs, even today, are essentially online diaries; in fact the proliferation of blogs is directly due to this, since anyone can write a diary, even if not anyone can create web pages. However, more and more, one finds specialized "topic" blogs: political blogs being the vast majority, but also for topics like music, photography, the media, and even academic disciplines like economics, philosophy, and of course computer science.

As I write entries, I am conscious of the fact that my posts are a form of public announcement, and as such should be governed by some of the rules of normal academic public discourse. When I chat with people at conferences about problems and results, I have to be careful in what I say about these conversations, in the same way that I would be careful in one-on-one discussions. However, it seems to me that if I hear about a new result, and the result is not confidential, telling a colleague at lunch is still different to posting it on a blog, mainly because of the illusion that I can control the rate of dissemination of information. Moreover, as with normal conversations, I wouldn't want people to think that everything they told me could end up as a blog entry at some point.

A discussion on these lines has been going on in some of the philosophy blogs. I think this kind of discussion will probably happen more and more as more disciplines turn to blogs as a means for information dissemination and general discussion.

Geometry Junkyard RSS feed.

Start your aggregators ! David Eppstein's Geometry Junkyard page, (that I have mentioned in the past), now has its own RSS feed.

From the "NP != Non-Polynomial" department...

Was browsing some science news, and came upon this tidbit (emphasis added) in a PR release for a SIGGRAPH paper on mesh simplification:

Computer scientists have struggled with the problem of finding an optimal mix of large and small elements for years. In 1998, theoreticians proved that the problem was ''NP hard'' -- that no general solution exists that can be solved by a computer in finite length of time.

Sigh...

Later on, the article goes on to say:

'This is not a hack,'' says another expert, in the field [.. snip ..], using the term for a makeshift, unsystematic improvisation. ''It has a strong formal basis. You can make up extreme cases that will trick it, but for ordinary shapes, it works remarkably well.''

That's funny. Strong formal basis, but has extreme cases that can trick it ? If it sounds like one and smells like one....

STOC 2004: A Report

I am happy to introduce my very first guestblogger, Chandra Chekuri from Bell Labs. Chandra was recently at the ACM Symposium on the Theory of Computing (STOC) in Chicago, and has this report from the conference:

---

This year's STOC was in Chicago as most of the readers of this blog already know. It was the first time in Chicago for me. The hotel was in downtown right across from Grant Park near Lake Michigan. I went early on Saturday and had a chance to walk around and check out the Blues Festival in the park and walked the Magnificient Mile. Didn't have much time to do anything else touristy but had a very positive impression of the city. Maybe I should also visit during the winter to have a balanced view!

I felt that the papers in this STOC were particularly good. In addition to the usual breadth of topics, several papers in each topic were quite interesting. The two best award papers and the two best student papers were very well received.

Best Papers:
* Multilinear Formulas for Permanent and Determinant are of Super-Polynomial Size, by Ran Raz.
* Expander Flows, Geometric Embeddings and Geometric Partitioning, by Sanjeev Arora, Satish Rao, and Umesh Vazirani.

Best student papers:
* Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus, by Jonathan Kelner
* Lower bounds for local search by Quantum Arguments, by Scott Aaronson.


Interestingly there was one algorithms paper and one lower bounds paper in each category. Algorithmic game theory, quantum algorithms/complexity, and sub-linear time algorithms (including property testing) are still the relatively new topics along with the more established areas.

The invited talks reflected the invasion by the new areas. The most interesting of the invited talks was by Avi Wigderson who was asked by Laszlo Babai to comment on whether theory of computing is still a unified discipline given the many diverse sub-areas that are represented at STOC/FOCS. Avi gave a very nice talk on this. He showed how communication complexity is central to many of the topics. He also connected interactive proofs to many areas and finally concluded with what he thought was the glue between the areas. He promised to put up his slides on his web page soon and you can see them for yourself (ed: will add a link when it is available link). One of the glues that he mentioned are people like Les Valiant who have contributed deeply to many different areas.

Most of the Business meeting was taken up by the discussion on moving the STOC special issue from JCSS to other journals. You can read more about this on Lance Fortnow's and Jeff Erickson's blogs. I am all for moving away from for-profit journals (especially Elsevier and Kluwer) to either society journals (ACM, SIAM, IEEE, Math Programming, INFORMS etc) or free electronic journals. Laszlo Babai very recently started a new free electronic journal ToC (Theory of Computing). With several very highly respected journals such as JACM and SICOMP available as society journals, will authors send their good papers to ToC? Or will this journal turn out to be like the Chicago Journal of TCS that was started by Babai many years ago and failed to catch on? I think times have changed and there is a higher probability for ToC to be successful. One thing that did bother me was that Babai chose to have most of the STOC'04 committee (of which he was the chair) as editors. The STOC'04 committee is filled with many fantastic young researchers, however some of the comments that Babai made and the way he went about choosing the editors makes one feel that ToC is his own show. In my opinion a respected journal should have a certain reputation that is independent from the editor-in-chief even though the editor-in-chief is well known and respected through out the community. I wish the best for ToC and I hope the editors lead the way in making it a success.

STOC 2005 is in Baltimore and there was a bid from U. Washington faculty Paul Beam and Anna Karlin (delivered by Venkat Guruswami) to host STOC 2006 in Seattle. Vladen Koltun compared the registration fees and hotel rates at STOC with those of SoCG and was wondering why we don't make more of an effort to make the whole thing cheaper. This issue keeps coming up but people ignore it - my take is that the people who care about it the most are not present at the business meeting! Another potential reason is that we have several conferences (at least three major ones, STOC/FOCS/SODA) each year and it is difficulty to find volunteers to make all this work out cheaply. That brings up the topic of the next conference, FOCS 2004, to be held in Rome, Italy. The accepted papers list will be out soon, June 25th according to the call for papers.

Another post will detail some of the papers and ideas that I liked the most at STOC.

---

Successful ideas...

In science, successful ideas are those that are pervasive and invasive, are invitingly elegant and methodical, are open to extensio9ns and variants, andc apture and objective necessity, ansswer a widespread but diffuse sense of dissatisfaction in the scientific community


Christos Papadimitriou, in NP-Completeness: A Retrospective (via the P-NP page)

geeks and fonts...

A couple of years ago, when Agarwal, Kayal and Saxena announced that PRIMES was in P, an entry was posted on slashdot and much of the early discussion centered not on the proof itself, but on how to convert PS to PDF, and the relative merits thereof (this was prompted by the fact that the authors had linked a PS file online).

A few days ago, Lance Fortnow posted a note about one of his favorite theorems in complexity, a result by Trevisan connecting extractors and pseudo-random number generators. He got 9 comments; a fair number. All of them were devoted to the technical details of PS to PDF conversions !!

I am as happy as the next person to jump into a lecture on using type1 fonts with latex, but....

Don Quixote enterprise ?

Via /., news of the first quantum computer simulation tool. However, what I find most interesting is this excerpt (emphasis mine):

Classical simulation of quantum processes seams like a Don Quixote enterprise - this is well known. But imagine, you may test all the quantum algorithms you have in mind now - not tomorrow when everybody is able to press them in hardware. Let's discover the quantum ways by simulation now - to reach the world of Quantum Computing today.

Something must have been lost in translation...

Losing a Ph.D for discredited papers...

From today's NYT:

A German university has revoked the doctoral degree of the former Bell Labs scientist who claimed a series of research breakthroughs, then was fired two years ago when it was discovered that he had manipulated data and fabricated results.

The physicist, J. Hendrik Schön, 33, did not commit misconduct in his doctoral research at the University of Konstanz, an investigation there found last year. But on Friday, the university said it had a legal right to rescind a degree when the recipient behaved "unworthily" of it.

I have mixed feelings about this: on the one hand it appears that he did fabricate data at Bell Labs. However, to rescind his Ph.D seems arbitrary, even if the university "had a legal right" to rescind it.

RSS for papers

The time has come to have RSS feeds for subjects at a much finer granularity than what arxiv.org provides. Suppose I want to track papers on art gallery problems. Today it is not hard to imagine a spider that crawls well known sites like SoCG conf pages/SODA web pages etc, finds paper titles, and determines what papers might be of relevance to an art gallery problem search. One could use Feedster right now for such a search, but searching over the entire web will generate a lot of junk (or nothing at all)

Seems like it would not be hard given current web technology....

SoCG: The Business Meeting

Read all about it here

SoCG: The Cruise

Last night our conference banquet was on a cruise boat that went up and down the Hudson and East River. It's a good way to see the less serious side of CG researchers. Bernard Chazelle is an accomplished guitarist, and during the cruise we had a number of solo pianists (jazz/classical) performing for our benefit.

Tverberg Points

Inspired by Algorithms for Center and Tverberg Points by Pankaj K. Agarwal, Micha Sharir, and Emo Welzl:

Usually, checking if a point satisfies property X is easier than finding a point that satisfies property X. Tverberg points are an example of a rather bizarre reversal of this situation.

Suppose I take a collection of points in the plane, and partition it into subsets cleverly so that the convex hulls of the subsets all intersect in at least one point. Such a point is called a Tverberg Point. It was shown by Tverberg that such a point always exists. However, the following problem has unknown complexity in three dimensions:

Given a point p and a set of points P, is p a Tverberg point of P

---

The Tverberg point is one among a family of nonparametric notions of "deep" points in a point set. Other notions are the centerpoint (a point that "sees" the maximum number of points no matter which direction it looks in), and the Radon point (a Tverberg point where you partition P into two pieces).

Problem 2: Coins...

Heard around the dinner table....

I am given n piles of coins, with the knowledge that the total number of coins is 1 + 2 + 3... + n. I take one coin from each pile, and make a new pile. If the i^th pile has i coins, this operation leaves all piles unchanged. Prove that no matter what starting configuration of coins in piles I start with, I always end up with this stable configuration.

Answer in a week, or thereabouts...

SoCG...Live !

Am at SoCG right now: will attempt to report on the activities as they happen...

Traditional dinner table conversation at conference dinners involves either gossip or tossing around of problems. Sometimes one even solves them ! I had mentioned the turnpike problem a while ago, and its variant, the "sum-turnpike" problem. Thanks to Vladlen Koltlun and Shankar Krishnan, there is now an efficient poly-time algorithm for the sum-turnpike problem.

Alan Turing: 50th Death Anniversary

Alan Turing died 50 years ago today. We often use the word genius lightly: for him, it is fitting...

---

Cryptonomicon is set partly in the Enigma period of WW II, and has many very accurate discussions of Turing machines and the halting problem. Turing is a character in the novel as well.

SODA 2005 invited speakers

Some of you may recall my musings on quantum gravity and the discrete nature of spacetime. I am delighted to note that at the upcoming Symposium on Discrete Algorithms, we will have an invited talk on loop quantum gravity by John Baez of UC Riverside.

Prof. Baez writes an occasional column called This Week's Finds in Mathematical Physics.

---

Micha Sharir and Uri Feige will also be speaking at SODA; two better speakers one will be hard-pressed to find...

FSTTCS Announcement

FSTTCS is the premier Indian conference on theory/algorithms/fundamental aspects of computer science. It's always in winter, so the weather is nice :), and this year it is in Chennai, in the south. The deadline for submission is coming up (Jun 21). More details are in the call for papers

Passwords as one-way functions

This is an interesting article: the premise is that a password should be something that is individualized, but not conscious:

In tests of the picture version, users went through a two-step process to get a set of user certificates, or unconscious passwords. Users were first shown a set of 100 to 200 pictures randomly selected from a database of 20,000 pictures. Pictures were organized in groups of 2 to 9 pictures with a common theme, and each user was certified on one picture from a given theme group. The user then practiced choosing certificate images from entire theme groups.

Later, in lieu of passwords, users identified most of a short series of certificate images. To guard against eavesdropping, each certificate picture is only used once, and the user retrains when they run low.

Subjects were able to recognize previously seen pictures with better than 90 percent accuracy for up to three months. According to the researchers' calculations, the chances that a user who guesses correctly four times in a row is an imposter is less than 1,000th of one percent.

Our ranks are growing :)

Just discovered Jeff Erickson's not-new blog (he has posts dating back to Sep 2003, but most activity appears to be recent). Congratulations on getting tenure !

How did I discover it ? Sitemeter: a great place to satisfy one's inner narcissist.

419 scams and world affairs

I have decided that instead of actually trying to read newspapers to figure out what is going on in the world, I will just monitor my 419 scam mail. So far in the past few years, I have got 419 scam variants from major hotspots in the world:

• Nigeria of course
  
• Liberia
  
• Sierra Leone
  
• Haiti
  
• And now Zimbabwe.
  

I am somewhat disappointed to have not received anything from Sudan, and even more surprised that nothing has come from Iraq. I am expecting some mail from the Congo in the next few days...

Upcoming events: sausage and soda

• The Symposium on Computational Geometry will be in NYC from Jun 9-11.
  
• The ACM Symposium on the Theory of Computing (one of the main theory conferences) will be in Chicago from Jun 13-15, where you can also visit the original theory blogger :)
  
• The paper submission deadline for the Symposium on Discrete Algorithms (SODA) is approaching (July 5). Consider this your first warning...
  

Math meets Hollywood

(Via slashdot...)
A little-known fact about "Futurama", FOX's cancelled cartoon sitcom about a pizza delivery boy stuck in the future, is that many of the writers had advanced degrees in math or related fields. Read this article for more info.

A personal connection is to Jeff Westbrook, one of the writers. He used to be at AT&T Labs, and is the only theoretician I know* who writes scripts for Hollywood. We even wrote a paper together, so I guess my Hollywood number is 1 !

---

* Len Adleman consulted on 'A Beautiful Mind' and I believe even "decorated" a blackboard for a scene in the movie.

Princeton math oral exams

Via Michael Nielsen, the Princeton Math Department Graduate Student Guide to Generals (their oral exams).

I found the following excerpt hilarious: this is the start of an orals transcript, with a commitee consisting of John Conway, Andrew Wiles, and Charles Fefferman (speakers are marked with lastname-firstletter:

C: "So who is the chair of this committee?"
F (scratching head): "I think it's one of you two."
W: "Is it me?"
C: "I don't know... Perhaps it's me."
W: "How will this be determined?"
F: "Does it matter??"
C: "Let me find out from the office downstairs."

(Just as he was about to leave, I informed Prof. Conway he was chair.
A similar discussion then ensued as to what my special topics were!!
It was quite entertaining. But at last, we were all ready to begin.)

C: "So who wants to ask the first question?"

(Everyone kept looking at Conway. (He was chair after all.) )

C: "Hey, why is everyone looking at me?!?"

(Another entertaining dispute followed.
Finally, Prof. Fefferman agreed to start.)

The Strong Law of Truly Misquoted Mathematics

On the one hand it is nice when technical terms from the world of math/CS sneak into common usage. On the other hand it can be rather grating. If I had a dime for every time someone used "exponential growth" to mean "something big", I could probably buy a single share of Google stock...

This excerpt from a Slate article on cell phone usage is another example:

...the cell-phone growth projections are based on premises that are more redolent of 1990s-era techno-enthusiasm than the current decade's putative realism. Some savvy observers of the telecom world detect the beginnings of a bubble. "At some point, we're going to run into the law of large numbers and it's going to be a nasty setup," said Cody Willard, general partner at CL Willard Capital and a columnist for TheStreet.com. "I just don't think we're quite there yet."

I have to ask: exactly what law is Mr. Willard scared of running into ? Let's consider the options:

The Weak Law of Large numbers:
The probability that the sum of i.i.d variables over the same distribution differs from the mean is arbitrarily small.


or even:
The Strong Law of Large NumbersNot only is the probability of deviation small, the actual deviation of the sum from the mean is arbitrarily small.


Somehow I don't see how either of these fit into an analysis of the global cell phone market. But wait!, there are some more intriguing possibilities.

The Frivolous Theorem Of ArithmeticAlmost all natural numbers are really large

Possible, but Mr. Willard did after all quote a law of large numbers. We should grant him at least some degree of precision in his statements.

Strong Law of Small NumbersThere aren't enough small numbers to meet the many demands made of them..

This seems somewhat more plausible: after all, soon we might run out of small numbers to describe cell phone usage, at which point the market might collapse.

But I think the real answer lies in a deeper analysis of his prognostication. Note if you will the use of the phrase 'nasty setup'. This clearly indicates his invocation of:

The Law of Truly Large NumbersWith a large enough sample, any outrageous thing is likely to happen

This indeed settles it. As cell phone usage increases, something bad is going to happen. Now we know why they get paid the big bucks in Wall Street.

Floating point arithmetic is not associative...

Especially in computational geometry, robust calculations are of paramount importance because of the algebraic calculations at the heart of most geometric algorithms, and the catastrophic effects of precision errors - you lose incidences, points disappear, algorithms crash, the universe slips into a black hole....

An old article by David Goldberg talks of the perils of floating point computations. Worth reading...
What Every Computer Scientist Should Know about Floating Point Arithmetic

Page Numbering Planar Graphs

In honor of the recently passed Graph Drawing deadline....

Suppose we place all the vertices of a graph on the spine of a book, and partition the edge set into sets such that each set can be drawn on a single page without crossings. The page number of a graph is the minimum number of pages required to draw a graph in this way. Clearly an outerplanar graph has page number 1.

A well known result by Yannakakis states that any planar graph can be drawn with page number 4, and this is necessary. A very interesting related result by Lenwood Heath in SODA 1991 states that the edges of a planar graph can be partitioned into two parts, each inducing an outer planar graph.

It is NP-hard to determine whether a given planar graph has page number 2 or not.

EVERYONE needs a Motivation section...

From Leonardo Da Vinci's serialized diaries:

When you put together the science of the motions of water, remember
to include under each proposition its application and use, in order
that this science may not be useless.--

Serialized books: a neat idea...

From BoingBoing, this link comes our way:

Matt Webb says:
I want to read the Notebooks, but there are 1,565 pages and I have too much else to read.

At a page a day it would take a little over four years, but be manageable.

Fortunately Project Gutenberg (who make freely available online out-of-copyright books) has created a text version of the Notebooks of Leonardo Da Vinci. You can download it. It lacks the illustrations of the original, but it's Good Enough.

Using this site, I can read one page a day using my RSS News Reader. Find an RSS News Reader. I started at page 1 on May 30th, 2004. I'm now on page 2. You can either read along with me, or start reading at page 1 today.


Get the RSS feeds here.

Coffee

Unattributed quote:
A mathematician is a machine for turning coffee into theorems

Paul Erdos, after going off coffee for a month:
You have set back the cause of mathematics for a month

And finally, Ziggy (and this will now be my unofficial logo):

A Nice Box Theorem

I was at Peter Winkler's last talk at Bell Labs before he leaves for Dartmouth.


TOURNAMENTS, BOXES AND NON-TRANSITIVE DICE

Many gymnasts compete in 2k-1 events, and are ranked in each with no ties. One competitor is deemed to have "beaten" another if she outscores the other in a majority of the events.
Afterward the organizers are embarrassed to discover that no matter how they award the prizes, there will always be a gymnast who didn't get a prize but beat every gymnast who did.
How many prizes should the organizers have had on hand to be sure this wouldn't happen?
(A meandering blackboard presentation based on recent work with N.Alon, G.Brightwell, H.Kierstead, and A.Kostochka.)

---

During this lecture he presented this gem, due to Imre Bárány and Jenö Lehel:

There exists a constant c = c(d) such that for any compact set S contained in R^d, there exists a subset A of S of size at most c such that S is contained in the union of "boxes" of pairs of points of A, where the box containing two points p and q is defined the smallest orthogonal box containing p and q.

A lower bound on c is doubly exponential in d (for d = 2, 4 points suffice).

---

Peter Winkler's talks are always beautiful this way; they start with a simple puzzle - something you could describe in a line or so - and then as the talk progresses, you realize the deeper and deeper levels of mathematics that are being used to solve the problem.

Rappamatics !

Courtesy of Aaron 'A-Dogg' Archer, some excerpts of PHAT Rappamatics....

U Can't Bound This
...
Cutting planes, by far
best found in a dimly lit bar
so flip, that coaster in the air {ADogg flips a coaster}
Call Bill Cook, run a comb through your hair
Now follow, the central path
Scale that data make your polytope phat
So make, your step-size large
Do this in practice, it's fast to converge.
[quadratic convergence]
...

Ramanujan's Revenge
....
I need a math transfusion.
My blood pressure's turnin' into fusion.
I've been racin' and pacin' ,
sweepin' the nation
'cuz mathematic lingo is what we're facin' .
Talkin' homomorphic, endomorphic, isomorphic, automorphic,
homotopic, isotopic, polytopic, can t stop it.
Every single theorem that I hold in my pocket
is BAD, too hot to handle.
I've got theorems that would cause a scandal.
Activated, iterated, integrated, combinated,
numerated, permutated, bifurcated, conjugated.
I can't stop, 'cuz the rhythm has got me.
Without math you re Mr. Softee,
and if you disagree that math is happenin' ,
I'll be on your butt like a contraction mappin' .
Down with MIP?
Yeah, you know me.
Down with MIP?
Yeah, you know me.
Down with MIP?
Yeah, you know me.
Who's down with MIP?
All the homies.

Word.

Zipf's Law and Log-Normal Distributions.

If you have ever done data analysis, you have probably bumped into the (in)famous Zipfian distributions, popularized by the "80-20" law:
80% of the work is done by 20% of the people
or
The probability of the i^th most frequent item is roughly i^-alpha

Michael Mitzenmacher has a nice survey (PS) outlining the history of such "power-law" distributions, the generative processes that create such distributions and their relationship to log-normal distributions (a distribution where the log of the variable is normally distributed). Worth a read...

Mathematicians don't understand math !!!

STOP THE PRESSES !

I feel the urge to fisk violently upon reading an article in today's NYT titled 'When Even Mathematicians Don't Understand the Math':
<.. deep breaths ...>

Here are some choice excerpts:

Asked if there exist mathematical concepts that defy explanation to a popular audience, Dr. Stewart, author of "Flatterland: Like Flatland, Only More So" replied: "Oh, yes - possibly most of them. I have never even dared to try to explain noncommutative geometry or the cohomology of sheaves, even though both are at least as important as, say, chaos theory or fractals."

I see. so this is news to the NYT that there are (perish the thought)mathematical ideas that cannot be explained to layman...

The Hodge conjecture deals not only with cohomology classes, a complicated group construct, but involves algebraic varieties, which Dr. Devlin describes as generalizations of geometric figures that really do not have any shape at all. "Those equations represent things that not only can we not visualize, we can't even imagine being able to visualize them," he said. "They are beyond visualization." This difficulty points to a math truism that ultimately framed his entire project.

"What the book was really saying was, 'You're not going to understand what this problem is about as a layperson, but neither will the experts,' '' he said, adding, "The story is that mathematics has reached a stage of such abstraction that many of its frontier problems cannot be understood even by the experts."

Well sure - an expert in sub area X may not always understand the terms in sub-area Y. Is this (a) surprising or (b) a BAD BAD thing ? Isn't this just the consequence of living in a rich and incredibly complex field ?


At the same time, higher math is used to decipher the existence and composition of the world. But how can it make sense that a nearly unintelligible language can explain the physical world?

There seems to be the unstated implication that a language unintelligible to the layman cannot be used to explain the world.. see below...


But if science writers described breakthroughs in genetics or zoology in terms of overarching aims and not concrete facts, readers would question the foundations of that field. That lay readers and scientists alike accept that they will never wrap their heads around much of higher math is evidence that it is a world unto itself.

But surely one can say the same thing about some of the denser theories of post-modern literary criticism, that it is incredibly hard for the layman, or even many literary theorists, to understand them. Is there some kind of subtle anti-intellectualism at work here - knowledge that is not accessible to the masses is not real knowledge ?

In fact, it is difficult to explain what math is, let alone what it says.
Sigh...two pages into the article, the writer figures it out...

"It isn't science," said Dr. John L. Casti, the author of "Five Golden Rules: Great Theories of 20th-Century Mathematics and Why They Matter." "Mathematics is an intellectual activity - at a linguistic level, you might say - whose output is very useful in the natural sciences. I think the criteria that mathematicians use for what constitutes good versus bad mathematics is much more close to that of a poet or a sculptor or a musician than it is to a chemist."

And just as one cannot define what it is that makes a moving phrase played on a violin moving, the essence of the superb equation may also be ineffable.

Finally something I can live with ;)...

Robot Origami

Computational geometers do origami.
Computational geometers do robotics.

And now, robots do origami:

"Our primary interest in origami is manipulation," Balkcom writes on his web page. "We are currently working on understanding more complicated origami skills - like reverse folding, squash folding, the rabbit ear, and prayer folding - that require the simultaneous manipulation of multiple non-colinear creases."

Summertime...

...is here, and that means summer students. When I was a grad student, getting a summer job always entailed negotiating that dreaded question 'Will you do programming', which to me was always a warning sign that the project would involve only programming.

Now that I am on the other side of the fence, I still dislike having students come over to do programming work; however, the reality is that one has to find projects that are interesting, have some kind of business motivation, and yet have a three month timeline. It is well nigh impossible to guarantee results in a theoretical project in any fixed time (or at least I have not learnt the art of this yet :)), so invariably summer projects tend to involve some kind of tool/system building so that one can demonstrate concrete progress in a short timespan.

The trick is to figure out a topic that is amenable to 'covert theory' that can lead to more satisfying long-term research. After all...

Before each summer is done
Their theorem will be unfurled
By the dawning of fall term
They'll take over the world... with algorithms !!


(with apologies to Pinky and the Brain)

Graph Drawing

The Graph Drawing deadline is fast approaching (May 31). It might seem strange to have an entire conference devoted to drawing graphs. However, this is a very valuable area; one would be surprised to see the number of situations in which one needs to visualize a large graph, and needs a good algorithm to do so.

There are many different approaches to drawing graphs; edges as straight lines or splines, or orthogonal chains, vertices as boxes or circles or points, faces as rectangles or orthogonal polygons. An interesting graph drawing result on planar graphs is Fary's theorem:

Any planar graph can be drawn with straight lines for edges and no crossings.

What makes the above result quite interesting is the following. Let a pseudoline arrangement be a collection of curves (each separating the plane into two parts) in which each pair intersects exactly once. Such a collection defines an arrangement of the plane (with faces, vertices and edges). Such an arrangement is stretchable if it is isomorphic to a straight line arrangement.

Not all pseudoline arrangements are stretchable. In fact, determining whether a given pseudoline arrangement is stretchable is NP-hard (due to Peter Shor).

Back from a trip...

Just back from vacation...while I get back up to speed, take a look at this

A bizarre fast growing function

Ackermann's function is a familar fast growing function to any of us who have studied the union-find data structure. Here is a sequence from Neil Sloane's Sequence Encyclopedia that has some intriguing growth properties.

---

Sequence A090822
a(1) = 1; for n>1, a(n) = largest integer k such that the word
a(1)a(2)...a(n-1) is of the form xy^k for words x and y
(where y has positive length), i.e. the maximal number of repeating
blocks at the end of the sequence so far.

---

The sequence goes 1,1,2,1,1,2,2,2,3,1,1,2,.....

The first time 4 occurs is at position 220, and the first time N occurs is
roughly near (2^(2^(3^(4^...(^N)))). It seems strange that such an
innocent-looking sequence has such bizarre behaviour.

For more on fast growing functions, definitely read Scott Aaronson's Busy Beaver article.

---

Update (7/20/2004): There is now a paper on this sequence proving that it is unbounded.

From the free market hall of shame....

McDonald's is allegedly trademarking the phrase "I am Asian"

Last time I checked, I was Asian too...

New Blog Style

Blogger underwent a massive makeover ('tis the season, isn't it), and I decided to reformat my blog. One good thing is that comments are now native to blogger, rather than being external...

Geometric Matching

Have been remiss in blogging activities for the past few days. Have been recovering from severe cat-shock :)

And now for something completely different, from the SoCG preview file...

---

A matching in a graph is a set of disjoint edges (i.e no two sharing an endpoint) connecting pairs of vertices, and a maximum matching is a matching of maximum size. A perfect matching is one in which every vertex is the endpoint of some edge in the matching, and a min-cost perfect matching is a perfect matching of minimum weight (when weights are associated with each edge).

In the geometric setting, nodes are points in the Euclidean plane, and edges are weighted by the (Euclidean) distance between the corresponding pair of points (in general, there is an edge between any two points). Computing a Euclidean matching pairs up vertices to minimize the sum of distance between these pairs. A red-blue matching is the geometric analogue of bipartite matching in graphs; match up red and blue vertices in pairs to minimize the total cost (= sum of distances).

In contrast with general graphs, a rather peculiar state of affairs has been the case with geometric matching. Namely, red-blue matching appeared harder to solve than the monochromatic variant. In fact, there is a linear time approximation algorithm due to Pankaj Agarwal and Kasturi Varadarajan for estimating a min-cost matching in the plane, but the best such algorithm for red-blue matching ran in time O(n^3/2).

Pankaj and Kasturi have a new result in the upcoming SoCG that improves matters significantly. Although a linear-time approximaton scheme for red-blue matching is still an open problem, they present an algorithm that computes an O(log(1/e))-approximation in time n^1+e.

A thought...

Continuing my reading of The Elegant Universe, I was struck by this passage, where the author describes entering grad school at the time when the first papers on string theory were about to be presented.

There was a pervasive feeling among the older graduate students that there was little or no future for particle physics.The standard model was in place and its remarkable success at predicting experimental outcomes indicated that its verification was merely a matter of time and details. Going beyond its limits to include gravity and possibly to explain the experimental input upon which it relies [... snip ...] was so daunting a task that all but the most courageous of physicists recoiled at the challenge. But six months later the mood had completely swung around


Makes me wonder if we are in the same holding pattern regarding the big problems like P != NP etc, solving all kinds of interesting problems, but staying away from the big Kahuna, waiting for the big breakthrough to happen....

On computer science and math

This article on lineman.net discusses the kind of math one needs for doing a computer science degree. I like this line, on what classes to take in high school.

If you have the chance at another course, go with geometry. Geometry will give you the opportunity to learn how to do proofs

Euclid would be proud....

Further discussion ensues on /.

SoCG Early Registration Deadline is May 1

More info here

Holes in sets

The annual sausage convention is nearing, and it's time to look at the coming attractions...

---

A "Ramsey theorem" says loosely that one can find a structured subset of any size in a larger set, as long as the set is large enough.
The usual example of this is that if you take 6 points, connect all pairs, and then color each edge with either red or blue, you will always get a monochromatic triangle.

Erdos and Szekeres proved one of the first "geometric" Ramsey theorems, that said:
Theorem. For any k, there exists an n = n(k) such that all planar point sets of size n(k) have a convex subset of size k.
This subset is independent, in that all points are on the convex hull of this set.

However, if you change the problem slightly, things start getting interesting. Suppose that instead of asking for a convex subset, you wanted an empty convex subset. In general, suppose you want a "k-hole": a hole bounded by k points. Then the above theorem breaks down. Specifically,

Theorem (Horton). There exist arbitrarily large finite point sets in the plane that do not contain a 7-hole.

But we also know:
Every sufficiently large point set in the plane contains a 5-hole.

Which leaves as a tantalizing open question: What about 6 ?

---

Pinchasi, Radoicic and Sharir have a paper that develops some key combinatorial equalities and inequalities around this question.

Update: k = 6 is resolved.

Books that read like a thriller...

Occasionally one finds technical books that, either because of the subject matter, or the style of writing, or some other inexplicable properties, make for such gripping reading that one almost wants to read from cover to cover in a single sitting.

Two such books that I have come across are Combinatorial Geometry, by Janos Pach and Pankaj Agarwal, and Jiri Matousek's Lectures on Discrete Geometry. These books overlap a little, but are largely disjoint in their coverage, and contain some of the true gems in computational geometry, like Helly's theorem and other theorems in convex geometry, the theory of epsilon-nets, a wealth of Erdos problems, and many many more.

I first read Combinatorial Geometry in grad school, and remember my advisor remarking that he couldn't put the book down. At that time I found the comment strange, and intriguing enough to look at the book. Five hours later, I knew what he meant...

We are lucky...

Having "come of age" in the Internet era, I consider myself rather fortunate. Till the crash of 2000, it was not hard to convince myself of the indispensability of computer science (and computer scientists) and the research job market reflected that. People who had been around longer used to talk about the early 1990s when CS research jobs were hard to come by and graduating Ph.Ds did postdocs as a matter of course to bide their time.

It seems a lot worse now, but compared to other professions, we are incredibly fortunate. This musing was prompted by an article from the Chronicle of Higher Education about the Invisible Adjunct, an anonymous adjunct in the humanities who wrote an eponymous and very popular blog. She just had to stop writing, having given up on her quest of finding a tenure-track position after having 'adjuncted' for five years.

An excerpt:
The Invisible Adjunct grew up in a working-class family in Canada. She put herself through college near home. That's where advisers first gave her the counsel she now tries not to hate them for: "You're too smart for law school," they told her. "You're one of us." And with that, she was off to an elite graduate school in the United States.

Five or so years later, she had a new doctorate in history and she waded into the job market. She managed to score a campus interview at an elite research university, but came in second. Given how small the world of academe is, she doesn't want to tell everyone where she almost landed. Let's just say you've all heard of it.

But in the five years since, after coming so close at one of the nation's top institutions, she has never been granted another campus interview at an American college, though she has applied all over. To be so close and then to disappear into the fog of adjunctdom makes the system seem all the more unfair.


There's an interesting related article at Crooked Timber about academic Calvinism (short summary: the worthy are rewarded with tenured jobs, and the unworthy go to Hell (or adjunctland).

---

Link via Brad DeLong

Discrete Spacetime ?

I've been reading Lee Smolin's 'Three Roads to Quantum Gravity' recently. For those of you who may not know about his work, Lee Smolin is a physicist working on efforts to unify quantum theory with general relativity. This book describes three paths to doing so, and is part of a new attempt to popularize some of the more radical theories on the cutting edge of physics (Brian Greene's 'Elegant Universe' is another). The March issue of Scientific American has a brief writeup on Smolin's work as well.

There is much that I don't understand in this book, and there are some fascinating and counter-intuitive ideas there. However, what intrigued me the most was this (from Chapter 8):

With matter there is a limit to how small we can divide something, for at some point we are left with individual atoms. Is the same true of space ? If we continue dividing, do we eventually come to a smallest unit of space, some smallest possible volume ? Or can we go on forever, dividing space into smaller and smaller bits, without ever having to stop ? All three of the roads I described in the Prologue favour the same answer to this question: that there is indeed a smallest unit of space. It is much smaller than an atom of matter, but nevertheless, [...snip...], there are good reasons to believe that the continuous appearance of space is as much an illusion as the smooth appearance of matter.


As he goes on to explain, it is not that good ol' Euclidean space is extra chunky; the notion of space itself breaks down at a certain level, giving rise to discrete graph-like structures. Now to a discrete geometer or a combinatorial person, the idea that our universe itself is discrete is a delicious idea. The idea of entropy (in the physical sense) has been related to entropy (in the information-theoretic sense) using such ideas.

Further, it begins to make me wonder about the Church-Turing thesis (well almost anything will, but that's a different story). One of the objections that has been raised regarding the universality of the Church-Turing thesis is the fact that Turing machines only operate on discrete entities, and have no way of dealing with real numbers. Now I am going way out on a limb here, but could a discrete universe make this a moot point ?

---

Update: I just picked up 'The Elegant Universe'. The key difference is in the approach each emphasizes: Greene stresses the importance of string theory, and Smolin, while discussing three different paths to quantum gravity, favors loop quantum graivity (both of these reflecting the authors' own expertise). As works of writing though, I have to say that I find 'The Elegant Universe' a bit more of a pleasant read. It feels like Smolin is struggling to hit the right metaphors to explain the theories he discusses (no fault of his - this is one of the deepest areas of science, after all)

Geometry and Combinatorics

Computational geometry deals with algorithms on geometric objects.
This is a statement that most computational geometry folks can agree on. It is also a statement that encapsulates the primary source of tension and profundity in this field, namely the interplay between the discrete (algorithms) and the continuous (geometry).

Algorithms take as input (and generate as output) discrete entities; at the most basic level strings of 0s and 1s. A geometric entity such as a line or point cannot always be represented so concisely. It would not be an exaggeration to say that it is this conflict that has inspired many of the techniques, theories, and areas of computational geometry.

The most immediate effect has been practical. As anyone who has tried to implement a geometric algorithm quickly realizes, issues of precision and robustness are not dry academic concerns when your convex hull starts looking like spaghetti ! Some wonderful work has come out of the problems in implementing geometric algorithms; robust computing, exact polynomial evaluation, how to determine the precision needed for a computation... In fact computational geometry has stood out among all algorithmic disciplines in its attention to issues of implementation.

There is a deeper level of interplay between the discrete and the continuous in geometric algorithms though. In a sense, some of the best theory in computational and combinatorial geometry has come from trying to abstract out a combinatorial structure that describes a geometric setting, and then using that combinatorial structure to prove a desired result. The trick has always been to take what is needed from the underlying geometry to construct an appropriate combinatorial space to work with.

Examples of this abound. Simple results on arrangements of lines can be proved merely by observing that the lines and their intersections can be represented as a planar graph. The Koebe-Andreev-Thurston theorem characterizes planar graphs in terms of contacts between circles.
Many theorems on arrangements use only incidence axioms, and thus are true in the projective plane, which in turn can be represented combinatorially.

What is so fascinating about this is that you can get deeper and deeper into the geometric structure, and new combinatorial structures keep emerging. If projective spaces give you a lower bound (and they often do), then it tells you that you need more than just incidence relationships. If you need to use convexity, then Helly's theorem (and Radon's theorem and others) gives you a nice way of handling convexity combinatorially. If combinatorial set systems defined on geometric objects are giving weak bounds, then VC-dimension arguments give you a way of capturing geometry in a combinatorial way.

The relationship goes both ways; planar graphs and interval graphs are but two examples of rich graph classes that are defined geometrically. Results in coding theory come from arguments about sphere packing. One of the great breakthroughs in complexity theory, Mulmuley's proof separating P and a slightly restricted variant of NC, uses geometric and topological methods.

Ultimately, this is what I enjoy about computational geometry; it provides a playground for rich algorithms, and the means to utilize tools from some of the deepest areas in mathematics. Truly, sitting in this mean is no mean pleasure.....

Deadlines:

Lance mentions some upcoming conference deadlines.

Some geometry-related activities:
The Canadian Conference on Computational Geometry (alas, no food-based acronym here): submission deadline is May 3.

Graph Drawing 2004: submission deadline is May 31

Infection: The Solution

And here it is: the solution to last week's problem:

Consider any configuration of infected cells. Calculate the length of the boundary of these cells (a single side being 1 unit long) and call it L.

L remains constant as more cells are infected



In the picture above, the blue lines mark the boundary of the infected region. Observe that when a new cell is infected, it destroys two boundary pieces (from the cells that infected it) and adds two (for its other two sides). Hence L remains constant. Since the boundary of the entire grid is of length 4n, and each infected cell can contribute at most 4 units to L, there must be at least n infected squares to start with.

---

Credit to Shankar Krishnan, and Rudolf Fleischer, who supplied a variant of this proof.

ACM Turing Award 2003 Goes To Alan Kay

ACM just announced the Turing Award for 2003. It goes to Alan Kay

For pioneering many of the ideas at the root of contemporary object-oriented programming languages, leading the team that developed Smalltalk, and for fundamental contributions to personal computing.

---

For those who don't know, the Turing Award is the most prestigious award in computer science and is awarded annually.

Ipe

Xfig is the drawing tool of choice for people writing papers that use the latex->dvi->ps pipeline. However, Xfig lacks a geometric sensibility; a way to draw incidences, tangencies etc precisely without having to rely on a steady hand.

Ipe is a tool first developed by Otfried Cheong that can handle such features. You can request that objects be snapped to boundaries of other objects, intersections, grid lines, etc. It is extensible (via Ipelets), and generates LaTeX for easy inclusion in files. This is a godsend especially when you have text and pictures interspersed in a drawing (Xfig can do this, but it is a little trickier and you don't really get WYSIWYG behaviour). Ipe also has plugins for computing Voronoi diagrams and Delaunay triangulations.

I've know about Ipe for a while but have been too lazy to change over; playing with it recently was encouraging, as the learning curve appears to be quite gentle.

---

thanks to Sariel

Interviewing

It is interview season at the labs, and a stream of candidates flows through our corridors. You can always tell who the candidate is by picking out the person in a suit (though that can occasionally be wrong at a corporate lab; thankfully I haven't yet accidentally asked my chairman which university he's interviewing from).

Taking the measure of a candidate is a tricky business in a research lab. Having come through the university system, I feel comfortable evaluating a candidate for a university position; one can look at letters, research interest, general drive and all kinds of parameters. In a research laboratory things can get a bit trickier. One wants the stellar academic credentials of course, but one also likes to see a certain kind of "renaissance" personality; the sense that the person you are interviewing is broader than the story their resume tells.

It is hard to determine this in our modern era of specialization. A candidate usually wants to show depth and expertise in an area, but it seems to me that one of the parameters for success in a lab is the ability to be flexible; to be able to take the skills one has and apply them both in one's own work, and when lending a hand in other projects. This calls for the ability to abstract, generalize and apply, rather than to specialize and drill down. I feel that in this respect at least, labs and universities differ, and this is a more interesting distinction between the two than the standard cliches about how much freedom of choice one has, how much business-oriented work one does, etc etc.

I wonder what kinds of questions can elicit whether or not a potential new hire has this kind of sensibility ?

WWW and WWB ?

It is interesting to see how the evolution of the blogosphere has paralleled the evolution of the WWW.

* Tim Berners-Lee and others (Dave Winer and others) develop hypertext link tools like HTML (RSS)
* People start creating web pages (blogs) frenetically in an initial growth spurt.
* Bookmark lists (blogrolls) become all the rage as people try to find more and more web pages (blogs)
* Meta-organizing entities (Yahoo/Kinja) start emerging, as a way to organize and classify the web (blogosphere)
* Google (Technorati) starts using link structure to determine "interesting" pages (blogs)
* Major organizations start creating web pages (RSS feeds) in response to user demand.

Based on this, one can expect the following to happen in the future:

* blogrolls, and the wonderful diversity of blogs, will start shrinking, at least in terms of hits (subscriptions). Prominent blogs will start drawing more and more of the traffic away from smaller ones.

* Audio/video content delivery mechanisms (the enclosure field in RSS is already an example of this) will start gaining importance (napblog anyone?)

* Media outlets will figure out a way to get advertising into blogs, in a more prominent way than currently exists. One example is to force you to clickthru an ad to read a full entry from a blog or a news feed.

What else ?

A meta-proof

inspired by pandagon: a meta-proof of P=/!=NP, coming to a newsgroup near you:

P: I would like to announce my proof of P=/!=NP. The proof is very short and demonstrates how to solve/not solve SAT in polynomial time. You may find a write up of the proof here.

|-- V: I started reading your proof and when you claim 'foobar' do you mean 'foobar' or 'phishbang' ?
|----P: I meant 'phishbang'. Thanks for pointing that out. An updated version is here.
|------V: Well if you meant 'phishbang' then statement "in this step we assume the feefum" is incorrect.
|--------P: No no, you don't understand. I can assume feefum because my algorithm has a glemish.
|-----------V: It has a glemish ? !! But having a glemish doesn't imply anything. All algorithms have glemishes !!
|----V': Yes, and in fact in the 3rd step of argument 4, your glemish contradicts the first propum.
|--V'': I think you need to understand some basic facts about complicity theory before you can go further. Here is a book to read.
|----P: My proof is quite clear, and I don't see why I have to explain it to you if you don't understand. I have spent a long time on this.
|------V': Um, this is a famous problem, and there are many false proofs, and so you do have to convince us that the argument using glemishes can actually work.
|--------P: But what is wrong in my proof ? I don't see any problems with it, and if you can't point one out, how can you say it is wrong.
|----------V'''': I don't have to read the entire proof: glemished algorithms are well known not to work.
|------------V'''''': Check out this reference by to see why.
P: <silence>
|--P: <answering earlier post>. This is what I mean by a glemish. it is really a flemish, not a glemish, which answers your objection.
|----P': Keep up the good work P. I tried publishing my result, and these people savaged my proof without even trying to identify a problem. All great mathematical progress has come from amateurs like us. See this link of all the theorems proved by non-experts.
|------V': Oh jeez, not P' again. I thought we had established that your proof was wrong.
|--------P': no you didn't: in fact I have a new version that explains the proof in such simple language even dumb&%&%s like you can get it.
|------P: Thanks P', I understand that there will be resistance from the community since I have proved what they thought to be so hard.
|--V': P, I'm trying to understand your proof, with the flemishes, and it seems that maybe there is a problem in step 517 with the brouhaha technique.
P: <silence>
|----P: V', thanks for pointing out that mistake. you are right. Instead of a brouhaha technique I need a slushpit. The details are complicated, so I will fix it and post a corrected version of the proof shortly. Thanks to all those who gave me constructive advice. I am glad that at least some of you have an open mind to accept new ideas.

---

This was prompted by the latest P=NP fiasco on comp.theory. I can only express my amazement and wonder at the few tireless souls (and they seem to be the same ones) who patiently try to address each new crackpot proof that comes down the pipe.

Problem 1: Infection.

People have suggested starting a problem of the day/week/month/ series. The problem of course is that once you start, you have to continue !
My compromise is that I will occasionally post interesting problems that come my way (and will take suggestions), with solutions a week later. No regularity in the supply of problems is guaranteed though.

So, to start, a problem that comes from the puzzle master, Peter Winkler (via Shankar Krishnan):

This is a Game of Life variant. Consider an n X n grid in the plane. Let a grid cell become infected if two of its neighbours are infected (diagonals are not included). The figure below illustrates how a cell can get infected.



Prove that in order for all the cells to become infected, at least n of the cells must have been infected to start with.

As with many of Peter's problems, there exists a Book proof. Your mission, should you choose to accept it, is to find it. Email me or post your solution in the comments. The first k people to get the right answer, (where k is a random number between 1 and 10), will be rewarded with their 10 bytes of blogosphere fame.

The Fafblog

WARNING: Non-geometry/algorithms/math post ahead...
There are all kinds of blogs on the net, but there is only one Fafblog.

For a take on the day's events that is so maniacally funny you wonder what the author is smoking....here's a sample, written after the Bush press conference

On our resolve:

It is strong.

Also it is resolute and firm. It is so firm! You have no idea how firm our resolve is. Whew! It's pretty firm I'll tell you that.

In addition to resolve we have resoluteness and strength. These are also very strong and resolute.

Also, freedom is beautiful. Look at those mountains! Smell that ocean air!

On the hideous bug invaders:

Reports regarding the hideous bug invaders have been greatly exaggerated and their laying of eggs in soldiers' brains is in no way to be perceived as a setback in the war against terror. Our resolve is so strong!

They have laid their eggs in far fewer soldiers' brains than the media is reporting. Man media there is something wrong with you!

Why from the looks of things on CNN you'd think theyd insectofied three whole platoons of soldiers by now which is crazy talk! Ha ha! Crazy talk, our resolve is strong!

---

and now back to previously scheduled geomblogging....

Theory and Practice

Straddling the theory + practice divide is always vexing, and I do this a lot when working at a research lab. The following note from an essay by Don Knuth is interesting:

The word 'theory' actually comes from the same root as the word 'theater'. .... the root word 'θέα' (a sight) led to (a place for viewing), (a spectator), and (a seeing, a spectacle).

And what about 'practice'. It's another Greek word, indeed another theatrical word: Practice means performance.
...
thus we can say that theory is to practice as rigor is to vigor.

-- from 'Theory and Practice II', in Selected papers in Computer Science

Knuth's point is not that theory is in any way subservient to practice: far from it. What he does argue is that theory far removed from practice becomes stale and ossified. His arguments, fleshed out over a series of articles, are more nuanced than I can do justice to in this note; suffice it to say that he wants to foster a far more active interaction between theory and practice than mathematicians (and theoretical computer scientists) are possibly comfortable with.

The essay ends with a beautiful bit of word play on the root word for theorem and the related root word for God:

Let us not confuse big-Omicron with big-Omega in making a theology out of theory. Let us rather practice what we preach. This will not only give the world better applications, it will ultimately give the world better theory.

The Abel Prize

I was not aware of this, but there is now a prize in mathematics that more closely resembles a Nobel prize. It is called the Abel Prize, (after Niels Henrik Abel) and has awarded prizes in 2003 and 2004.

From kuro5hin:

As is well known, there is no Nobel Prize in Mathematics. Instead, most people have looked to the Fields Medal as the most prestigious award for mathematical achievement. The Fields Medal, however, differs significantly from the Nobel Prize in that it is only awarded every four years (at each meeting of the International Congress of Mathematicians), to two, three or four recipients. Moreover, it is only awarded to mathematicians not older than 40, in order to encourage further achievements. This also has the pleasant side effect of rewarding recent work, rather than work done half a century earlier, as is too often the case with Nobel Prizes. Tellingly, both Atiyah (1966) and Serre (1954) have also won Fields Medals.

The Abel Prize, by contrast, seems to resemble the Nobel Prize more closely. It is awarded annually by a Scandinavian learned society (the Nobel Prize is awarded by the Swedish Academy of Sciences), it is worth a considerable amount of money, and so far all three recipients are over seventy years old. Happily, this allows rewarding those (relatively few) mathematicians who missed the Fields Medals due to their age.


This year's winners: Michael Attiyah and Isadore Singer for the discovery of the index theorem (explained here by John Rognes)

More Computer Science Poetry

Continuing the April Poetry Month theme, check out the poems written for Satish Rao's complexity class at Berkeley.

Here are some samples:

A set of problems,
Intractable or easy?
We may never know. -- Nemanja Isailovic

---

And this one from 'Wes', written to mimic an actual poem:

Bits in your multitudes
Scarce to be counted
We need but sample
A few random ones.
-CS 270, "Bits"

and the original:

Stars in your multitudes
Scarce to be counted
Filling the darkness
With order and light.
-Les Miserables, "Stars"

Mathematical Jabberwocky

April is National Poetry Month. In that spirit, I present this offering, courtesy of The Cyberiad, by Stanislaw Lem (translated by Michael Kandel).

The setting:
Trurl the constructor has created an electronic bard that can compose any poem. Klapaucius, Trurl's friend and co-constructor, requests

A love poem, lyrical, pastoral, and expressed in the language of pure mathematics. Tensor algebra mainly, with a little topology and higher calculus, if need be. But with feeling, you understand, and in the cybernetic spirit.

The result:

Come, let us hasten to a higher plane,
Where dyads tread the fairy fields of Venn,
Their indices bedecked from one to n,
Commingled in an endless Markov chain!

Come, every frustum longs to be a cone,
And every vector dreams of matrices.
Hark to the gentle gradient of the breeze:
It whispers of a more ergodic zone.

In Riemann, Hilbert or in Banach space
Let superscripts and subscripts go their ways.
Our asymptotes no longer out of phase,
We shall encounter, counting, face to face.

I'll grant thee random access to my heart,
Thou'lt tell me all the constants of thy love;
And so we two shall all love's lemmas prove,
And in our bound partition never part.

For what did Cauchy know, or Christoffel,
Or Fourier, or any Boole or Euler,
Wielding their compasses, their pens and rulers,
Of thy supernal sinusoidal spell?

Cancel me not -- for what then shall remain?
Abscissas, some mantissas, modules, modes,
A root or two, a torus and a node:
The inverse of my verse, a null domain.

Ellipse of bliss, converse, O lips divine!
The product of our scalars is defined!
Cyberiad draws nigh, and the skew mind
cuts capers like a happy haversine.

I see the eigenvalue in thine eye,
I hear the tender tensor in thy sigh.
Bernoulli would have been content to die,
Had he but known such a squared cosine 2 phi!


I hope this encourages you to read the book. The Cyberiad is an amazingly joyful playground of words and inventive notions, far different from much of the science fiction we see today.

arxiv.org RSS feeds

Hein Roehrig points out that arxiv.org now has their own RSS feeds for new papers. For example, the computational geometry feed is at http://arxiv.org/rss/cs.CG, and other feeds are generated in the same fashion, using the URL

http://arxiv.org/rss/<main-category>.<subcategory>

because Google is the source of all knowledge

I felt I had to create a page with this...

Jeff Erickson took me to task (and rightly so) for not starting the Geomblog with

The Sacred Sausage Invocation
Let P be a set of n points in the plane in general position. Amen.

Amen indeed.....

---

For those who don't get it, the primary conference in computational geometry is the Symposium on Computational Geometry, often called SoCG.

Kepler's Conjecture

It appears that the NYT story I referred to in a previous post may not have been entirely on the money in its description of the situation regarding the publication of Hales' proof. The matter will resolve itself soon hopefully....

Square Wheels

An interesting study of polygonal motions (article by Ivars Peterson on Sciencenews, found via Radio):

A square wheel can roll smoothly, keeping the axle moving in a straight line and at a constant velocity, if it travels over evenly spaced bumps of just the right shape. This special shape is called an inverted catenary.

A catenary is the curve describing a rope or chain hanging loosely between two supports. At first glance, it looks like a parabola. In fact, it corresponds to the graph of a function called the hyperbolic cosine. Turning the curve upside down gives you an inverted catenary.


This picture is too funny:
(credit: Stan Wagon)

Some interesting points:
* A triangular wheel cannot roll smoothly on any surface
* Is there a road-worthy combination of wheel and surface in which the wheel and surface have the same shape ?

Writing Papers

PhD is a hilarious comic strip on grad student life, especially in the engineering disciplines. I used to read it when I was a grad student at Stanford, and still find it spot-on in its depictions of life as a grunt in the trenches of science.

Here is the strip from Wednesday, April 05:

Kepler's Conjecture Theorem

Kepler's conjecture, one of the oldest conjectures in geometry, was that the optimal packing of unit spheres could never achieve a density of more than pi/sqrt{18}. A few years ago, Thomas Hales (with help from Samuel Ferguson), proved the conjecture with extensive use of computers to assist in the proof. The New York Times, in their infiinte wisdom, managed to greet this proof with a line that went something like 'Mathematicians have now proved what greengrocers have known all long' ....sigh...

What prompted this note is a new article (NYT; reg. reqd) that indicates that Thomas Hales' proof is going to be split into two parts:

But Dr. Hales's proof of the problem, known as the Kepler Conjecture, hinges on a complex series of computer calculations, too many and too tedious for mathematicians reviewing his paper to check by hand.

Believing it thus, at some level, requires faith that the computer performed the calculations flawlessly, without any programming bugs. For a field that trades in dispassionate logic and supposedly unambiguous truths and falsehoods, that is an uncomfortably gray in-between.

Because of the ambiguities, the journal, the prestigious Annals of Mathematics, has decided to publish only the theoretical parts of the proof, which have been checked in the traditional manner. A more specialized journal, Discrete and Computational Geometry, will publish the computer sections.


Now I don't quite trust the NYT when it comes to matters of science, but if this is true, it does send a rather unpleasant message, that the Annals of Mathematics is the place for rigorous proofs, and Discrete and Computational Geometry is the place for "computer-assisted proofs" (you can almost hear the sneer in that line). Now D&CG is the one of the primary journals of reference for work in computational geometry, and most of the papers published there are as theoretical as any. So I am somewhat puzzled at why this decision was made. If someone has more information to share, I'd like to hear more about it.

Submissions to Research Conferences

In computer science, the number of submissions to conferences has been increasing steadily over the past few years. There are many hypotheses attempting to explain this phenomenon, and as they are all completely unvalidated by real data, I will spare you the details.

However, in a pioneering and breathtakingly original piece of work, Cormode, Czumaj and Muthukrishnan have proposed a number of solutions to the problem of conference submission glut, as well as the problem of articially lowered conference acceptance ratios. The abstract:

In the beginning was the pub. This work was triggered by a pub conversation where the
authors observed that many resumes list acceptance ratios of conferences where their
papers appear, boasting the low acceptance ratio. The lower the ratio, better your paper
looks. The list might look equally impressive if one listed the rejection ratio of
conferences where ones paper was submitted and rejected. We decided to lampoon
rather than lament the effort the PC typically put in: wouldn’t the world be better if we
could encourage only high quality submissions and so run top conferences with very
high acceptance ratios? This paper captures our thoughts, and it is best consumed in a
pub (and in color).


Enjoy....

Funny Paper Titles

I collect paper titles that I consider to be "interesting". Research paper titles have gone the way of non-fictions books in recent years, with the use of the execrable A:B format, which can loosely be explained as:

A (Let's say something that we think is clever and pithy):B (maybe no one got the joke, so let's explain it in boring detail).

Consider this post a plea for help. Don't let the dark side lure you !!! There are many ways to title a paper cleverly (if you so choose to), without being sucked into A:B inanity. Here are some of the gems. All of the titles below refer to papers in (some area of) computer science. Warning: this is a highly idiosyncratic view; please don't complain if I list (or don't list) your title here. If you have contributions, post them in the comments or email me.

Short and sweet
Division is good
Reductions that Lie
T(A)=T(B)?

Funny
Mick gets some (the odds are on his side) (This one is particularly noteworthy, seeing as it mixes cultural references in)
O-O: What have they done to DB2
It's okay to be skinny, if your friends are fat.

Just Weird
Gray Visiting Motzkins
Cracking the cracking problem with coons patches
Pass the butter

And finally, a paper title that isn't yet, but should be !!

Searching for Spock in a Quantum Haystack

Erdos and proofs 'from the Book' (cont..)

Yesterday I talked about Erdos's beautiful idea of proofs from the Book, and mentioned an example problem whose proof could be viewed as being a 'Book proof'.
Here is the proof, (due to L. M. Kelly)

Theorem. There is no way to arrange n points in the plane (not on a line) so that a line through any two points will always pass through a third.

Proof:
Suppose the theorem is false. Let P be the given set of points, and let L be the set of all lines that pass through at least two points of P. Over all pairs (p, l) where p is in P and l is in L, and p does not lie on l, pick the pair (pp, ll) such that the distance from pp to ll is the smallest. By assumption, all lines pass thru at least three points, and so there are three points on ll, two of which (call them q1, q2) must lie on one side of the perpendicular from pp to ll.

Say q1 is closer to the perpendicular and q2 is further. Consider the pair (q1, lll), where lll is the line joining pp and q2. A simple drawing shows that q1 is closer to lll than pp is to ll, contradicting the minimality of the pair (pp,ll). Hence the theorem is proved.
end proof.

---

Bonus Points
You might notice that the above proof uses metric properties of the Euclidean plane (i.e the notion of distance), and order axioms (the notion of betweenness). It is possible to prove the above result without using metric properties (merely using order axioms), but it is not possible to drop the order axioms themselves. The reason is a topic for another note, on the limitations of combinatorics in geometry. Stay tuned....