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 /.