It would take too many books to even begin to describe the genius of Paul Erd�s; one such book is " The Man Who Loved Only Numbers: The Story of Paul Erd�s and the Search for Mathematical Truth" by Paul Hoffman.
Apart from his 1500+ research papers, Erd�s numbers (mine is 3!), and a dazzling array of problems in combinatorics, geometry, number theory, and countless other areas, Erd�s also bequeathed to us the beautiful notion of a 'proof from the Book'.
If I see a really nice proof, I say it comes straight from the Book . . . God has a transfinite Book, which contains all theorems and their best proofs, and if He is well intentioned toward those [mathematicians], He shows them the Book for a moment. And you wouldn't even have to believe in God, but you must believe that the Book exists.
(A. Soifer, Mathematics Competitions, vol.4, I, 1991, p.63) (via this link)
The idea of beauty in mathematics is something any mathematician understands intuitively. Although to a layman, the process of proving a theorem may seem mechanical (A => B, B=> C), to a mathematician, the elegance of a proof is sometimes as valuable as the proof itself. Like any aesthetic notion, elegance is hard to define; it lies in the eyes (or in this case the mind's eye) of the beholder. Erd�s 's idea of a 'Book proof' is a poetic way of describing a proof that is elegant, surprising, and hard to achieve.
Here is an example of one such proof, of the Sylvester-Gallai Theorem, taken from the book 'Proofs from THE BOOK' by Aigner and Ziegler:
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.
I will post the proof tomorrow; till then, keep your brain open !
Wednesday, March 31, 2004
Tuesday, March 30, 2004
Hyperbolic Geometry And Graph Visualization
Just attended a talk (our regular Tuesday "cookie talk") on hyperbolic geometry for graph visualization, by Paul Burchard.
One of the problems that has plagued people who draw graphs is the fact that Euclidean spaces are not ideally suited for representing graphs. First of all, if your graph isn't planar, you have crossings of various kinds, and then if the graph has lots of edges, drawing the interconnects can make rendering a nightmare.
An approach proposed by Munzner and Burchard suggests the use of hyperbolic geometry to render graphs, instead of Euclidean geometry. Hyperbolic spaces drop the parallel postulate, replacing it by the following:
For any infinite straight line L and any point P not on it, there are many other infinitely extending straight lines that pass through P and which do not intersect L.
-- From MathWorld
This has many consequences, among them the fact that the sum of angles of a triangle is no longer 180 degrees (it is less). An interesting metric property is now that the circumference of a circle of "radius" R has length roughly e^R, instead of R for Euclidean spaces.
What this implies is that there is "more space" in a hyperbolic geometry to represents points that are not too far away from you. A graph may have many points close to it (an exponential number in many cases), and so a hyperbolic space provides the real estate needed to render such graphs.
There are numerous references on hyperbolic geometry on the web (and many applets that explain what it means to draw a line, triangle, circle etc in hyperbolic space). The Geometry Junkyard has a good collection.
An interesting question is: can we embed an arbitrary metric space in a hyperbolic space with no distortion in edge lengths ? the exponential blowup in the volume of a ball seems to suggest that this is possible....
One of the problems that has plagued people who draw graphs is the fact that Euclidean spaces are not ideally suited for representing graphs. First of all, if your graph isn't planar, you have crossings of various kinds, and then if the graph has lots of edges, drawing the interconnects can make rendering a nightmare.
An approach proposed by Munzner and Burchard suggests the use of hyperbolic geometry to render graphs, instead of Euclidean geometry. Hyperbolic spaces drop the parallel postulate, replacing it by the following:
For any infinite straight line L and any point P not on it, there are many other infinitely extending straight lines that pass through P and which do not intersect L.
-- From MathWorld
This has many consequences, among them the fact that the sum of angles of a triangle is no longer 180 degrees (it is less). An interesting metric property is now that the circumference of a circle of "radius" R has length roughly e^R, instead of R for Euclidean spaces.
What this implies is that there is "more space" in a hyperbolic geometry to represents points that are not too far away from you. A graph may have many points close to it (an exponential number in many cases), and so a hyperbolic space provides the real estate needed to render such graphs.
There are numerous references on hyperbolic geometry on the web (and many applets that explain what it means to draw a line, triangle, circle etc in hyperbolic space). The Geometry Junkyard has a good collection.
An interesting question is: can we embed an arbitrary metric space in a hyperbolic space with no distortion in edge lengths ? the exponential blowup in the volume of a ball seems to suggest that this is possible....
Friday, March 26, 2004
Teaching High School Physics
Lance Fortnow recently posted a note on teaching evolution in which he said:
We should fight these attempts but we need to do so in a careful manner. Scientists should not impose the truth on school-age children, that will make us no better than the creationists who wish to impose their version of the truth. Instead we need to explain the reasoning behind evolution, the same holds for any scientific principle we teach. For example, I can't expect students to trust me when it comes to the Church-Turing thesis but instead I need to lay out a careful argument why the thesis must hold.
One should not force students to accept evolution, rather lay out the arguments and let the students learn to believe evolution on their own. Only then will they become true believers.
In a comment to this post, I replied:
On the other hand, we teach school-age children Newtonian physics without laying out a careful argument why the thesis must hold.
...[other unrelated stuff]
to which he responded, after talking to an Indian grad student of his:
This caught me as strange so I asked one of our Indian graduate students how he learned physics in school. He said they were given the appropriate theory and formulas. I asked if they did experiments. He said they were given descriptions of experiments on exams and had to predict the outcome but they never actually performed any experiments.
This is in sharp contrast to my high school physics class in New Jersey...
[...snip...]
Which teaching method is superior? In India they can go into more depth in the theory since they don't spend time on experiments. However I don't think you truly get an understanding for a scientific principle without getting your hands dirty.
I was going to comment on his blog, but I felt a longer response was apropos:
First of all, the impression that my post (and lance's interpretation of it) gives, that in Indian schools one doesn't do experiments, is completely false. I have had my teachers practically burn their clothes with demonstrations of hygroscopic activity (and the reactivity of sodium), and I remember long painful hours in physics labs wondering why the value of g was not coming out to 9.8 m/s^2 in my experimental setup. Also, I am likely to get into trouble with my mother for even implying that all indian schools teach is theory: she spends much of her time as a middle school science teacher designing practical activities that demonstrate scientific principles !
My point (possibly mis-stated) was that evolution is a phenomenon that happens over very large time scales, at least the effects that are being challenged by the ID folks. It is not hard to set up a petri dish and the right conditions to see bacteria evolving. However, from what I understand of ID theory, they don't argue about the simple evolutionary behaviour you can see here. What they argue about are the large jumps in complexity: formation of an eye being one example that was bandied about.
Now you can set up a lot of petri dishes, but you are not going to get bacteria with eyes any time soon. The same problem comes up with quantum computing. You can perform a diffraction experiment to get some inkling of the wave/particle duality of light, but it is quite hard to conduct experiments that really test the theory well; one has to read about the experiments rather than "do them" (again, I am speaking in the context of high school).
One of the hallmarks of science is the right to question a claim and demand reproducible results. We should definitely encourage that at every level of scientific education. But we have to be willing to be objectively biased i.e assert (current and temporary) superiority of a theory based on the weight of evidence; otherwise education can be reduced to post-modern "We report; you decide" media buffoonery.
We should fight these attempts but we need to do so in a careful manner. Scientists should not impose the truth on school-age children, that will make us no better than the creationists who wish to impose their version of the truth. Instead we need to explain the reasoning behind evolution, the same holds for any scientific principle we teach. For example, I can't expect students to trust me when it comes to the Church-Turing thesis but instead I need to lay out a careful argument why the thesis must hold.
One should not force students to accept evolution, rather lay out the arguments and let the students learn to believe evolution on their own. Only then will they become true believers.
In a comment to this post, I replied:
On the other hand, we teach school-age children Newtonian physics without laying out a careful argument why the thesis must hold.
...[other unrelated stuff]
to which he responded, after talking to an Indian grad student of his:
This caught me as strange so I asked one of our Indian graduate students how he learned physics in school. He said they were given the appropriate theory and formulas. I asked if they did experiments. He said they were given descriptions of experiments on exams and had to predict the outcome but they never actually performed any experiments.
This is in sharp contrast to my high school physics class in New Jersey...
[...snip...]
Which teaching method is superior? In India they can go into more depth in the theory since they don't spend time on experiments. However I don't think you truly get an understanding for a scientific principle without getting your hands dirty.
I was going to comment on his blog, but I felt a longer response was apropos:
First of all, the impression that my post (and lance's interpretation of it) gives, that in Indian schools one doesn't do experiments, is completely false. I have had my teachers practically burn their clothes with demonstrations of hygroscopic activity (and the reactivity of sodium), and I remember long painful hours in physics labs wondering why the value of g was not coming out to 9.8 m/s^2 in my experimental setup. Also, I am likely to get into trouble with my mother for even implying that all indian schools teach is theory: she spends much of her time as a middle school science teacher designing practical activities that demonstrate scientific principles !
My point (possibly mis-stated) was that evolution is a phenomenon that happens over very large time scales, at least the effects that are being challenged by the ID folks. It is not hard to set up a petri dish and the right conditions to see bacteria evolving. However, from what I understand of ID theory, they don't argue about the simple evolutionary behaviour you can see here. What they argue about are the large jumps in complexity: formation of an eye being one example that was bandied about.
Now you can set up a lot of petri dishes, but you are not going to get bacteria with eyes any time soon. The same problem comes up with quantum computing. You can perform a diffraction experiment to get some inkling of the wave/particle duality of light, but it is quite hard to conduct experiments that really test the theory well; one has to read about the experiments rather than "do them" (again, I am speaking in the context of high school).
One of the hallmarks of science is the right to question a claim and demand reproducible results. We should definitely encourage that at every level of scientific education. But we have to be willing to be objectively biased i.e assert (current and temporary) superiority of a theory based on the weight of evidence; otherwise education can be reduced to post-modern "We report; you decide" media buffoonery.
Thursday, March 25, 2004
On the definition of computing:
From an unsolicited resume sent to a colleague:
Expertise: Cryptanalysis
Computing skills: Microsoft Word
sigh.....
Expertise: Cryptanalysis
Computing skills: Microsoft Word
sigh.....
Wednesday, March 24, 2004
The Panda's Thumb
I try to spare readers (readers ? any readers ? anyone out there ? Hello ? ..) my political blatherings, because anyone can talk about politics. However, I would be remiss if I didn't make a note of the latest pathetic firebomb thrown by the (un)intelligent design bozos.
It started with a review in the Harvard Law Review of "Law, Darwinism, and Public Education: The Establishment Clause and the Challenge of Intelligent Design" by Francis Beckwith. The book itself (which I have not read) appears to make a legal case for the teaching of (un)intelligent design in schools and why this does not conflict with the Establishment Clause of the U.S. Constitution.
The review is somewhat mindless, in that "nonscientist tries to make sense of science" kind of way, but generated a rather violent screed from Brian Leiter, a law prof at UT Austin. More mayhem ensured, and the National Review Online came out with fists flying, and life was good (see Kevin Drum for a nice survey of this soap opera).
The good thing that came out of it, and the real point of this post, is the creation of a blog devoted to the defense of evolution against barbarians, cretins, and mindless government legislatures. Visit The Panda's Thumb ! Mention it to your friends !
Update: I was at The Panda's Thumb just now, and read this:
...it should be noted that the formation of this blog was not inspired by this incident at all. It is a mere coincidence that one followed on the heels of another, though I'm quite certain that some of our friends from the Discovery Institute could put together a compelling Argument from Really Big Numbers showing the staggering implausibility of those two things occuring in that specific order by random chance alone.
It started with a review in the Harvard Law Review of "Law, Darwinism, and Public Education: The Establishment Clause and the Challenge of Intelligent Design" by Francis Beckwith. The book itself (which I have not read) appears to make a legal case for the teaching of (un)intelligent design in schools and why this does not conflict with the Establishment Clause of the U.S. Constitution.
The review is somewhat mindless, in that "nonscientist tries to make sense of science" kind of way, but generated a rather violent screed from Brian Leiter, a law prof at UT Austin. More mayhem ensured, and the National Review Online came out with fists flying, and life was good (see Kevin Drum for a nice survey of this soap opera).
The good thing that came out of it, and the real point of this post, is the creation of a blog devoted to the defense of evolution against barbarians, cretins, and mindless government legislatures. Visit The Panda's Thumb ! Mention it to your friends !
Update: I was at The Panda's Thumb just now, and read this:
...it should be noted that the formation of this blog was not inspired by this incident at all. It is a mere coincidence that one followed on the heels of another, though I'm quite certain that some of our friends from the Discovery Institute could put together a compelling Argument from Really Big Numbers showing the staggering implausibility of those two things occuring in that specific order by random chance alone.
The Turnpike Problem
We take freeway exits for granted: I have often wondered what would happen if we had to do our regular commutes without the benefit of the huge green signs announcing breathlessly that our exit is 1 mile ....1/2 mile.... 1/4 mile... 500 FEET away.
Suppose it got even worse: not only do we not have exit signs, we don't even know quite where the exits are - sort of like platform 9 3/4 at King's Cross. However mercifully (or sadistically, depending on your point of view), someone supplied us with distances between pairs of exits. Formally, we are given numbers x1, x2, ...x(N * (N-1)/2) and must determine the exits P1, P2, .... PN that yield these inter-exit distances.
Reconstructing the locations of the exits is called The Turnpike Problem. A Google search yields lots of information on this topic: in fact the first link is:
Turnpike not the problem; traffic is
Oh well, never mind....
At any rate, this problem is surprisingly nasty. It occupies the limbo zone between NP-Complete and P, in the company of Graph Isomorphism and Factoring (they used to have a bridge foursome before Primes departed for P-land). It can be reduced to factoring an appropriately chosen polynomial, and so proving it NP-hard would be extremely interesting.
Turnpike reconstruction also comes up in X-ray crystallography and DNA reconstruction. Skiena, Smith and Lemke discuss this problem in some detail and present a backtracking method for solving it.
A Variant: I just saw this on comp.theory:
Suppose that instead of providing the difference between pairs of exits, we were given the sums. Does the problem change significantly ?
Suppose it got even worse: not only do we not have exit signs, we don't even know quite where the exits are - sort of like platform 9 3/4 at King's Cross. However mercifully (or sadistically, depending on your point of view), someone supplied us with distances between pairs of exits. Formally, we are given numbers x1, x2, ...x(N * (N-1)/2) and must determine the exits P1, P2, .... PN that yield these inter-exit distances.
Reconstructing the locations of the exits is called The Turnpike Problem. A Google search yields lots of information on this topic: in fact the first link is:
Oh well, never mind....
At any rate, this problem is surprisingly nasty. It occupies the limbo zone between NP-Complete and P, in the company of Graph Isomorphism and Factoring (they used to have a bridge foursome before Primes departed for P-land). It can be reduced to factoring an appropriately chosen polynomial, and so proving it NP-hard would be extremely interesting.
Turnpike reconstruction also comes up in X-ray crystallography and DNA reconstruction. Skiena, Smith and Lemke discuss this problem in some detail and present a backtracking method for solving it.
A Variant: I just saw this on comp.theory:
Suppose that instead of providing the difference between pairs of exits, we were given the sums. Does the problem change significantly ?
Monday, March 22, 2004
compgeom mailing list
The compgeom mailling list is a good way to keep in touch with announcements and events in the field. People also post requests for help with problems, references etc.
List archives are maintained by Sariel Har-Peled.
List archives are maintained by Sariel Har-Peled.
Saturday, March 20, 2004
Scientists and Poets
i wanted to throw this in yesterday, in the faint hope of having some deep thought to sign off for the weekend with:
I was reading an article yesterday about the perceived schism between poetry and science. The author went into some depth to argue that the disconnect was not as deep as one may think: some examples that he cited were Goethe, Shelley, and Byron.
He also discussed in some length Mary Shelley's Frankenstein, and one line caught my eye:
The basic lesson Frankenstein can teach us is this: science can tell us how to do something, but it cannot tell us whether we should do it.
It struck me that this fairly common meme confuses to a degree basic science and "applied" science or engineering. Scientists, at the most basic level, tell us what is, as well as how. In their description of the (physical) world, they are as much helpless prisoners of a Platonic reality (quantum physics, relativaity, what have you) as artists are bound by our own humanness. Humanity permeates all that we do, including science, and it is the evil within us that makes scientific tools dangerous, as dangerous as the kinds of powerful rhetoric that have killed as many people (if not more) than the atom bomb. We don't blame Karl Marx for the evils of communism, or the writers of the Bible for the Crusades; why is it so easy to blame the scientists ?
Another poet said it well:
The evil that men do lives after them;The good is oft interred with their bones.
To end on a more cheery note, let it not be said that mathematicians lack a poetic streak. Below I reproduce in full the famous poem by Soddy that answers the question: when can 4 circles be made to mutually touch each other ?
The Kiss Precise
by Frederick Soddy
For pairs of lips to kiss maybe
Involves no trigonometry.
'Tis not so when four circles kiss
Each one the other three.
To bring this off the four must be
As three in one or one in three.
If one in three, beyond a doubt
Each gets three kisses from without.
If three in one, then is that one
Thrice kissed internally.
Four circles to the kissing come.
The smaller are the benter.
The bend is just the inverse of
The distance form the center.
Though their intrigue left Euclid dumb
There's now no need for rule of thumb.
Since zero bend's a dead straight line
And concave bends have minus sign,
The sum of the squares of all four bends
Is half the square of their sum.
To spy out spherical affairs
An oscular surveyor
Might find the task laborious,
The sphere is much the gayer,
And now besides the pair of pairs
A fifth sphere in the kissing shares.
Yet, signs and zero as before,
For each to kiss the other four
The square of the sum of all five bends
Is thrice the sum of their squares.
In Nature, June 20, 1936
I was reading an article yesterday about the perceived schism between poetry and science. The author went into some depth to argue that the disconnect was not as deep as one may think: some examples that he cited were Goethe, Shelley, and Byron.
He also discussed in some length Mary Shelley's Frankenstein, and one line caught my eye:
The basic lesson Frankenstein can teach us is this: science can tell us how to do something, but it cannot tell us whether we should do it.
It struck me that this fairly common meme confuses to a degree basic science and "applied" science or engineering. Scientists, at the most basic level, tell us what is, as well as how. In their description of the (physical) world, they are as much helpless prisoners of a Platonic reality (quantum physics, relativaity, what have you) as artists are bound by our own humanness. Humanity permeates all that we do, including science, and it is the evil within us that makes scientific tools dangerous, as dangerous as the kinds of powerful rhetoric that have killed as many people (if not more) than the atom bomb. We don't blame Karl Marx for the evils of communism, or the writers of the Bible for the Crusades; why is it so easy to blame the scientists ?
Another poet said it well:
The evil that men do lives after them;The good is oft interred with their bones.
To end on a more cheery note, let it not be said that mathematicians lack a poetic streak. Below I reproduce in full the famous poem by Soddy that answers the question: when can 4 circles be made to mutually touch each other ?
The Kiss Precise
by Frederick Soddy
For pairs of lips to kiss maybe
Involves no trigonometry.
'Tis not so when four circles kiss
Each one the other three.
To bring this off the four must be
As three in one or one in three.
If one in three, beyond a doubt
Each gets three kisses from without.
If three in one, then is that one
Thrice kissed internally.
Four circles to the kissing come.
The smaller are the benter.
The bend is just the inverse of
The distance form the center.
Though their intrigue left Euclid dumb
There's now no need for rule of thumb.
Since zero bend's a dead straight line
And concave bends have minus sign,
The sum of the squares of all four bends
Is half the square of their sum.
To spy out spherical affairs
An oscular surveyor
Might find the task laborious,
The sphere is much the gayer,
And now besides the pair of pairs
A fifth sphere in the kissing shares.
Yet, signs and zero as before,
For each to kiss the other four
The square of the sum of all five bends
Is thrice the sum of their squares.
In Nature, June 20, 1936
Wednesday, March 17, 2004
The Paths of the Planets
Calculus is a heavy hammer, and can be used to solve many problems. Sometimes, a much more elegant solution to a problem can be found using basic geometric techniques.
One such example is Kepler's observations of the nature of planetary motion. Although Kepler's observations were accurate, it was not apparent why the planets should behave the way they did. Newton proved using calculus and his laws of motion that the orbits of planets are elliptical and that they sweep out equal areas in fixed time periods. However, he also showed this using nothing but the laws of motion and plane geometry, presumably so as to convince an audience that might be skeptical of calculus.
Richard Feynman rederived Newton's method and presented it a lecture that is now part of a collection called Feynman's Lost Lectures. Nigel Higson and Rachel Hall at Penn State included this as part of coursework they developed for an honors calculus class.
The technique itself can be found here. It is a beautiful use of plane geometry, one among many such examples of the power of elementary geometric reasoning (let us not forget that the first theorems were geometric proofs)
One such example is Kepler's observations of the nature of planetary motion. Although Kepler's observations were accurate, it was not apparent why the planets should behave the way they did. Newton proved using calculus and his laws of motion that the orbits of planets are elliptical and that they sweep out equal areas in fixed time periods. However, he also showed this using nothing but the laws of motion and plane geometry, presumably so as to convince an audience that might be skeptical of calculus.
Richard Feynman rederived Newton's method and presented it a lecture that is now part of a collection called Feynman's Lost Lectures. Nigel Higson and Rachel Hall at Penn State included this as part of coursework they developed for an honors calculus class.
The technique itself can be found here. It is a beautiful use of plane geometry, one among many such examples of the power of elementary geometric reasoning (let us not forget that the first theorems were geometric proofs)
Tuesday, March 16, 2004
The sweetest smelling junkyard...
...that you'll ever find.
From time to time, I am called upon (usually by people I have met for the first time), to answer the burning question
'But what is computational geometry used for' ?
David Eppstein has put together an extremely comprehensive set of pages titled 'Geometry in Action' that illustrate the many ways in which computational geometry seeps into the world at large. WARNING: read too many of these pages and you will start seeing Voronoi diagrams in challah bread.
David also has a page titled 'The Geometry Junkyard' which contains an eclectic collection of material related to discrete and computational geometry. Great to rummage thru...
From time to time, I am called upon (usually by people I have met for the first time), to answer the burning question
'But what is computational geometry used for' ?
David Eppstein has put together an extremely comprehensive set of pages titled 'Geometry in Action' that illustrate the many ways in which computational geometry seeps into the world at large. WARNING: read too many of these pages and you will start seeing Voronoi diagrams in challah bread.
David also has a page titled 'The Geometry Junkyard' which contains an eclectic collection of material related to discrete and computational geometry. Great to rummage thru...
Monday, March 15, 2004
PubMed and www.arxiv.org
I just received an update of articles posted to the cs arxiv at www.arxiv.org. For those of you who use blog readers for everything, Hein Roehrig maintains RSS feeds of most (if not all) of the topic areas maintained at the archive. Yet another email that I can eliminate from my mailbox; more time to read spam ;)
This spurred a thought that has been tickling me for some time now. Why is it that we in CS don't have a comprehensive archive of all papers published in the field ? INSPEC has often been the database search engine of choice, but it is usually accessible only from non-web-based interfaces, and is (in my opinion) secondary to google/citeseer searches nowadays. However, it has often happened that because I didn't look at the right sources or ask the right people, I missed a reference that would have been useful in my work.
Now if any of you have ever visited PubMed, you know that this is an incredible resource for biologists. Every paper from every journal (as far as I know) has a PubMed entry with an abstract, and can be searched for. There are also links to the actual document (usually via the journal web site). Biologists publish an awful lot of papers; when I was doing computational biology work every week there would be new papers that I'd have to track down and read, and having a resource like PubMed gave me the perfect one-stop-shoppping experience.
Math has MathSciNet, and physics (possibly parts of it) seems to have adjusted very well to the e-print server model. Why not CS ? One problem in my view is that the success of arxiv.org depends on people voluntarily submitting their papers. For PubMed (and possibly MathSciNet), this is done automatically (or via a third party) whenever new papers are published.
p.s Lance Fortnow has a hilarious description (with pictures) of how a Ph.D defense in Amsterdam is conducted.
This spurred a thought that has been tickling me for some time now. Why is it that we in CS don't have a comprehensive archive of all papers published in the field ? INSPEC has often been the database search engine of choice, but it is usually accessible only from non-web-based interfaces, and is (in my opinion) secondary to google/citeseer searches nowadays. However, it has often happened that because I didn't look at the right sources or ask the right people, I missed a reference that would have been useful in my work.
Now if any of you have ever visited PubMed, you know that this is an incredible resource for biologists. Every paper from every journal (as far as I know) has a PubMed entry with an abstract, and can be searched for. There are also links to the actual document (usually via the journal web site). Biologists publish an awful lot of papers; when I was doing computational biology work every week there would be new papers that I'd have to track down and read, and having a resource like PubMed gave me the perfect one-stop-shoppping experience.
Math has MathSciNet, and physics (possibly parts of it) seems to have adjusted very well to the e-print server model. Why not CS ? One problem in my view is that the success of arxiv.org depends on people voluntarily submitting their papers. For PubMed (and possibly MathSciNet), this is done automatically (or via a third party) whenever new papers are published.
p.s Lance Fortnow has a hilarious description (with pictures) of how a Ph.D defense in Amsterdam is conducted.
3SUM
Anyone who tries solving any interesting computational problem soon has to stare the NP-hardness ogre in the face.
Although proving a problem NP-hard can direct one's energies in the right direction (get an approximation, solve a special case), it can often be a nuisance.
One of the nice things about geometry is that (along with string matching and data structures), it is a rich source of problems which are in P i.e the problem can be solved in polynomial time. Some of the coolest algorithmic techniques come from geometry; getting an algorithm to run in time that is subquadratic in the input size can force one to delve into fairly hairy tricks.
But what if one is stuck ? There are many problems for which it seems extremely difficult to break the n2 bound. This is where 3SUM comes in:
Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0?
A simple enough problem, and you can solve it in quadratic time. Not much is know about whether one can do any better. What makes this problem useful is that it can be used a proof of hardness for many other problems, much like we use one NP-hard problem to show another one NP-hard.
If you want to suggest that your favorite problem can't be solved in subquadratic time, reduce 3SUM to it i..e show that if you can solve this problem, you can also solve 3SUM. Voila, you can dump your problem on the ever more burdened back of 3SUM, and walk away a free geometer :)
More details on 3SUM here. It's a wiki page, so edit it if you have a problem that is known to be 3SUM-hard
Although proving a problem NP-hard can direct one's energies in the right direction (get an approximation, solve a special case), it can often be a nuisance.
One of the nice things about geometry is that (along with string matching and data structures), it is a rich source of problems which are in P i.e the problem can be solved in polynomial time. Some of the coolest algorithmic techniques come from geometry; getting an algorithm to run in time that is subquadratic in the input size can force one to delve into fairly hairy tricks.
But what if one is stuck ? There are many problems for which it seems extremely difficult to break the n2 bound. This is where 3SUM comes in:
Given a set S of n integers, are there elements a, b, c in S such that a + b + c = 0?
A simple enough problem, and you can solve it in quadratic time. Not much is know about whether one can do any better. What makes this problem useful is that it can be used a proof of hardness for many other problems, much like we use one NP-hard problem to show another one NP-hard.
If you want to suggest that your favorite problem can't be solved in subquadratic time, reduce 3SUM to it i..e show that if you can solve this problem, you can also solve 3SUM. Voila, you can dump your problem on the ever more burdened back of 3SUM, and walk away a free geometer :)
More details on 3SUM here. It's a wiki page, so edit it if you have a problem that is known to be 3SUM-hard
Friday, March 12, 2004
Open problems (continued...)
Karen asks:
I wonder whether the ability to pick out interesting problems is innate or can be taught. What do you think?
I really am not sure. A professor I used to know said that taste in problems is something that can't be taught. I am not sure I agree with that completely though. I think that in grad school it is possible to train people to ask why a question should be considered interest. In fact one might argue that asking the right questions is the core of good research.
Every field has the foundational issues that drive them. In theoretical computer science, and computational geometry, one of the key issues is often: What is the key process underlying the structure of a problem, and how can this be used to solve it ? A paper that can answer this question will more often than not be deemed interesting.
So it is important to understand what the raison d'etre of your chosen field is. This is usually never stated explicitly, but there is usually a tacit broad consensus on what it is, and this is where an advisor, and good training, can help a lot.
Beyond that though, it is probably not a good idea to worry too much about what is interesting. A vibrant research field is a mosaic that comes from individual contributions in many different directions. It would be boring if everyone did the same thing. One should be willing to take the effort to sell one's contributions though, and not stand on ceremony waiting for others to realize what pearls of wisdom you have placed before them :)
I wonder whether the ability to pick out interesting problems is innate or can be taught. What do you think?
I really am not sure. A professor I used to know said that taste in problems is something that can't be taught. I am not sure I agree with that completely though. I think that in grad school it is possible to train people to ask why a question should be considered interest. In fact one might argue that asking the right questions is the core of good research.
Every field has the foundational issues that drive them. In theoretical computer science, and computational geometry, one of the key issues is often: What is the key process underlying the structure of a problem, and how can this be used to solve it ? A paper that can answer this question will more often than not be deemed interesting.
So it is important to understand what the raison d'etre of your chosen field is. This is usually never stated explicitly, but there is usually a tacit broad consensus on what it is, and this is where an advisor, and good training, can help a lot.
Beyond that though, it is probably not a good idea to worry too much about what is interesting. A vibrant research field is a mosaic that comes from individual contributions in many different directions. It would be boring if everyone did the same thing. One should be willing to take the effort to sell one's contributions though, and not stand on ceremony waiting for others to realize what pearls of wisdom you have placed before them :)
Thursday, March 11, 2004
Open Problems....
Finding interesting problems to work on is always challenging for a professional researcher. Usually a nice problem to work on should be
(1) interesting to you !!
(2) at least of some interest to the community
People may argue about the relevance of (2). The way I see it is that research is often like being at a very large party. There are many conversations going on all the time, and
you can either start one, or join in an ongoing discussion. You could also stand in a corner and talk to yourself, but it's not always much fun, and you may not always get people to listen.
So how does one find out what problems are of interest to the community ? Some factors:
(a) is the problem of relevance to many other problems (a "hub" problem)
(b) is it something that has been around for a while and is unsolved (an "authority" problem, to stretch a PageRank metaphor).
For some time now, the computational geometry has maintained a list of open problems that by virtue of their existence satisfy both of the above conditions.
The Open Problems Project is edited by Erik Demaine, Joe Mitchell, and Joe O'Rourke, and has grown from its original set of 30 to 56 problems now.
Some of these problems are quite hard and have been around for a while; others may just need the right idea to be cracked. Knowing which is which is the $1,000,000 question :)
(1) interesting to you !!
(2) at least of some interest to the community
People may argue about the relevance of (2). The way I see it is that research is often like being at a very large party. There are many conversations going on all the time, and
you can either start one, or join in an ongoing discussion. You could also stand in a corner and talk to yourself, but it's not always much fun, and you may not always get people to listen.
So how does one find out what problems are of interest to the community ? Some factors:
(a) is the problem of relevance to many other problems (a "hub" problem)
(b) is it something that has been around for a while and is unsolved (an "authority" problem, to stretch a PageRank metaphor).
For some time now, the computational geometry has maintained a list of open problems that by virtue of their existence satisfy both of the above conditions.
The Open Problems Project is edited by Erik Demaine, Joe Mitchell, and Joe O'Rourke, and has grown from its original set of 30 to 56 problems now.
Some of these problems are quite hard and have been around for a while; others may just need the right idea to be cracked. Knowing which is which is the $1,000,000 question :)
Wednesday, March 10, 2004
The Mathematical American & Sangaku
Scientific American has an online collection of articles titled "The Mathematical American" (not free, alas).
One article that intrigued me was the note on Japanese Temple Geometry (Sangaku) by Tony Rothman:
During Japan's period of national seclusion (1639-1854), native mathematics thrived, as evidenced in sangaku--wooden tablets engraved with geometry problems hung under the roofs of shrines and temples
There is a nice link discussing some of the problems.
One article that intrigued me was the note on Japanese Temple Geometry (Sangaku) by Tony Rothman:
During Japan's period of national seclusion (1639-1854), native mathematics thrived, as evidenced in sangaku--wooden tablets engraved with geometry problems hung under the roofs of shrines and temples
There is a nice link discussing some of the problems.
Computational Origami OR How to eat sugary cereal that's good for you
Computational geometry draws its parentage both from geometry, and from the theory of computation. As such, it has both formal aspects (only professional mathematicians need apply!) and some gloriously innovative and entertaining dimensions that give it wide reach beyond the academic environment. Heck, you might be doing computational geometry without even knowing it !
Origami (and folding) is one such area. The field of computational origami sprung up in an attempt to analyze folding patterns and ask questions like: 'Here's a set of creases in a sheet of paper: how do I get there from a blank sheet ?'
Not unlike Euclid's axioms, there are basic axioms underpinning the science of folding. These were developed by mathematician Humiaki Huzita in 1992.
Robert Lang, credited with being one of the pioneers of the field of computational origami, has a program called TreeMaker that you can use to design origami designs from scratch.
Alas, the question we asked earlier has an answer, but like most questions in theoretical computer scieince, it is an answer we may not like: Determining whether a given sequence of creases can be achieved by flat folding is NP-hard. This is due to Marshall Bern and Barry Hayes.
You might wonder, "All this is fine and dandy, but can I get a job doing computational origami ?". As it turns out...
Erik Demaine, a professor at MIT, is known (among other things) for his work on folding and origami. He has a very nice folding page.
David Eppstein, whose geometry pages merit many entries of their own, has another nice page on folding.
... Of course, with great power comes great responsibility. Not all origamists use their superpowers for good....
UPDATE: Looks like I'm not the first to comment on computational origami
Origami (and folding) is one such area. The field of computational origami sprung up in an attempt to analyze folding patterns and ask questions like: 'Here's a set of creases in a sheet of paper: how do I get there from a blank sheet ?'
Not unlike Euclid's axioms, there are basic axioms underpinning the science of folding. These were developed by mathematician Humiaki Huzita in 1992.
Robert Lang, credited with being one of the pioneers of the field of computational origami, has a program called TreeMaker that you can use to design origami designs from scratch.
Alas, the question we asked earlier has an answer, but like most questions in theoretical computer scieince, it is an answer we may not like: Determining whether a given sequence of creases can be achieved by flat folding is NP-hard. This is due to Marshall Bern and Barry Hayes.
You might wonder, "All this is fine and dandy, but can I get a job doing computational origami ?". As it turns out...
Erik Demaine, a professor at MIT, is known (among other things) for his work on folding and origami. He has a very nice folding page.
David Eppstein, whose geometry pages merit many entries of their own, has another nice page on folding.
... Of course, with great power comes great responsibility. Not all origamists use their superpowers for good....
UPDATE: Looks like I'm not the first to comment on computational origami
Tuesday, March 09, 2004
What is Computational Geometry ?
There aren't that many blogs on computer science, although there are tons on computers. Especially if one works in theoretical computer science, one is accustomed to the blank stares that people give you when you tell them what you do for a living. Of course, doing geometry is even worse..
Geometry ? Isn't that something you do in high school
Who cares about geometry anyway ?
That's all very well, but why does my PC crash when I click this button
I will try to deal with the first two questions (as for the third, get linux...). For those of you who have drunk deep at the holy well of geometry, there will (hopefully) be things of use for you as well: I'll try to keep a running commentary of events of note in the geometry community and around. Comments, brickbats, insults, are all welcome.
And occasionally I might meander further into the real world; after all, a blog is for meandering...
Geometry ? Isn't that something you do in high school
Who cares about geometry anyway ?
That's all very well, but why does my PC crash when I click this button
I will try to deal with the first two questions (as for the third, get linux...). For those of you who have drunk deep at the holy well of geometry, there will (hopefully) be things of use for you as well: I'll try to keep a running commentary of events of note in the geometry community and around. Comments, brickbats, insults, are all welcome.
And occasionally I might meander further into the real world; after all, a blog is for meandering...
Thursday, March 04, 2004
Yes, but can it lower the toilet seat behind it ?
Craig Silverstein was talking at a search engine meet about the next generation of search engines. This from WebProNews:
Silverstein is now changing his vision of the future of search to an even more bizarre scenario. In a speech closely resembling a Star Trek episode, he shared his new prediction of search moving towards the existence of search pets hundreds of years from now. These search pets would not necessarily be like a pet dog, but more like "a genetically engineered beast."
Adding to the science fiction, he believes search pets will be able to understand emotions and allow people to search for things that aren't necessarily facts. For example, searchers can ask search pets, "What did Bob mean when he said that?"
[...snip...]
Search pets could also help out in the bedroom. Take marital issues, for example. Guys, when you ask your honey what's wrong and she says nothing - there IS somehting wrong and it's NOT nothing. Silverstein sees search pets as being able to find to the correct answer to these tricky questions.
Silverstein is now changing his vision of the future of search to an even more bizarre scenario. In a speech closely resembling a Star Trek episode, he shared his new prediction of search moving towards the existence of search pets hundreds of years from now. These search pets would not necessarily be like a pet dog, but more like "a genetically engineered beast."
Adding to the science fiction, he believes search pets will be able to understand emotions and allow people to search for things that aren't necessarily facts. For example, searchers can ask search pets, "What did Bob mean when he said that?"
[...snip...]
Search pets could also help out in the bedroom. Take marital issues, for example. Guys, when you ask your honey what's wrong and she says nothing - there IS somehting wrong and it's NOT nothing. Silverstein sees search pets as being able to find to the correct answer to these tricky questions.
Tuesday, March 02, 2004
Heads ! No, Tails !
Phil Luckett is probably feeling rather aggrieved right about now.
Persi Diaconis, Susan Holmes and Richard Montgomery just showed that coin tossing, that most elementary of approaches to generating randomness, is biased. With a probability of 51%, a coin will land on the same side that it was tossed from.
If you ever get a chance to attend one of Prof Diaconis's talks, definitely do so. His biography is rather entertaining; he spent time in a circus before becoming a mathematician.
Persi Diaconis, Susan Holmes and Richard Montgomery just showed that coin tossing, that most elementary of approaches to generating randomness, is biased. With a probability of 51%, a coin will land on the same side that it was tossed from.
If you ever get a chance to attend one of Prof Diaconis's talks, definitely do so. His biography is rather entertaining; he spent time in a circus before becoming a mathematician.
Monday, March 01, 2004
So I just discovered Squawkbox.tv. An excellent tool for adding comments to sites like blog*spot that don't allow native commenting.
Stay tuned... will start updating in earnest after Friday....
[UPDATE]: Just found Haloscan. Even better for comments/trackbacks....
Stay tuned... will start updating in earnest after Friday....
[UPDATE]: Just found Haloscan. Even better for comments/trackbacks....
Welcome,
There are lots of blogs on the web, but very few on algorithms and theoretical computer science. I hope to use this space to publish random musings
on this fascinating field. And no, I don't fix computers for a living.
I am inspired by Lance Fortnow's Complexity Blog, which is always interesting reading...
There are lots of blogs on the web, but very few on algorithms and theoretical computer science. I hope to use this space to publish random musings
on this fascinating field. And no, I don't fix computers for a living.
I am inspired by Lance Fortnow's Complexity Blog, which is always interesting reading...
Subscribe to:
Posts (Atom)