You have to wonder: when you lay down a mathematical challenge, do you throw a quill at the feet of your rival ?In 1530, Niccolo Tartaglia (1500-1557) received two problems in cubic equations from Zuanne da Coi and announced that he could solve them. He was soon challenged by Fiore, which led to a famous contest between the two. Each contestant had to put up a certain amount of money and to propose a number of problems for his rival to solve. Whoever solved more problems within 30 days would get all the money.
Tartaglia received questions in the form x3 + mx = n, for which he had worked out a general method. Fiore received questions in the form x3 + mx2 = n, which proved to be too difficult for him to solve, and Tartaglia won the contest.
Later, Tartaglia was persuaded by Gerolamo Cardano (1501-1576) to reveal his secret for solving cubic equations. Tartaglia did so only on the condition that Cardano would never reveal it. A few years later, Cardano learned about Ferro's prior work and broke the promise by publishing Tartaglia's method in his book Ars Magna (1545) with credit given to Tartaglia. This led to another competition between Tartaglia and Cardano, for which the latter did not show up but was represented by his student Lodovico Ferrari (1522-1565). Ferrari did better than Tartaglia in the competition, and Tartaglia lost both his prestige and income.
Monday, September 25, 2006
Mathematics as blood sport
I for one am glad that we have left the challenge era of mathematics far behind us. From Wikipedia's entry on the cubic equation:
Thursday, September 21, 2006
Turingistan
Bernard Chazelle has updated what has been called 'The IPod essay'. An excerpt:
Let's try a thought experiment, shall we? You're the unreconstructed Algorithm skeptic. Fresh from splitting your playlist, Alice, naturally, is the advocate. One day, she comes to you with a twinkle in her eye and a question on her mind: “What are the benefits of the central law of mechanics?” After a quick trip to Wikipedia to reactivate your high school physics neurons and dust off the cobwebs around them, you reply that F=ma does a decent job of modeling the motion of an apple as it is about to crash on Newton's head: “What's not to like about that?” “Oh, nothing,” retorts Alice, “except that algorithms can be faithful modelers, too; they're great for conducting simulations and making predictions.” Pouncing for the kill, she adds: “By the way, to be of any use, your vaunted formulas will first need to be converted into algorithms.” Touché.Much fun. Go read.
Wednesday, September 20, 2006
The magic of √2
Bill Gasarch has an entertaining dialogue on √2 in the latest issue of SIGACT News (which also has an interesting variant of art-gallery problems in the Geometry column). It's a remarkable coincidence, because I was just about to post an entry about a 7th grade classroom problem that revolves around properties of √2). Unlike T, T, F, S, E, this problem actually does have some really nice math behind it.
The problem is as follows:
It turns out that numbers satisfying this equation can be derived from solutions to Pell's equation:
where x, y are integers. Pell's equation actually gives good rational approximations to √2, in the form x/y, where x, y are solutions. What's more, if x/y is a convergent in the continued fraction of √2, then x2y2 is a square triangular number (i.e can be written as n(n+1)/2 or k2).
There's also a general form of the solution, that I first found (courtesy David Applegate) in the Hardy/Wright book on number theory. The "trick" here is to realize that the appropriate way to solve this is over the field of numbers of the form a + b√2.
It's rather satisfying that a simple extra credit problem for a 7th grade math class can yield such nuggets.
The problem is as follows:
You live on a street where the houses are numbered 1,2, 3, etc.. You notice that the sum of house numbers prior to yours equals the sum of house numbers after yours. What is your house number, and how many houses are there on the street ? Your answer should be in the 30sSome quick algebra on n, the number of houses, and k, your house address, reveals that the numbers satisfying this condition yield a square triangular number. Namely, n and k must satisfy the equation
n(n+1)/2 = k2
It turns out that numbers satisfying this equation can be derived from solutions to Pell's equation:
x2 - 2 y2 = 1
where x, y are integers. Pell's equation actually gives good rational approximations to √2, in the form x/y, where x, y are solutions. What's more, if x/y is a convergent in the continued fraction of √2, then x2y2 is a square triangular number (i.e can be written as n(n+1)/2 or k2).
There's also a general form of the solution, that I first found (courtesy David Applegate) in the Hardy/Wright book on number theory. The "trick" here is to realize that the appropriate way to solve this is over the field of numbers of the form a + b√2.
It's rather satisfying that a simple extra credit problem for a 7th grade math class can yield such nuggets.
Sunday, September 17, 2006
Looming submission deadlines.
Apropos of my post on implementing geometric algorithms, it seems like a good time to mention the upcoming ALENEX deadline.
to add the deadline to your calendar.
Another deadline that's coming up even sooner is for the Fall Workshop on Computational Geometry, the annual math-conference-style event for geometers. This year it's in Smith College on Nov 10-11, and is being run by Ileana Streinu. One of the special events this year is a 3D Printing demo by Joe O'Rourke. The deadline is Sep 22, and it should already be in your calendar by now, but if not, click here.
p.s if you want to create buttons like above for your event, here's the link.
The aim of the ALENEX workshop is to provide a forum for presentation of original research in the implementation and experimental evaluation of algorithms and data structures.If you use Google Calendar, click
to add the deadline to your calendar.Another deadline that's coming up even sooner is for the Fall Workshop on Computational Geometry, the annual math-conference-style event for geometers. This year it's in Smith College on Nov 10-11, and is being run by Ileana Streinu. One of the special events this year is a 3D Printing demo by Joe O'Rourke. The deadline is Sep 22, and it should already be in your calendar by now, but if not, click here
.p.s if you want to create buttons like above for your event, here's the link.
Thursday, September 14, 2006
Implementing geometric algorithms.
Over at bit-player, Brian Hayes has a tale of woe about implementing a geometric algorithm. Not even a complicated one at that, merely an algorithm to check if two line segments intersect. His story is the usual one: general position is a fiction thought up by sadistic geometers (but of course !), and even the simplest of ideas needs many special cases to take of degenerate data.
Apart from being surprised that he didn't have problems with precision (how DO you tell if both endpoints of a line segment are identical), I sympathize with his plight. As anyone who's ever implemented a geometric algorithm will tell you, it's much harder than it seems, and to an extent, the idealized algorithms geometers design can be hard to implement. CGAL and LEDA have made life a lot easier, but robustness and exact computation are still important (if highly uncool) areas of computational geometry.
Apart from being surprised that he didn't have problems with precision (how DO you tell if both endpoints of a line segment are identical), I sympathize with his plight. As anyone who's ever implemented a geometric algorithm will tell you, it's much harder than it seems, and to an extent, the idealized algorithms geometers design can be hard to implement. CGAL and LEDA have made life a lot easier, but robustness and exact computation are still important (if highly uncool) areas of computational geometry.
Wednesday, September 13, 2006
Matrix wizardry
While we're on the topic of books,
p.s the reason the identity is so handy is that it allows you to get the variable matrix X out from in between A and B.
vec(AXB) = (BT ⊗ A) vec(X)This identity is your best friend if you're doing any kind of matrix calculus. To know more about it, and all you might ever want to know about Kronecker products, the vec() operator, and matrix calculus, check out The Matrix Cookbook, a 50+ page reference guide for all things matrix and calculus.
p.s the reason the identity is so handy is that it allows you to get the variable matrix X out from in between A and B.
New textbooks in theoryCS...
There appears to be a outpouring of new theoryCS textbooks. I had mentioned the Mitzenmacher/Upfal book on probability and randomized algorithms some time ago. Recently, Jon Kleinberg and Éva Tardos published Algorithm Design, the book with THE MOST elaborate real-world exercises I have seen. Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani have another algorithms text coming out as well.
The not-so-latest addition to this list is a new book on complexity theory by Sanjeev Arora and Boaz Barak. For a long time now, Papadimitriou's book has been the definitive text in this area, but it has begun showing its age, especially with all the new developments in complexity theory. The Arora/Barak book is not yet published, but has been placed online for comments.
The magic of Papadimitriou's book was in making complexity classes spring to life as the denizens of the Zoo that they really are. Complexity theory can be a dry topic if not imbued with a sense of direction and purpose, helping us understand the WHY of how these classes came to be. If my cursory scanning of the Arora/Barak book indicates anything, it is that this new book is a worthy successor.
The two books cover similar material in the foundational sections; where I think the new book takes off is in its coverage of the more "modern" aspects of complexity theory: the profound results on pseudorandomness, hardness and cryptograpy, interactive proofs and approximations, natural proofs, communication complexity and lower bound methods, and even quantum computing.
The not-so-latest addition to this list is a new book on complexity theory by Sanjeev Arora and Boaz Barak. For a long time now, Papadimitriou's book has been the definitive text in this area, but it has begun showing its age, especially with all the new developments in complexity theory. The Arora/Barak book is not yet published, but has been placed online for comments.
The magic of Papadimitriou's book was in making complexity classes spring to life as the denizens of the Zoo that they really are. Complexity theory can be a dry topic if not imbued with a sense of direction and purpose, helping us understand the WHY of how these classes came to be. If my cursory scanning of the Arora/Barak book indicates anything, it is that this new book is a worthy successor.
The two books cover similar material in the foundational sections; where I think the new book takes off is in its coverage of the more "modern" aspects of complexity theory: the profound results on pseudorandomness, hardness and cryptograpy, interactive proofs and approximations, natural proofs, communication complexity and lower bound methods, and even quantum computing.
Thursday, September 07, 2006
The Indian grad student experience, and more...
I occasionally read the Chronicle of Higher Education: I guess it's de rigeur for my academic colleagues. It's often too stuffy for me, but this issue has two articles that are real gems (and had me nodding my head in agreement paragraph after paragraph).
Unless you've hung around Indian grad students, you have no idea of the kind of organizational skills that we can muster up when it comes to helping fellow Indian students acclimatize. I recall being picked up at SFO by a "senior" grad student and driven to Stanford, and supplied with all kinds of useful information when I got there, (including copies of all the variations of the driving tests the California DMV uses!). Apparently, things have become much more sophisticated: check out this description of the Indian student organization at NC State (and yes, I do own a copy of The Inscrutable Americans; the letter Gopal writes to his father at the beginning of the book is priceless).
The other article could have easily been written about my parents, and their general bewilderment at the kind of work I do (I remember the first time I went to work in shorts while my father was visiting, and how scandalized he was) . It's hilarious: do check it out.
Unless you've hung around Indian grad students, you have no idea of the kind of organizational skills that we can muster up when it comes to helping fellow Indian students acclimatize. I recall being picked up at SFO by a "senior" grad student and driven to Stanford, and supplied with all kinds of useful information when I got there, (including copies of all the variations of the driving tests the California DMV uses!). Apparently, things have become much more sophisticated: check out this description of the Indian student organization at NC State (and yes, I do own a copy of The Inscrutable Americans; the letter Gopal writes to his father at the beginning of the book is priceless).
The other article could have easily been written about my parents, and their general bewilderment at the kind of work I do (I remember the first time I went to work in shorts while my father was visiting, and how scandalized he was) . It's hilarious: do check it out.
Wednesday, September 06, 2006
Data hosting on the web
I recently lost my cellphone, and all my contacts with it. I got a new phone (off ebay, no less) and cingular sent me a SIM card so I could preserve my number. But my contacts were all gone. Now I hear about a new service called ZYB.com that will maintain a web backup of your contacts. The idea is that they collect your contact info (via SMS) and store it, and you can retrieve it (again via SMS) on any phone that allows for text messaging.
It's a cool idea: although there are doohickeys you can get to sync your palm/outlook/PC addressbook with a phone, they are usually vendor specific. This is more general, and is aligned with the whole "store your data on the web" philosophy that's all the rage nowadays (mail, calendars, online spreadsheets, ...)
Privacy of course is the issue, especially with contact info, a gold mine of real telephone numbers and often email addresses. ZYB of course makes all the right noises about privacy, but ultimately you have to trust them.
Why must that be ? It can't be that hard to store data encrypted, and decrypt on the fly only when a user provides a pass-phrase ? The problem with SMS specifically is that the user might have to type the pass phrase out in the open, but maybe there's an IPsec equivalent of SMS out there ? And even if there isn't, wouldn't server-side encryption obviate the need to trust a private entity ?
Given how ubiquitous crypto has become, I think I'd need to be convinced why obvious schemes like this can't be used before handing over data to an entity that I have to "trust".
p.s another point that came up in discussion was the lifetime of such a company. What's the guarantee they won't go belly up in a year and sell your data, or worse, lose it ?
It's a cool idea: although there are doohickeys you can get to sync your palm/outlook/PC addressbook with a phone, they are usually vendor specific. This is more general, and is aligned with the whole "store your data on the web" philosophy that's all the rage nowadays (mail, calendars, online spreadsheets, ...)
Privacy of course is the issue, especially with contact info, a gold mine of real telephone numbers and often email addresses. ZYB of course makes all the right noises about privacy, but ultimately you have to trust them.
Why must that be ? It can't be that hard to store data encrypted, and decrypt on the fly only when a user provides a pass-phrase ? The problem with SMS specifically is that the user might have to type the pass phrase out in the open, but maybe there's an IPsec equivalent of SMS out there ? And even if there isn't, wouldn't server-side encryption obviate the need to trust a private entity ?
Given how ubiquitous crypto has become, I think I'd need to be convinced why obvious schemes like this can't be used before handing over data to an entity that I have to "trust".
p.s another point that came up in discussion was the lifetime of such a company. What's the guarantee they won't go belly up in a year and sell your data, or worse, lose it ?
SODA results trickling in...
The full list should be available soon. Unusually, no information about accepts/submits was provided in the author notification.
Here's our (accepted) paper.
Update: 135 papers accepted, with some caveats. There were 4 merges, and with two papers, I believe that there will be two separate papers in the (already extra-large) proceedings, but only one talk. The rationale for this escapes me. Effectively there will be 137 papers in the proceedings though. This translates to a 36% acceptance rate.
Update II: The list of accepted papers is here.
Here's our (accepted) paper.
Update: 135 papers accepted, with some caveats. There were 4 merges, and with two papers, I believe that there will be two separate papers in the (already extra-large) proceedings, but only one talk. The rationale for this escapes me. Effectively there will be 137 papers in the proceedings though. This translates to a 36% acceptance rate.
Update II: The list of accepted papers is here.
Thursday, August 31, 2006
Undergrads and arXiv ?
Via Daniel Lemire, this prediction:
If you are an undergrad who's never functioned without the arXiv, please please pretty please apply for a summer job at AT&T, and request me as your mentor.
I shall now wait for a deluge of applications to clog my mailbox.
< snarky researcher off>
Today’s undergrads have never thought about the world any differently – they’ve never functioned without IM and Wikipedia and arXiv, and they’re going to demand different kinds of review for different kinds of papers.< snarky researcher on>
If you are an undergrad who's never functioned without the arXiv, please please pretty please apply for a summer job at AT&T, and request me as your mentor.
I shall now wait for a deluge of applications to clog my mailbox.
< snarky researcher off>
Wednesday, August 30, 2006
Planar graphs and Steinitz's theorem
One way of representing a 3-connected planar graph is as the 1-skeleton (i.e the vertices and edges) of a convex polytope. A neat way of visualizing this is by shining a light above one face of the polytope and looking at the shadow formed (see David Eppstein's beautiful picture). Steinitz's theorem says that in fact this is an exact characterization: convex polytopes are exactly those polytopes whose edge graphs are planar.
There are different ways this convex polytope can be constructed, and it can be made to take various forms. Oded Schramm, in a paper titled 'How to Cage an Egg' that should go on my list of cool paper titles, shows that given any convex polytope and any smooth strictly convex body in R3, there is a combinatorially equivalent convex polytope that can be embedded such that each edge touches the surface of the convex body (in particular, we could use a sphere). There are many other results of this flavor; Ziegler's book on polytopes has more, as does Jeff Erickson's page on constructing convex polytopes.
But the question that puzzles me is this. Steinitz's original proof yields a polytope with rational coordinates (and thus integer coordinates). However, the values involved are doubly exponential in the number of vertices. Subsequently, Onn and Sturmfels showed that a "mere" single exponential suffices (specifically, their bound is of the form n169n3). It is open whether a polynomial (quadratic?) bound suffices.
Enter László Lovász, and the Colin de Verdière number of a graph. It would take too long to explain this number here (van der Holst, Lovász and Schrijver have a survey); basically it's the second eigenvalue of an associated matrix and has the interesting property of correlating with planarity, outer planarity and linkless embeddability for different values of the number. Lovász and Schrijver showed that a Colin de Verdière matrix (a matrix achieving the number) can be used to embed a planar graph on the sphere (using the geodesics as edges) so that each face is the intersection of the sphere with a convex polyhedral cone.
Lovász, in later work, then showed that this matrix can be used to generate a Steinitz representation of a planar graph as well. Which finally brings me to the question I wanted to ask:
Is there anything known about the size complexity of the Steinitz representation that the Lovász construction generates ? My references for the size of the Steinitz representation are quite old (the Ziegler book and the Onn/Sturmfels paper) and maybe there is a known polynomial upper bound ? If not, could the Lovász construction be a good candidate ?
It's worth noting that for higher dimensional polytopes, it is known that a doubly exponential representation is the best one can hope for. As often happens, the 3D case is special in this regard.
Update: David Eppstein points out that Chrobak, Goodrich and Tamassia showed a bound of O(n log n) bits per vertex (instead of n3) in SoCG 1996 (they apparently weren't aware of the Onn/Sturmfels result though).
Update II: Isn't the internet great ! Another commenter points out a monograph by
Jürgen Richter-Gebert on the realization of polytopes. Here's where things get interesting. The monograph (dated 1996) has two Steinitz realizations. One is a general bound that uses 18n2 bits per vertex (better than Onn/Sturmfels) and the other, which applies to simplicial polytopes (specifically realizations of the 3-connected planar graphs that Chrobak et al consider), uses linear number of bits per vertex (something like n * log 43) ! So this work improves on the Chrobak et al work, while being roughly concurrent (Both author groups are unaware of each other's work).
Of course all of this predates the Lovász construction, so the possibility of further improvement still exists.
There are different ways this convex polytope can be constructed, and it can be made to take various forms. Oded Schramm, in a paper titled 'How to Cage an Egg' that should go on my list of cool paper titles, shows that given any convex polytope and any smooth strictly convex body in R3, there is a combinatorially equivalent convex polytope that can be embedded such that each edge touches the surface of the convex body (in particular, we could use a sphere). There are many other results of this flavor; Ziegler's book on polytopes has more, as does Jeff Erickson's page on constructing convex polytopes.
But the question that puzzles me is this. Steinitz's original proof yields a polytope with rational coordinates (and thus integer coordinates). However, the values involved are doubly exponential in the number of vertices. Subsequently, Onn and Sturmfels showed that a "mere" single exponential suffices (specifically, their bound is of the form n169n3). It is open whether a polynomial (quadratic?) bound suffices.
Enter László Lovász, and the Colin de Verdière number of a graph. It would take too long to explain this number here (van der Holst, Lovász and Schrijver have a survey); basically it's the second eigenvalue of an associated matrix and has the interesting property of correlating with planarity, outer planarity and linkless embeddability for different values of the number. Lovász and Schrijver showed that a Colin de Verdière matrix (a matrix achieving the number) can be used to embed a planar graph on the sphere (using the geodesics as edges) so that each face is the intersection of the sphere with a convex polyhedral cone.
Lovász, in later work, then showed that this matrix can be used to generate a Steinitz representation of a planar graph as well. Which finally brings me to the question I wanted to ask:
Is there anything known about the size complexity of the Steinitz representation that the Lovász construction generates ? My references for the size of the Steinitz representation are quite old (the Ziegler book and the Onn/Sturmfels paper) and maybe there is a known polynomial upper bound ? If not, could the Lovász construction be a good candidate ?
It's worth noting that for higher dimensional polytopes, it is known that a doubly exponential representation is the best one can hope for. As often happens, the 3D case is special in this regard.
Update: David Eppstein points out that Chrobak, Goodrich and Tamassia showed a bound of O(n log n) bits per vertex (instead of n3) in SoCG 1996 (they apparently weren't aware of the Onn/Sturmfels result though).
Update II: Isn't the internet great ! Another commenter points out a monograph by
Jürgen Richter-Gebert on the realization of polytopes. Here's where things get interesting. The monograph (dated 1996) has two Steinitz realizations. One is a general bound that uses 18n2 bits per vertex (better than Onn/Sturmfels) and the other, which applies to simplicial polytopes (specifically realizations of the 3-connected planar graphs that Chrobak et al consider), uses linear number of bits per vertex (something like n * log 43) ! So this work improves on the Chrobak et al work, while being roughly concurrent (Both author groups are unaware of each other's work).
Of course all of this predates the Lovász construction, so the possibility of further improvement still exists.
Saturday, August 26, 2006
Mathematics and Wikipedia
From yet more ink spilled over l'affaire Perelman, a description of mathematics apropos for these modern times:
Mathematics is supposed to be a Wikipedia-like undertaking, with thousands of self-effacing scriveners quietly laboring over a great self-correcting text.
Friday, August 25, 2006
TWA: Travelling while Asian
So let me get this straight:
- You can't talk in Arabic
- You can't fidget with a cell phone
- You can't wear a T-shirt with Arabic writing
- You can't pray
Tuesday, August 22, 2006
The "I-Team" vs the A-Team.
From Terence Tao's Field's medal announcement:
He did this work in collaboration with four other mathematicians, James Colliander, Markus Keel, Gigliola Staffilani, and Hideo Takaoka. Together they have become known as the "I-team", where "I" denotes many different things, including "interaction"... The word "interaction" also refers to interactions among the team members, and indeed collaboration is a hallmark of Tao's work.Consider this, from the A-Team:
I like mathematical progressions, but we're really picky about whom we work for.Given one of the things Tao won the Fields Medal for, this is strangely appropriate.
Replacing impossibility by infeasibility
One of the great conceptual breakthroughs in cryptography was the idea that an impossibility - this code cannot be cracked - can be replaced by infeasibility - this code is computationally hard to crack - with great success. Indeed, the notion that all you need to do is fool a computationally bounded adversary is at the core of derandomization.
It's an idea that transcends theoryCS - that you can model entities by computationally bounded objects, and can then prove interesting things about them that you couldn't have done if the entity was all powerful. And it's realistic ! As long as you're willing to believe in the effective variant of the Church-Turing thesis (all effective computations are in BPP; we'll pretent quantum computing doesn't exist for now), then it accurately models any computational entity you can choose to build.
Which brings us to social choice and voting theory. As you may well be aware, Arrow's theorem is a rather depressing impossibility result for designing a "fair" election. Either you lose some nice property (no dictatorship!), or some adversary can find a way to beat the system another way. But given all of the above, a more plausible question one might ask is: can a computationally bounded adversary crack an election ? (Disclaimer: I have no evidence that Diebold is a computationally bounded adversary; it certainly has no resource constraints)
What got my attention were two new papers on the arxiv, one by Faliszewski, Hemaspaandra, and Hemaspaandra, and the other by Hemaspaandra, Hemaspaandra, and Rothe.
The first paper asks the question that Katherine Harris must have surely wondered about, "How Hard Is Bribery in Elections?". The short answer is, "It depends", and the long answer is that depending on the type of voting scheme and who's doing the rigging (a briber or the voters themselves), the problem goes between being in P and being NP-Complete.
The second paper studies the problem of when the organizer of an election seeks to rig it:
It's an idea that transcends theoryCS - that you can model entities by computationally bounded objects, and can then prove interesting things about them that you couldn't have done if the entity was all powerful. And it's realistic ! As long as you're willing to believe in the effective variant of the Church-Turing thesis (all effective computations are in BPP; we'll pretent quantum computing doesn't exist for now), then it accurately models any computational entity you can choose to build.
Which brings us to social choice and voting theory. As you may well be aware, Arrow's theorem is a rather depressing impossibility result for designing a "fair" election. Either you lose some nice property (no dictatorship!), or some adversary can find a way to beat the system another way. But given all of the above, a more plausible question one might ask is: can a computationally bounded adversary crack an election ? (Disclaimer: I have no evidence that Diebold is a computationally bounded adversary; it certainly has no resource constraints)
What got my attention were two new papers on the arxiv, one by Faliszewski, Hemaspaandra, and Hemaspaandra, and the other by Hemaspaandra, Hemaspaandra, and Rothe.
The first paper asks the question that Katherine Harris must have surely wondered about, "How Hard Is Bribery in Elections?". The short answer is, "It depends", and the long answer is that depending on the type of voting scheme and who's doing the rigging (a briber or the voters themselves), the problem goes between being in P and being NP-Complete.
The second paper studies the problem of when the organizer of an election seeks to rig it:
Electoral control refers to attempts by an election's organizer (``the chair'') to influence the outcome by adding/deleting/partitioning voters or candidates.In some circles, this is also known as the venue selection process for SODA. What the authors show is that by combining elections in a certain way, the overall election can be made resistant (i.e NP-hard) to control by the organizer.
Saturday, August 19, 2006
Originality vs understanding, and the nature of creativity.
One of the comments in the SIGGRAPH forum I talked about earlier was about the (mistaken) emphasis on original trivial contributions versus "incremental" but more profound contributions. The statement is of course stacked (who would argue in favor of "trivial" contributions !), but it brings up a point worth noting.
You can be creative while being original, and indeed this is the standard way one thinks about creativity. But solely emphasizing originality misses a deeper truth about why we do research, which is the acquiring of wisdom and understanding. Indeed, it takes a certain, different kind of creativity to deeply understand certain concepts, often by establishing connections between known areas or making subtle observations about the relationships between entities. Indeed, in computational geometry, we have a name for one such kind of creativity: "Chan's method" :)
Originality and understanding are part of the larger process of acquiring knowledge and wisdom about a domain. A new area of knowledge profits from originality because problems start blossoming forth, and ideas come fast and furious. Over time, deep understanding leads to the building of connections among known concepts, and this further strengthens the area. Mature areas like mathematics find great value in the establishing of connections; the whole of category theory can be viewed as one gigantic connection generator.
Computer science is a young discipline; like all young disciplines, new ideas are valued, and they come so fast that there is often little time to reflect and make connections. My personal belief (your mileage may vary) is that at least in the realm of algorithms and geometry we've reached a kind of consolidation limit point, where more and more often we are running up against problems that call for brand new ways of thinking, and where "more of the same" kinds of results seem less interesting. In such a setting, results that prove less, but connect more, seem more valuable to me.
You can be creative while being original, and indeed this is the standard way one thinks about creativity. But solely emphasizing originality misses a deeper truth about why we do research, which is the acquiring of wisdom and understanding. Indeed, it takes a certain, different kind of creativity to deeply understand certain concepts, often by establishing connections between known areas or making subtle observations about the relationships between entities. Indeed, in computational geometry, we have a name for one such kind of creativity: "Chan's method" :)
Originality and understanding are part of the larger process of acquiring knowledge and wisdom about a domain. A new area of knowledge profits from originality because problems start blossoming forth, and ideas come fast and furious. Over time, deep understanding leads to the building of connections among known concepts, and this further strengthens the area. Mature areas like mathematics find great value in the establishing of connections; the whole of category theory can be viewed as one gigantic connection generator.
Computer science is a young discipline; like all young disciplines, new ideas are valued, and they come so fast that there is often little time to reflect and make connections. My personal belief (your mileage may vary) is that at least in the realm of algorithms and geometry we've reached a kind of consolidation limit point, where more and more often we are running up against problems that call for brand new ways of thinking, and where "more of the same" kinds of results seem less interesting. In such a setting, results that prove less, but connect more, seem more valuable to me.
Wednesday, August 16, 2006
SIGGRAPH, hiring, and peer review.
There's been an interesting flareup in the graphics community prompted by the posting of a note by Michael Ashikhmin on his web page. Ashikhmin is a known graphics researcher (with SIGGRAPH papers to his credit) who recently (June this year) proclaimed his desire to leave the graphics community because of
None of the objections are particularly novel; indeed, I have yet to go to a theory conference where people have NOT complained about the reviewers. However, what takes this beyond just your ordinary embittered-researcher-rant is that many prominent researchers in graphics appear to publicly both agree with him.
Michael says in his letter that senior graphics researchers recommended that he host a forum devoted to discussing this issue, and once he set the forum up, many well known and respected graphics researchers (John Hart, Marc Levoy, and Jonathan Shewchuk among others), commented publicly on the matter. In fact, Marc Levoy (who's the papers chair for SIGGRAPH 2007) went further and organized a town hall meeting at SIGGRAPH 2006 to discuss paper reviewing procedures (I don't know what transpired there).
There are many comments on the forum from anonymous commenters who claim to be published authors at SIGGRAPH. As far as I can tell, not one person disagrees with the primary claims that Michael makes, although Marc does attempt to mount a defense of the paper review process, while still acknowledging the main problems, and outlining strategies that he will employ in 2007 to fix some of them.
Many good suggestions were made. One of the primary ones was to add a new SIGGRAPH-like conference so that one venue didn't have to take all the load (STOC and FOCS were cited favorably here). Prohibiting committee members from submitting was another idea (again, the theory community was cited), although this was frowned upon by Marc Levoy, who complained that he wouldn't be able to find people for a committee (he did aver that he wouldn't be submitting anything).
This is probably the first time I've seen this kind of discussion take place (partly) on the record without dismissing the complaint as sour grapes. The question of course is whether anything will come of it in the long term. It's worth mentioning that even in our conservative (by nature, not by politics) research world, change can happen, and can often happen rapidly. Witness the collective revolt by academicians of all stripes against Elsevier, and closer to home, consider the split in ICRA (one of the main robotics conferences) to form RSS (Robotics: Science and Systems).
my deep disgust for the state of affairs within computer graphics research community and my inability to fit well within existing systemHis grievances are many, and appear to be a direct consequence of the hegemonic nature of SIGGRAPH, by far the most prestigious conference in graphics. Specifically, he argues that all the usual problems with conference reviewing (extreme subjectiveness, poor quality of the reviews, clique-formation) are exacerbated by the overwhelming influence SIGGRAPH papers have on one's career (being hired, advancing in one's career, getting tenure, etc).
None of the objections are particularly novel; indeed, I have yet to go to a theory conference where people have NOT complained about the reviewers. However, what takes this beyond just your ordinary embittered-researcher-rant is that many prominent researchers in graphics appear to publicly both agree with him.
Michael says in his letter that senior graphics researchers recommended that he host a forum devoted to discussing this issue, and once he set the forum up, many well known and respected graphics researchers (John Hart, Marc Levoy, and Jonathan Shewchuk among others), commented publicly on the matter. In fact, Marc Levoy (who's the papers chair for SIGGRAPH 2007) went further and organized a town hall meeting at SIGGRAPH 2006 to discuss paper reviewing procedures (I don't know what transpired there).
There are many comments on the forum from anonymous commenters who claim to be published authors at SIGGRAPH. As far as I can tell, not one person disagrees with the primary claims that Michael makes, although Marc does attempt to mount a defense of the paper review process, while still acknowledging the main problems, and outlining strategies that he will employ in 2007 to fix some of them.
Many good suggestions were made. One of the primary ones was to add a new SIGGRAPH-like conference so that one venue didn't have to take all the load (STOC and FOCS were cited favorably here). Prohibiting committee members from submitting was another idea (again, the theory community was cited), although this was frowned upon by Marc Levoy, who complained that he wouldn't be able to find people for a committee (he did aver that he wouldn't be submitting anything).
This is probably the first time I've seen this kind of discussion take place (partly) on the record without dismissing the complaint as sour grapes. The question of course is whether anything will come of it in the long term. It's worth mentioning that even in our conservative (by nature, not by politics) research world, change can happen, and can often happen rapidly. Witness the collective revolt by academicians of all stripes against Elsevier, and closer to home, consider the split in ICRA (one of the main robotics conferences) to form RSS (Robotics: Science and Systems).
Tuesday, August 15, 2006
Poincare's conjecture
Dennis Overbye has a great article in the NYT today about the resolution(?) of Poincare's conjecture. He does an excellent job describing both the conjecture itself and the main line of attack that Perelman follows, while narrating the history of the proof both accurately and without unnecessary romanticization of the mathematicians involved.
For a more detailed nontechnical survey that goes more into the roles of the different players, see Allyn Jackson's article on the latest Notices of the AMS. A more technical account is presented in a manuscript by Shing-Tung Yau.
For a more detailed nontechnical survey that goes more into the roles of the different players, see Allyn Jackson's article on the latest Notices of the AMS. A more technical account is presented in a manuscript by Shing-Tung Yau.
Thursday, August 10, 2006
Guns don't kill people, people kill people.
I was watching CNN, and a talking head (who happened to be a former Somebody in Israeli aviation) was making a point that I thought was quite reasonable. He said that it's too hard to focus on the method of making explosives, since explosives sufficient to destroy a plane in mid-air can be made from a variety of chemicals. It was more important, in his view, to focus on the people executing the missions; it was much harder to hide oneself from an acute observer than it was to hide chemicals.
Israeli immigration is notorious for doing exactly this; I've never been to Israel, but colleagues tell me of being interrogated to within an inch of their lives about the details of theorems in the papers they were presenting. After 9/11, I remember similar arguments being made in the US, but they quickly got bogged down in issues of racial profiling, and we quickly found that randomly pulling out gentle Caucasian grandmothers from Iowa was a reasonable thing to do.
So what's the computer science angle here ? If we think of computer security, I'd argue that many of the discussions revolve around blocking techniques: this attack on that cryptosystem, that weakness in this OS, and so on. It seems like the security precautions being put into place on the airlines now are just like that: a weakness is revealed, a (usually overblown) patch is put in place, and so on.
This approach appears completely unsuited for protecting against "real" security hacks though ! The much-derided 'humint' approach appears to be far more effective (and far less overtly intrusive to the population at large).
Israeli immigration is notorious for doing exactly this; I've never been to Israel, but colleagues tell me of being interrogated to within an inch of their lives about the details of theorems in the papers they were presenting. After 9/11, I remember similar arguments being made in the US, but they quickly got bogged down in issues of racial profiling, and we quickly found that randomly pulling out gentle Caucasian grandmothers from Iowa was a reasonable thing to do.
So what's the computer science angle here ? If we think of computer security, I'd argue that many of the discussions revolve around blocking techniques: this attack on that cryptosystem, that weakness in this OS, and so on. It seems like the security precautions being put into place on the airlines now are just like that: a weakness is revealed, a (usually overblown) patch is put in place, and so on.
This approach appears completely unsuited for protecting against "real" security hacks though ! The much-derided 'humint' approach appears to be far more effective (and far less overtly intrusive to the population at large).
Precision, recall, and bottles of water.
The latest airline explosion plot has sparked a predictable overreaction by the much-beloved TSA, which once again demonstrates that it lacks a basic understanding of precision and recall.
Let's recap, shall we ? Suppose you're trying to find all elements of a subset S in a universe U, and return as an answer the set H.
Precision measures the quality of your answer; what fraction of the elements of H are indeed in S ? The higher the precision, the lower the false-positive rate.
Recall measures the efficacy of the procedure; what fraction of the elements of S did you actually find ? The higher the recall, the lower the false-negative rate.
As any statistician will tell you, false-positives and false-negatives are complementary; increase one, and the other decreases. Search engines need high precision, (they also need good ranking, but that's a different story).
The TSA is clearly going for high recall. Banning bottles of water will surely eliminate any future plans for liquid explosives that use water, but it also eliminates the many (how shall I say) *innocent* uses of water ?
p.s I don't mind the short term enforcement of stricer guidelines while law enforcement attempts to figure out what kinds of explosives were being designed. I just have no faith that the new draconian regulations will be relaxed any time soon, considering how long it took to allow us to carry nail clippers on board flights again.
Let's recap, shall we ? Suppose you're trying to find all elements of a subset S in a universe U, and return as an answer the set H.
Precision measures the quality of your answer; what fraction of the elements of H are indeed in S ? The higher the precision, the lower the false-positive rate.
Recall measures the efficacy of the procedure; what fraction of the elements of S did you actually find ? The higher the recall, the lower the false-negative rate.
As any statistician will tell you, false-positives and false-negatives are complementary; increase one, and the other decreases. Search engines need high precision, (they also need good ranking, but that's a different story).
The TSA is clearly going for high recall. Banning bottles of water will surely eliminate any future plans for liquid explosives that use water, but it also eliminates the many (how shall I say) *innocent* uses of water ?
p.s I don't mind the short term enforcement of stricer guidelines while law enforcement attempts to figure out what kinds of explosives were being designed. I just have no faith that the new draconian regulations will be relaxed any time soon, considering how long it took to allow us to carry nail clippers on board flights again.
Thursday, August 03, 2006
Timestamping using the arXiv...
When is it appropriate to post an article to the arXiv ? You could opt to post when
When IEEE SPDL comes along, who claims precedence ? Certainly not Santa, since he has no document to be cited ? But can Banta claim precedence merely by posting on the arXiv ? there has been no peer review after all, and his proof could be full of holes.
It would be easy enough to declare that Banta has no claim to precedence, since there is no peer-reviewed cited work available. But there are two problems with this:
As my Indian readers will know, Santa and Banta often star in jokes making fun of the lack of intelligence of a particular ethnic community in India. At least in this anecdote, they are both smart researchers; consider it my contribution to ethnic amity. :)
- A journal /conference accepts the paper. You could also just post it on your website at that point, although the arXiv does allow for better dissemination.
- You submit to a journal/conference. I'm told that this is often the model in areas of physics. Seems reasonable enough, although at least in CS, the fear of being "scooped" might prevent you from doing so, not to mention the often-byzantine "double-blind" policies of some conferences.
- You've dried yourself off from the shower you were taking when inspiration struck. Ok, so maybe I'm exaggerating slightly, but...
When IEEE SPDL comes along, who claims precedence ? Certainly not Santa, since he has no document to be cited ? But can Banta claim precedence merely by posting on the arXiv ? there has been no peer review after all, and his proof could be full of holes.
It would be easy enough to declare that Banta has no claim to precedence, since there is no peer-reviewed cited work available. But there are two problems with this:
- It negates the value of the arxiv ! After all, if I cannot claim any kind of precedence, but can have someone pick over my result and improve it, what incentive do I have for posting anything ? One answer to this could be that my result is cast-iron, and can't be improved, but this happens far less often, and cannot be a useful answer in all situations.
- It ignores common practice within the community ! People will often talk about new results they have, and if the result is important enough, word will spread, and ownership will be (informally) established.
- People cite technical reports all the time ! One of the founding papers of streaming algorithms was (and has remained) a DEC technical report.
As my Indian readers will know, Santa and Banta often star in jokes making fun of the lack of intelligence of a particular ethnic community in India. At least in this anecdote, they are both smart researchers; consider it my contribution to ethnic amity. :)
Musings on the arXiv.
Things that make you go 'hmmmm', or why arXiv can't replace peer review:
Take the paper excerpted above. It claims to solve graph isomorphism in polynomial time, a result that if true would be quite momentous. The abstract already warns me that the technical material would be complex, and (call me parochial, shallow, what-have-you) the complete absence of grammatical structure does raise some tiny red flags.
So where does this leave me ? I'd like to know whether there is any merit to this paper. In the absence of peer review, I'd have to wade through it myself, or hope that someone with more technical expertise in the material does it for me, and announces their verdict in a forum where I can hear about it.
The polynomial solution of graph isomorphism problem is obtained by consideration symmetry properties of regular $k$-partitions that, on one hand, generalize automorphic $k$-partitions (=systems of $k$-orbits of permutation groups), and, on other hand, schemes of relations (strongly regular 2-partitions or regular 3-partitions), that are a subject of the algebraic combinatorics.Although I appreciate the value of the arXiv, there are some things about it that I still don't get.
Take the paper excerpted above. It claims to solve graph isomorphism in polynomial time, a result that if true would be quite momentous. The abstract already warns me that the technical material would be complex, and (call me parochial, shallow, what-have-you) the complete absence of grammatical structure does raise some tiny red flags.
So where does this leave me ? I'd like to know whether there is any merit to this paper. In the absence of peer review, I'd have to wade through it myself, or hope that someone with more technical expertise in the material does it for me, and announces their verdict in a forum where I can hear about it.
Monday, July 24, 2006
Where duality helps
If you do geometry (or approximation algorithms, for that matter) long enough, it becomes second nature to flip between primal and dual space. Points become hyperplanes, convex hulls become envelopes, and so on.
Here's a question that has been puzzling me: What is a good example of a problem where flipping between primal and dual (or even just going from one to the other) is the key to its solution ? Now obviously, there are NP-hard problems that admit a primal-dual solution, where by definition we need the dual space. I don't mean these kinds of problems.
I'm merely wondering if there is a relatively simple problem with a relatively simple solution that would be hard to explain without duality. The easiest that comes to mind is how the complexity of the convex hull in 3D is linear (because the complexity of the lower envelope in 3D is linear). Another potential example is the rotating calipers method for finding diameter/width etc: it can be much easier to see what's going on in the dual space.
Here's a question that has been puzzling me: What is a good example of a problem where flipping between primal and dual (or even just going from one to the other) is the key to its solution ? Now obviously, there are NP-hard problems that admit a primal-dual solution, where by definition we need the dual space. I don't mean these kinds of problems.
I'm merely wondering if there is a relatively simple problem with a relatively simple solution that would be hard to explain without duality. The easiest that comes to mind is how the complexity of the convex hull in 3D is linear (because the complexity of the lower envelope in 3D is linear). Another potential example is the rotating calipers method for finding diameter/width etc: it can be much easier to see what's going on in the dual space.
Tuesday, July 18, 2006
Windows and Linux, side by side
Captain's log, Sector 43, 3rd Quadrant, HELL. Temperature, -19 F:
Microsoft Corp. on Monday said it is teaming up with Linux supplier XenSource to allow computers to run the upcoming version of Microsoft's Windows server operating system on computers that are simultaneously running Linux software.In the latest sign that it is dropping its resistance to Linux, Microsoft of Redmond, Washington is teaming up with Palo Alto, California-based XenSource to compete with VMware, now the biggest supplier of so-called ``virtualization'' software.
Friday, July 14, 2006
Thursday, July 13, 2006
Visa problems when travelling to the US ?
John Langford advertises an effort to document cases of visa problems for researchers trying to enter the US.
A serious effort is under way to raise this as in issue in need of fixing. Over the long term, effectively driving research conferences to locate outside of the US seems an unwise policy. Robert Schapire is planning to talk to a congressman. Sally Goldman suggested putting together a list of problem cases, and Phil Long setup an email address immigration.and.confs@gmail.com to collect them.I'll second that. DON'T BE SHY. Efforts like this can actually work, and what makes them happen is access to the right people, and a good set of cases to fight for. The more cases there are (and all of us know of at least a few), the more powerful an argument we have. So please send mail to the above address.
If you (or someone you know) has had insurmountable difficulties reaching a conference in the US, please send an email with:
Name:
Email address:
Conference:
Difficulty:
Details: (be brief please)
We expect most of the problem cases are students, so don’t be shy.
Tuesday, July 11, 2006
7 blasts in Bombay
Developing...
all blasts along the Western Railway, in first-class compartments during the evening rush hour (around 1830). Death tolls are unconfirmed, but expected to be high. Mumbai Help is the central information source right now.
all blasts along the Western Railway, in first-class compartments during the evening rush hour (around 1830). Death tolls are unconfirmed, but expected to be high. Mumbai Help is the central information source right now.
Friday, July 07, 2006
EurekaUK: Great discoveres coming out of Britain in the last 50 years.
An interesting list, and this item was interesting:
I grew up thinking that one of ENIAC/EDSAC/EDVAC was the first stored-program computer. It turns out that ENIAC came close to being one, but didn't. There's more info at Wikipedia. According to Wikipedia, the Manchester "Baby" was developed in 1948, which was more than 50 years ago :)
Section four: Discoveries for the digital age
Manchester: birth of the first working computer
Two University of Manchester scientists, Freddie Williams and Tom Kilburn, are credited with running the world's first stored program computer.
I grew up thinking that one of ENIAC/EDSAC/EDVAC was the first stored-program computer. It turns out that ENIAC came close to being one, but didn't. There's more info at Wikipedia. According to Wikipedia, the Manchester "Baby" was developed in 1948, which was more than 50 years ago :)
SODA submits: stunning drop
Muthu announces that there were 380 submissions at SODA this year. This is a stunning drop: last year, some 450 were submitted, and the year before, 487 (although many of those were short papers). This is the lowest submission count since 2002, coinciding with a much-larger-than-normal increase in the committee size.
Wednesday, June 28, 2006
FOCS 2006
So the FOCS paper list is out, and it appears that there are a number of very interesting (geometry) papers on the list. I'll have to wait till people start putting papers online to actually comment on them, but I'd say that even looking at geometry alone, there appear to some very interesting papers, on point location, the upper bound theorem, clustering and k-means, and algorithms for hyperbolic spaces.
Wednesday, June 21, 2006
Breaking news: soccer balls no longer polyhedral !
The soccer ball provides a great example of Euler's formula (I'm told it's also fun to kick it around and stuff). It consists of 20 hexagons and 12 pentagons, and a standard question one can ask is: why can't we tile the whole surface with hexagons ? This shape is also called the Buckyball, and is a special case of a carbon allotrope called a fullerene.
Apparently, the soccer balls being used at the World Cup are no longer polyhedral. They consist of 14 pieces, many of which look a lot like the squashed oval shape you see on tennis balls and baseballs. This makes the ball rounder and faster, and apparently gives it baseball-like effects when moving through the air. Players (and especially goalkeepers) have been complaining about this, but then they complain every World Cup, so....
Apparently, the soccer balls being used at the World Cup are no longer polyhedral. They consist of 14 pieces, many of which look a lot like the squashed oval shape you see on tennis balls and baseballs. This makes the ball rounder and faster, and apparently gives it baseball-like effects when moving through the air. Players (and especially goalkeepers) have been complaining about this, but then they complain every World Cup, so....
Tuesday, June 20, 2006
Changing the way power-law research is done.
From time to time, I have had Michael Mitzenmacher comment on issues relating to power-law research. Michael now has an editorial in the latest issue of Internet Mathematics, on new directions for power-law research.
I highly recommend reading it, whether you work in this area or not. It addresses the main point that has always made me uncomfortable about power-law research: that almost anything looks like a power-law if you squint hard enough. Michael makes the argument that
I highly recommend reading it, whether you work in this area or not. It addresses the main point that has always made me uncomfortable about power-law research: that almost anything looks like a power-law if you squint hard enough. Michael makes the argument that
while numerous models that yield power law behavior have been suggested, and in fact the number of such models continues to grow rapidly, no general mechanisms or approaches have been suggested that allow one to validate that a suggested model is appropriate.There is a larger point here about "algorithms on data" and "algorithms on structures" that I want to talk about, but I'll keep that for a later post.
Wednesday, June 14, 2006
All very blunt-rollin' shiznit
Dick Karp recommends: "Keep the party crackin while I'm steady rappin':"
Lance Fortnow is stoked. "Real niggas recognize the realness"
Ok, maybe not.
Lance Fortnow is stoked. "Real niggas recognize the realness"
Ok, maybe not.
Tuesday, June 13, 2006
SoCG 2006: The "shape" of things to come...
Sedona is very hot. Not hot enough to fry an egg on the pavement, but still very hot. Hot enough that any hiking activities must be conducted at 5:30 AM or so, so that one may be back in one's air-conditioned ozone-layer killing hotel by 7:45 or so, when things really start heating up.
On Monday, a bunch of us had hiked out to the Bell Rock, a rather large bell-shaped rock near the hotel. On Wednesday (I was too cowardly to brave the elements on Tuesday), we decided to climb as far up the rock as we could go. Lest you think that I am some kind of rock climbing savant, I will assure you that no such thing is true. The rocks were rough enough and the trails well marked enough that we could get pretty high up without needing technical apparatus of any kind.
Here, in all its beauty, is Bell Rock:
From this angle, it's hard to explain how high we got, but it was high enough :). It started raining as we descended. The rocks proceeded to get very slick, but in every other way the rain was highly welcome. The rest of the morning was pleasantly cool as a result; so much so that it was hard to stay indoors and attend the first session.
Even though it was day 3 of the conference, which usually means my brain is fried and I am longing to return home, I really wanted to attend the first session. You see, this session was one of many on the burgeoning area of computational topology, a topic that now has a significant presence within computational geometry.
In a sense, there is no surprise that computational topology has become an important area. One of the main application areas of geometry is the understanding of shape, whether it be the triangulated meshes that constitute shapes in an animation, or the intricate surfaces induced by electrostatic forces at the surface of a protein molecule.
Topology provides much of the underlying mathematics of shape. Not all of it: metric properties of the shape are obviously important. But a good deal of it. A classic example of this is the following question:
Much work at this year's SoCG was on new sampling criteria and new ways of representing the medial axis (an important structure that acts as a kind of "skeleton" of a shape). In other words, the mathematics and the algorithmics of reconstructing shapes.
Another thread of work is on a notion called 'persistence'. Persistence is a little tricky to define intuitively (and I strongly recommend Afra Zomorodian's excellent monograph), but the basic idea is that you first create a sequence of evolving structures for a shape. One example of this could be the level sets of a terrain as you increase the "level". Then, you look for features that are "long-lasting", or "persistent" within this sequence. Such features are likely to be more permanent parts of the shape, and can be used to identify key parts of the shape. Much work has now gone into computing persistence, doing it in a stable fashion, and trying to generalize it in various settings.
In general, persistence is a way of identifying important elements of a shape, and can often be a "subroutine" in higher level topological analysis of shape.
A third thread that's somewhat distinct from the above, but deals squarely with "algorithmic topology" is exemplified by work on computing paths on shapes of different topological characteristics. Applications of this work are less immediate, but one can imagine using such algorithms to deal with the manifolds generated via surface reconstruction etc. I'm sure Jeff Erickson has more to say about this.
To work in this area, you need a very good grasp of topology (combinatorial, algebraic), some Morse theory, and of course good algorithmic and geometric intuition. The first two topics are not usually covered in a graduate degree in algorithms, and that makes this field a bit harder to get into, but its ranks are growing.
Computational topology is definitely a new and challenging direction in geometry. I wouldn't be surprised if it ended up having its own conference sooner or later: I hope not though. The cross-fertilization between topology and more traditional computational geometry is one of the more interesting trends in the field right now.
On Monday, a bunch of us had hiked out to the Bell Rock, a rather large bell-shaped rock near the hotel. On Wednesday (I was too cowardly to brave the elements on Tuesday), we decided to climb as far up the rock as we could go. Lest you think that I am some kind of rock climbing savant, I will assure you that no such thing is true. The rocks were rough enough and the trails well marked enough that we could get pretty high up without needing technical apparatus of any kind.
Here, in all its beauty, is Bell Rock:
From this angle, it's hard to explain how high we got, but it was high enough :). It started raining as we descended. The rocks proceeded to get very slick, but in every other way the rain was highly welcome. The rest of the morning was pleasantly cool as a result; so much so that it was hard to stay indoors and attend the first session.
Even though it was day 3 of the conference, which usually means my brain is fried and I am longing to return home, I really wanted to attend the first session. You see, this session was one of many on the burgeoning area of computational topology, a topic that now has a significant presence within computational geometry.
In a sense, there is no surprise that computational topology has become an important area. One of the main application areas of geometry is the understanding of shape, whether it be the triangulated meshes that constitute shapes in an animation, or the intricate surfaces induced by electrostatic forces at the surface of a protein molecule.
Topology provides much of the underlying mathematics of shape. Not all of it: metric properties of the shape are obviously important. But a good deal of it. A classic example of this is the following question:
given points sampled from a shape, under what conditions can I reconstruct a shape that is geometrically and topologically similar to the original shape ?Many results over the years have attempted to answer this question via "sampling criteria" of the form, "if you sample points so that they satisfy some condition SC, then there's an algorithm that will correctly reconstruct the shape within some error bounds". The goal is to get as relaxed conditions SC as possible, given that we often don't have control over the sampling process.
Much work at this year's SoCG was on new sampling criteria and new ways of representing the medial axis (an important structure that acts as a kind of "skeleton" of a shape). In other words, the mathematics and the algorithmics of reconstructing shapes.
Another thread of work is on a notion called 'persistence'. Persistence is a little tricky to define intuitively (and I strongly recommend Afra Zomorodian's excellent monograph), but the basic idea is that you first create a sequence of evolving structures for a shape. One example of this could be the level sets of a terrain as you increase the "level". Then, you look for features that are "long-lasting", or "persistent" within this sequence. Such features are likely to be more permanent parts of the shape, and can be used to identify key parts of the shape. Much work has now gone into computing persistence, doing it in a stable fashion, and trying to generalize it in various settings.
In general, persistence is a way of identifying important elements of a shape, and can often be a "subroutine" in higher level topological analysis of shape.
A third thread that's somewhat distinct from the above, but deals squarely with "algorithmic topology" is exemplified by work on computing paths on shapes of different topological characteristics. Applications of this work are less immediate, but one can imagine using such algorithms to deal with the manifolds generated via surface reconstruction etc. I'm sure Jeff Erickson has more to say about this.
To work in this area, you need a very good grasp of topology (combinatorial, algebraic), some Morse theory, and of course good algorithmic and geometric intuition. The first two topics are not usually covered in a graduate degree in algorithms, and that makes this field a bit harder to get into, but its ranks are growing.
Computational topology is definitely a new and challenging direction in geometry. I wouldn't be surprised if it ended up having its own conference sooner or later: I hope not though. The cross-fertilization between topology and more traditional computational geometry is one of the more interesting trends in the field right now.
Euler meets Homer... D'oh !
More news on Jeff Westbrook, our theory "mole" inside Hollywood (He's not Jennifer Garner, but he does just fine). Jeff now writes for the Simpsons, and is apparently trying to get an Euler's theorem reference into the show.
(HT: David Poole via Chris Volinsky)
(HT: David Poole via Chris Volinsky)
Monday, June 12, 2006
India: the old, and the new.
Indians are a traditional lot, in more ways than one. While here in Amreeka, NBA/NFL/MLB stars have to deal with the "problem" of women throwing themselves at them (ok, so maybe Wilt and Shawn Kemp don't deal too well with it), Indian sports stars have more traditional problems:
On the other hand, Indians are savvy with cutting-edge technology. While senators in the US need to be sent iPods so they might understand what MP3 players are, Indian industrialists are way more advanced:
(HT: India Uncut and Sepia Mutiny)
Though India's new batting sensation Mahendra Singh Dhoni is Jharkhand's most eligible bachelor, his family say that he has no intention of getting married for at least another three years as his mind right now is only on cricket.
According to his members, Dhoni, started getting marriage proposals when he played for the country and these proposals multiplied ten folds when he scored 148 against Pakistan at Vishakapatnam earlier this year.
After his unbeaten 183 against Sri Lanka at Jaipur and another unbeaten 45 at Pune he has been flooded with marriage proposals but he has no plans of settling down yet and will only think of marriage after another three years, a family member said.
On the other hand, Indians are savvy with cutting-edge technology. While senators in the US need to be sent iPods so they might understand what MP3 players are, Indian industrialists are way more advanced:
Concealing secret transactions in pen-drives and iPods is fast catching up as a trend, say income tax and Directorate of Revenue Intelligence officials, who now take special care to seize these devices before laying hands on account books and computers during a raid. The internet too is a favoured hideaway for tax-evaders, who post details of illegal accounts on the web before deleting these files from their records.The land of contradictions indeed....(p.s Sariel, careful what you do with your iPod :))
Though these gizmos are small enough to fit into a shirt pocket, they have immense memory ^ ranging from 1 to 30 giga bytes. They are also very easy to discard. Officials believe that during many raids, pen-drives have been put into burning furnaces, crushed under car wheels or simply thrown into dustbins. In one case, a pen-drive was recovered from the driver of an accused.
(HT: India Uncut and Sepia Mutiny)
The proof of Fermat's theorem is a "Rube Goldberg contraption"
Doron Zeilberger does not pull his punches:
All that Andrew Wiles did, in his FLT proof, was solve one problem, using ad hoc arguments, that depend on historical contingencies of what was proved before. It is a huge Rube Goldberg contraption, that is unlikely to lead to anything further of any significance, just more of the same human drivel.In context, he is talking about the importance of computer-generated proofs. Read the whole article.
Saturday, June 10, 2006
SoCG 2006: Overlays of Minimization Diagrams
Tuesday was the day of the banquet. The "banquet" was a jeep tour of Sedona, ending at Sedona airport (on a hill. I repeat: Sedona airport is on a hill). The overlook near the airport is a great place to see the sunset (in principle, but more on that later), and looks out over the entire town.
The jeeps are open-air seven-seaters, the kind of "SUV" that was really designed for offroading, Trust me when I tell you that none of the wimpy SUVs you see on the road would have survived the bone-rattling trip we took. As I said to someone later on, it was like going on a roller coaster over a discontinous function.
The usual tourist patter aside, it was a great ride. 5 of the jeeps took a more "rugged" ride, and although all my bones were aching the next day, it was worth it ! This ranks up there with the S0CG 2004 Manhattan cruise-with-open-bar (yes, geometers do have too much fun).
And now, back to business. The featured paper of the day is 'Overlays of Minimization Diagrams' by Vladlen Koltun and Micha Sharir.
The lower envelope of an arrangement of entities in R^d (the set of entities you hit first as you move upwards from z = -infinity) is a very important structure in geometry. Many optimization problems can be expressed as searches over a suitably defined lower (or upper) envelope, or combinations thereof. A minimization diagram is what you get when you project the lower envelope onto the underlying domain one dimension lower. The best example of this is a Voronoi diagram of points, which as we all know is the projection of the lower envelope of an arrangement of suitably defined cones.
What do you get if you take two such minimization diagrams and put them on each other ? This overlay, which itself is another subdivision of space, is also useful in geometric optimization. The canonical example here is the computation of a minimum width annulus of a set of points. I'd like to find a center, and two concentric circles of radius r and R, so that all the points in my input are enclosed between the two circles, and R-r is as small as possible.
This problem is a robust version of circle fitting, or checking how close points are to a circular shape. It's not hard to see that what you need is a large empty circle, and a small enclosing ball, both centered at the same point. Any vertex of a Voronoi diagram gives you a large empty circle (in fact, a maximal empty circle). If you computed a "farthest-point" Voronoi diagram, i.e a minimization diagram from the upper envelope, you'd get candidates for the smallest enclosing ball. It turns out that the center of the optimal minimum width annulus must be a vertex of the overlay of these two minimization diagrams.
As with many geometry problems, we quickly go from searching to counting, from "find the optimal x satisfying property P" to "Enumerate all the x that can satisfy property P". The question in this case is: What is the complexity of the overlay of two minimization diagrams ?
Of course, a more basic question is: what is the complexity of one minimization diagram ? For the case of hyperplane arrangements, the answer follows from the famous Upper Bound Theorem of McMullen from 1970:
The key lemma that establishes this fact is very simple; indeed the authors express surprise that this lemma hasn't been observed before. It involves a "reversal of operators": namely, that the overlay of minimization diagrams can be expressed as a minimization of overlays.
More formally,
The jeeps are open-air seven-seaters, the kind of "SUV" that was really designed for offroading, Trust me when I tell you that none of the wimpy SUVs you see on the road would have survived the bone-rattling trip we took. As I said to someone later on, it was like going on a roller coaster over a discontinous function.
The usual tourist patter aside, it was a great ride. 5 of the jeeps took a more "rugged" ride, and although all my bones were aching the next day, it was worth it ! This ranks up there with the S0CG 2004 Manhattan cruise-with-open-bar (yes, geometers do have too much fun).
And now, back to business. The featured paper of the day is 'Overlays of Minimization Diagrams' by Vladlen Koltun and Micha Sharir.
The lower envelope of an arrangement of entities in R^d (the set of entities you hit first as you move upwards from z = -infinity) is a very important structure in geometry. Many optimization problems can be expressed as searches over a suitably defined lower (or upper) envelope, or combinations thereof. A minimization diagram is what you get when you project the lower envelope onto the underlying domain one dimension lower. The best example of this is a Voronoi diagram of points, which as we all know is the projection of the lower envelope of an arrangement of suitably defined cones.
What do you get if you take two such minimization diagrams and put them on each other ? This overlay, which itself is another subdivision of space, is also useful in geometric optimization. The canonical example here is the computation of a minimum width annulus of a set of points. I'd like to find a center, and two concentric circles of radius r and R, so that all the points in my input are enclosed between the two circles, and R-r is as small as possible.
This problem is a robust version of circle fitting, or checking how close points are to a circular shape. It's not hard to see that what you need is a large empty circle, and a small enclosing ball, both centered at the same point. Any vertex of a Voronoi diagram gives you a large empty circle (in fact, a maximal empty circle). If you computed a "farthest-point" Voronoi diagram, i.e a minimization diagram from the upper envelope, you'd get candidates for the smallest enclosing ball. It turns out that the center of the optimal minimum width annulus must be a vertex of the overlay of these two minimization diagrams.
As with many geometry problems, we quickly go from searching to counting, from "find the optimal x satisfying property P" to "Enumerate all the x that can satisfy property P". The question in this case is: What is the complexity of the overlay of two minimization diagrams ?
Of course, a more basic question is: what is the complexity of one minimization diagram ? For the case of hyperplane arrangements, the answer follows from the famous Upper Bound Theorem of McMullen from 1970:
The complexity of the lower envelope of a collection of n hyperplanes in d dimensions is n⌊d/2⌋.Given this, an easy bound on the overlay of two such diagrams would be n2 * ⌊d/2⌋, merely by observing that every intersection of two features creates a new feature. The main result of this paper is that the correct answer is much smaller:
The complexity of the overlay of two minimization diagrams for collections of n hyperplanes in d dimensions is n⌈d/2⌉.Note the flip from floor to ceiling. This creates some unusual effects; the complexity of the overlay of two minimization diagrams in odd dimensions has the same complexity as that of one such diagram; in even dimensions, the difference is one (remember that the minimization diagram inhabits one fewer dimension than the arrangement of hyperplanes defining it).
The key lemma that establishes this fact is very simple; indeed the authors express surprise that this lemma hasn't been observed before. It involves a "reversal of operators": namely, that the overlay of minimization diagrams can be expressed as a minimization of overlays.
More formally,
The overlay of two minimization diagrams of n d-variate functions is isomorphic to a subset of the minimization diagram of 2n d+1-variate functions.The result above extends to 2 <= m <= d. Similar results also hold for arrangements of simplices, or of constant-degree algebraic functions. They all follow almost directly from the above lemma.
Thursday, June 08, 2006
SoCG 2006: Locality Sensitive Hashing.
After many years of lugging a laptop around with me at conferences, I decided to leave it in the room this time. It helps immensely with my focus during talks, and even helps during the breaks, when I can either talk to people or read the proceedings, rather than check email ... and the web ... and some blogs ... and oops ! one session's blown away.
One of the more notable talks I heard on Tuesday was by Rina Panigrahy on a new lower bound for locality-sensitive hashing by Rajeev Motwani, Assaf Naor and himself.
Locality-sensitive hashing is a suprisingly effective "geometric" analogue of hashing first developed by Piotr Indyk and Rajeev Motwani. In standard hashing, the goal is to maintain a set of elements S drawn from a large universe U so that you can answer the question "is i in S" really quickly. Because U is typically much larger than S, what you'd like is a storage structure that uses space proportional to the size of S, rather than the size of U (which would be easy to do).
Hashing is one of the most elegant, profound and practical ideas to come out of the study of algorithms and data structures. It's almost impossible to find any serious program that doesn't need some kind of hash data structure. A detailed post on hashing will have to wait for another day though..
Locality-sensitive hashing is a way to take hashing to a geometric arena (you knew geometry had to show up sooner or later). Suppose that instead of merely having a set of elements from a universe, I had a set of points in a metric space. For example, maybe I have points situated in 1o-dimensional space with the normal Euclidean distance.
My goal is the same: I want to store points from the space in a data structure so I can ask the question: "is i in S ?". But now that points have distances between them, I can ask the related question, "is i near some point of S ?". Locality-sensitive hashing gives you a data structure that answers such questions approximately. More precisely, given parameters c, r, p, q, the structure guarantees that if two elements are within distance r of each other, then they are hashed to the same bucket with probability p, and if they are further than c * r, then this happens with probability q. In general, you want p to be much larger than q of course, and you'd like c to be as close to 1 as possible.
The actual construction is quite simple (you create a collection of hash functions and map each point to a vector of hash values), and has had numerous applications. What controls the efficacy of the scheme is the parameter r = log(1/p)/log(1/q), which affects both the space and time bounds of the algorithm; the smaller r is, the better. Roughly speaking, the space required by an algorithm is n^(1+r) and the query time is n^r.
Since c controls the quality of the hash, and r controls its efficiency, these two parameters vary inversely. In fact, for l1, it was shown earlier that r <= 1/c. What this paper shows is that for any lp norm, r >= 0.462/cp. Specifically, this means that the bound for l1 is almost tight. Together with new work by Andoni and Indyk showing that LSH for l2 can be done with r <= 1/c2, this gives almost matching upper and lower bounds for LSH for a range of norms.
It's a very nice result, and quite simple. In fact, for those who grumble that papers with few pages are not viewed kindly by PCs, this paper is only 4 pages long.
Update (6/11/06): As Piotr points out in the comments, the bounds are not quite matched. There is a constant factor gap between the upper and lower bounds, and thus some more work to do. Damn you, big-O notation !!!
One of the more notable talks I heard on Tuesday was by Rina Panigrahy on a new lower bound for locality-sensitive hashing by Rajeev Motwani, Assaf Naor and himself.
Locality-sensitive hashing is a suprisingly effective "geometric" analogue of hashing first developed by Piotr Indyk and Rajeev Motwani. In standard hashing, the goal is to maintain a set of elements S drawn from a large universe U so that you can answer the question "is i in S" really quickly. Because U is typically much larger than S, what you'd like is a storage structure that uses space proportional to the size of S, rather than the size of U (which would be easy to do).
Hashing is one of the most elegant, profound and practical ideas to come out of the study of algorithms and data structures. It's almost impossible to find any serious program that doesn't need some kind of hash data structure. A detailed post on hashing will have to wait for another day though..
Locality-sensitive hashing is a way to take hashing to a geometric arena (you knew geometry had to show up sooner or later). Suppose that instead of merely having a set of elements from a universe, I had a set of points in a metric space. For example, maybe I have points situated in 1o-dimensional space with the normal Euclidean distance.
My goal is the same: I want to store points from the space in a data structure so I can ask the question: "is i in S ?". But now that points have distances between them, I can ask the related question, "is i near some point of S ?". Locality-sensitive hashing gives you a data structure that answers such questions approximately. More precisely, given parameters c, r, p, q, the structure guarantees that if two elements are within distance r of each other, then they are hashed to the same bucket with probability p, and if they are further than c * r, then this happens with probability q. In general, you want p to be much larger than q of course, and you'd like c to be as close to 1 as possible.
The actual construction is quite simple (you create a collection of hash functions and map each point to a vector of hash values), and has had numerous applications. What controls the efficacy of the scheme is the parameter r = log(1/p)/log(1/q), which affects both the space and time bounds of the algorithm; the smaller r is, the better. Roughly speaking, the space required by an algorithm is n^(1+r) and the query time is n^r.
Since c controls the quality of the hash, and r controls its efficiency, these two parameters vary inversely. In fact, for l1, it was shown earlier that r <= 1/c. What this paper shows is that for any lp norm, r >= 0.462/cp. Specifically, this means that the bound for l1 is almost tight. Together with new work by Andoni and Indyk showing that LSH for l2 can be done with r <= 1/c2, this gives almost matching upper and lower bounds for LSH for a range of norms.
It's a very nice result, and quite simple. In fact, for those who grumble that papers with few pages are not viewed kindly by PCs, this paper is only 4 pages long.
Update (6/11/06): As Piotr points out in the comments, the bounds are not quite matched. There is a constant factor gap between the upper and lower bounds, and thus some more work to do. Damn you, big-O notation !!!
Tuesday, June 06, 2006
SoCG 2006: Day 1 - Da Bizness...
So Jeff Erickson, while not even being here, managed to post a fairly accurate rendition of the SoCG business meeting. This of course means one of two things:
The Erickson-meeting was far more entertaining than the poor substitute for fiction that the real meeting was. However, since I am a dedicated worker bee in this community, I will attempt to add some truthiness to his description.
The heat: It is so hot that apparently someone stole the free sunscreen that the organizers had placed on the registration table. Carola made a plaintive plea for its return. Alon (very defensively) claimed that he didn't expect the weather. To which I say, NO ONE EXPECTS THE WEATHER. It's THREE main weapons are surprise, unpredictability, .... oh never mind.
The drinks: We had drink statistics ! as you might suspect, we are a bunch of effete snobs who only drink imported beer.
PC Stats: Papers get in if you write them on folding, sensors, blah blah, 3-4 authors good, blah blah.
Aren't PC stats fun ?
Next year: In Gyeongju, which we are told repeatedly is the old capital of Korea. It is "apparently" easier to get to than Sedona. You
2008:
Who won ? oh yeah, it was DC, 45/28.
General discussion:
The most listless general discussion section EVAH ! Pankaj, John Hershberger and Carola tried valiantly to create controversy over parallel sessions, and the rest of us drink our imported beers and say 'Pfeh'. Thankfully this ends quickly, with no resolution (What! what did you expect?) and this sad spectacle comes to an end.
I feel nostalgic for short papers.
- Jeff, having spent many many years attending SoCG, has a keen sense of the pulse of the community and can distill out its essence.
- SoCG business meetings are really boring and predictable.
The Erickson-meeting was far more entertaining than the poor substitute for fiction that the real meeting was. However, since I am a dedicated worker bee in this community, I will attempt to add some truthiness to his description.
The heat: It is so hot that apparently someone stole the free sunscreen that the organizers had placed on the registration table. Carola made a plaintive plea for its return. Alon (very defensively) claimed that he didn't expect the weather. To which I say, NO ONE EXPECTS THE WEATHER. It's THREE main weapons are surprise, unpredictability, .... oh never mind.
The drinks: We had drink statistics ! as you might suspect, we are a bunch of effete snobs who only drink imported beer.
PC Stats: Papers get in if you write them on folding, sensors, blah blah, 3-4 authors good, blah blah.
Aren't PC stats fun ?
Next year: In Gyeongju, which we are told repeatedly is the old capital of Korea. It is "apparently" easier to get to than Sedona. You
- Fly to Incheon airport (50 bajillion hours)
- Take a bus to Seoul (1 hour)
- Take a train to Gyeongju (3 hours by super-fast-your-teeth-will-ache train, 5 hours by lets-stop-and-pick-pickled-cabbage train)
2008:
- David Mount for DC: I hope someone comes up with a better bid than this
- Tamal Dey for OSU, looking at his PR material: Is this really Columbus ?
Who won ? oh yeah, it was DC, 45/28.
General discussion:
The most listless general discussion section EVAH ! Pankaj, John Hershberger and Carola tried valiantly to create controversy over parallel sessions, and the rest of us drink our imported beers and say 'Pfeh'. Thankfully this ends quickly, with no resolution (What! what did you expect?) and this sad spectacle comes to an end.
I feel nostalgic for short papers.
Sunday, June 04, 2006
SoCG 2006: Day 0
"God made the Grand Canyon, but He lives in Sedona"I heard this from a fellow passenger on the shuttle from Phoenix to Sedona. It might overstate the case slightly, but Sedona is indeed gorgeous. The Hilton Resort faces the main red rock formations, and my room has a gorgeous view (no pictures, because I neglected to bring my camera download dongle).
It is very very hot here. People think that because I'm Indian, I have no business complaining about the heat or worse, that I should enjoy the heat ! I point out that because I'm Indian, I have a healthy respect for heat and spend my time as far away from it as possible. The low temperature here is higher than the highs when I was in Zurich a week ago. Yikes !
As a consequence, even simple things like taking a walk are tricky. I wanted to walk up to the Bell Rock, one of the standout examples of the red rock formations. It's a mile away, and quite doable under normal circumstances.
Alas, these are anything but normal circumstances. The concierge gave me the 'crazy foreigner' look when I proposed my plan. She did recommend that I try getting up at dawn and walking over, when it's cooler. I might actually do that, for the second time in my life (the first time was in Zion National Park, and the trek was well worth it).
It's hard to get around without a car. In fact, I wonder if this might actually not be an excellent place for the American equivalent of the Dagstuhl/Bertinoro/Oberwolfach workshops. It's hard to get around anyway, and in the summer you wouldn't want to !
Saturday, June 03, 2006
Idempotence and Corners: A new "angle" on range searching.
Range searching is probably the most well explored area in computational geometry, and one that has led to the richest array of techniques, both for upper bounds and lower bounds.
The problem itself is very easy to state. You're given points in a range, and a query from a family of ranges. Find all points contained in the range, and report the set of points (searching), the cardinality of points (counting) or even whether the range is non-empty (emptiness).
If one defines an appropriate commutative semigroup, then all of the above formulations can be captured by the same basic problem. Given a mapping w from points to the semigroup, compute the sum (with respect to the semigroup) of w(p) for all points in the range. Searching maps to the union operation, counting to addition, and emptiness to the OR function.
Most results in range searching are phrased in terms of space-time tradeoffs: if you are willing to pay m space, what is the query time as a function of m and n, the number of points ? The interesting points are at the extremes: If you want logarithmic query time (this ignores the time to output the search results, or you can consider counting queries), then you need polynomial space, and if you want linear space, then you'll end up with near-linear query time.
A flurry of results starting in the late 80s and culminating in the early 90s resolved most of the open problems in range searching, especially for the challenging simplex (or halfspace) range searching problems. The survey by Agarwal and Erickson has more details.
For all intents and purposes, this area appeared be to a closed one. More recently, there was work on tradeoffs for approximate range searching (when you might allow points that are "near" the range to be included in the answer). Here, it was possible to transfer the high complexity from terms involving n (or d) to terms involving epsilon, the error parameter (again, I oversimplify; see here and here for more details).
Recently though, two papers by Arya, Malamatos and Mount appear to have opened up some new angles (pun intended) to range searching. The first paper (which appeared in STOC this year) is titled, in Wildesque fashion, 'On the Importance of Idempotence".
The premise is neat: in all the upper and lower bounds for range searching, the group structure is not explored in any particular way (for technical reasons, the group must be a "faithful semigroup", but that's it). What they show in their paper is that for exact range searching to a degree, and more importantly for approximate range searching, the group structure can change the bounds. Specifically, if the group operation is idempotent, i.e a + a = a, then the (matching) upper and lower bounds for approximate range searching reduce to the square root of their previous values (i.e by a factor of 2 in the exponent). Idempotent group operators include min (used to find the smallest element in a range) and OR (to check range emptiness).
[Aside]
What's really interesting about this is that idempotence itself can be viewed as a limit of a "dequantization process" over integral domains. One example of this is how the field (R, max,+) can be retrieved from the field (R, +, *) (there are some technical details needed) by using the mapping x -> 1/h ln(x), as h tends to infinity. The question is then: can the difference between the idempotent and integral bounds on range searching be viewed as two points on a continuum parameterized by such a parameter ?
There's a lot of work out there on idempotence, so-called "tropical mathematics", and the relation between quantum and classical phenomena. All very interesting stuff.
[End Aside]
In a paper coming up at SoCG, Arya, Malamatos and Mount go one step further. They further show that the shape of the ranges is also very important. Their earlier results on idempotence were for ball queries: in this paper they show that if the queries are angular (like rectangles), then the separation between idempotent and integral semigroups doesn't quite show up, and that smooth, well rounded queries (like balls) are needed for this to work.
The problem itself is very easy to state. You're given points in a range, and a query from a family of ranges. Find all points contained in the range, and report the set of points (searching), the cardinality of points (counting) or even whether the range is non-empty (emptiness).
If one defines an appropriate commutative semigroup, then all of the above formulations can be captured by the same basic problem. Given a mapping w from points to the semigroup, compute the sum (with respect to the semigroup) of w(p) for all points in the range. Searching maps to the union operation, counting to addition, and emptiness to the OR function.
Most results in range searching are phrased in terms of space-time tradeoffs: if you are willing to pay m space, what is the query time as a function of m and n, the number of points ? The interesting points are at the extremes: If you want logarithmic query time (this ignores the time to output the search results, or you can consider counting queries), then you need polynomial space, and if you want linear space, then you'll end up with near-linear query time.
A flurry of results starting in the late 80s and culminating in the early 90s resolved most of the open problems in range searching, especially for the challenging simplex (or halfspace) range searching problems. The survey by Agarwal and Erickson has more details.
For all intents and purposes, this area appeared be to a closed one. More recently, there was work on tradeoffs for approximate range searching (when you might allow points that are "near" the range to be included in the answer). Here, it was possible to transfer the high complexity from terms involving n (or d) to terms involving epsilon, the error parameter (again, I oversimplify; see here and here for more details).
Recently though, two papers by Arya, Malamatos and Mount appear to have opened up some new angles (pun intended) to range searching. The first paper (which appeared in STOC this year) is titled, in Wildesque fashion, 'On the Importance of Idempotence".
The premise is neat: in all the upper and lower bounds for range searching, the group structure is not explored in any particular way (for technical reasons, the group must be a "faithful semigroup", but that's it). What they show in their paper is that for exact range searching to a degree, and more importantly for approximate range searching, the group structure can change the bounds. Specifically, if the group operation is idempotent, i.e a + a = a, then the (matching) upper and lower bounds for approximate range searching reduce to the square root of their previous values (i.e by a factor of 2 in the exponent). Idempotent group operators include min (used to find the smallest element in a range) and OR (to check range emptiness).
[Aside]
What's really interesting about this is that idempotence itself can be viewed as a limit of a "dequantization process" over integral domains. One example of this is how the field (R, max,+) can be retrieved from the field (R, +, *) (there are some technical details needed) by using the mapping x -> 1/h ln(x), as h tends to infinity. The question is then: can the difference between the idempotent and integral bounds on range searching be viewed as two points on a continuum parameterized by such a parameter ?
There's a lot of work out there on idempotence, so-called "tropical mathematics", and the relation between quantum and classical phenomena. All very interesting stuff.
[End Aside]
In a paper coming up at SoCG, Arya, Malamatos and Mount go one step further. They further show that the shape of the ranges is also very important. Their earlier results on idempotence were for ball queries: in this paper they show that if the queries are angular (like rectangles), then the separation between idempotent and integral semigroups doesn't quite show up, and that smooth, well rounded queries (like balls) are needed for this to work.
Friday, June 02, 2006
The Great Indian Menace...
While people in this country are wailing and gnashing their teeth about the growing tech strength of India and China, folks back in the motherland are wailing and gnashing their teeth about the re-emergence of the "reservations" monster (India's answer to affirmative action). Proposals to raise the number of seats reserved for "backward castes" from its current 22.5% to 49.5% in institutions of higher learning (IITs, business schools, med schools) have caused an uproar among student bodies and faculties across the country. There's a LOT of politics swirling around this mess, and the issues are much thornier than a straight affirmative action debate, but there is genuine (if a bit unfounded) concern about the potential for "killing the golden goose" as it were.
Of course, everyone is missing a true sign of the apocalypse: a non-Indian winning the National Spelling Bee !! Five out of the last seven winners (and all four top competitors last year) were of Indian origin. But this year, the top placed finisher was 4th (and boy did he have a game face) !
I was amused (and somewhat confused) to see a Hindi word with absolutely no connection to English being used. The word was 'izzat', which means 'pride', or'honor'. Its pronounciation was of course mangled horribly: it's a wonder that the speller managed to get it right. And if one wanted to be pedantic, the word isn't even Hindi; it's Urdu.
p.s Having bought into the stereotype of spelling bee champs being these monomaniacal bottle-glass wearing loons, I was pleasantly surprised by the eventual champ, who displayed remarkable maturity and a sense of balance in her brief biopic.
Of course, everyone is missing a true sign of the apocalypse: a non-Indian winning the National Spelling Bee !! Five out of the last seven winners (and all four top competitors last year) were of Indian origin. But this year, the top placed finisher was 4th (and boy did he have a game face) !
I was amused (and somewhat confused) to see a Hindi word with absolutely no connection to English being used. The word was 'izzat', which means 'pride', or'honor'. Its pronounciation was of course mangled horribly: it's a wonder that the speller managed to get it right. And if one wanted to be pedantic, the word isn't even Hindi; it's Urdu.
p.s Having bought into the stereotype of spelling bee champs being these monomaniacal bottle-glass wearing loons, I was pleasantly surprised by the eventual champ, who displayed remarkable maturity and a sense of balance in her brief biopic.
Tuesday, May 30, 2006
Shortest Paths On Convex Polytopes
So here I am, trying to get some sausage tasting in before I leave. I'm trying to hunt down a paper by Schreiber and Sharir on computing shortest paths exactly in three dimensions on a convex polytope.
The story of this problem is interesting. If the domain is arbitrary (three dimensions with arbitrary obstacles: think of a missile flying through a city), the problem is NP-hard (which is good if you're a pacifist). If you then restrict yourself to shortest paths on a convex polytope (now you're a snake on a really nice hill, trying to find some food), then the problem becomes easier.
Eons ago (well ok, back in 1986) Sharir and Schorr gave the first polynomial time algorithm for this problem. Their solution (runnning in n3 log n time) exploited a very neat fact about shortest paths on a convex surface; the so-called "unfolding" property.
Here's where things get strange: apparently no one (except the author, I imagine) believes that the paper is correct. There are numerous details left unspecified in the conference version, (Joe O'Rourke has made an attempt to explain what's going on), and to date there has been no journal version of this paper.
Which brings us to the paper I started off with. Schreiber and Sharir have a paper in this year's SoCG that presents an optimal algorithm for the shortest path problem on convex polytopes. Their algorithm runs in n log n time. The long version of the paper is now 131 pages and counting (!), and contains in an appendix an attempt at refuting aspects of Kapoor's algorithm.
Verifying the details of this algorithm will take some time, but at least there is a fully detailed manuscript available. Perhaps this will bring to an end the mystery surrounding the true complexity of the problem.
Aside: So I do a google search for "An efficient algorithm for shortest paths on a convex polytope in three dimensions", and the top links I find are for "Approximating shortest paths on a convex polytope in three dimensions". I guess approximations are more important after all.
Update (3/26/07): I recently received the following email from Sanjiv Kapoor and am reproducing it with his permission:
The story of this problem is interesting. If the domain is arbitrary (three dimensions with arbitrary obstacles: think of a missile flying through a city), the problem is NP-hard (which is good if you're a pacifist). If you then restrict yourself to shortest paths on a convex polytope (now you're a snake on a really nice hill, trying to find some food), then the problem becomes easier.
Eons ago (well ok, back in 1986) Sharir and Schorr gave the first polynomial time algorithm for this problem. Their solution (runnning in n3 log n time) exploited a very neat fact about shortest paths on a convex surface; the so-called "unfolding" property.
suppose you draw a shortest path between two points on a convex surface, and then cut out the faces containing the path. If you unroll them onto a table, the path you drew would be a straight line. Voila !This was subsequently improved. Mount used a "continuous Djikstra" method that expanded wavefronts from the start point, shaved the running time down to n2 log n. This approach was generalized to non-convex polyhedra by Mitchell, Mount and Papadimitrious. in 1990, Chen and Han removed the log factor in the algorithm, using a different approach. That's where things stood for a long time (I'm ignoring other aspects of the story) till 1999, when Sanjeev Kapoor had a paper in STOC that claimed an n log2n running time for the problem.
Here's where things get strange: apparently no one (except the author, I imagine) believes that the paper is correct. There are numerous details left unspecified in the conference version, (Joe O'Rourke has made an attempt to explain what's going on), and to date there has been no journal version of this paper.
Which brings us to the paper I started off with. Schreiber and Sharir have a paper in this year's SoCG that presents an optimal algorithm for the shortest path problem on convex polytopes. Their algorithm runs in n log n time. The long version of the paper is now 131 pages and counting (!), and contains in an appendix an attempt at refuting aspects of Kapoor's algorithm.
Verifying the details of this algorithm will take some time, but at least there is a fully detailed manuscript available. Perhaps this will bring to an end the mystery surrounding the true complexity of the problem.
Aside: So I do a google search for "An efficient algorithm for shortest paths on a convex polytope in three dimensions", and the top links I find are for "Approximating shortest paths on a convex polytope in three dimensions". I guess approximations are more important after all.
Update (3/26/07): I recently received the following email from Sanjiv Kapoor and am reproducing it with his permission:
The single outstanding comment "apparently no one (except the author, I imagine) believes that the paper is correct" on your blog, is worrisome in its expansiveness -- (note that a blog is a public document)--He also encloses a mail from Yevgeny Schreiber which acknowledges his comments and modifies one of their examples claiming a problem with his algorithm. Yevgeny continues to mention technical details in the 1999 paper that remain unresolved, so this matter remains unsettled.
A more detailed (at least enough details from my viewpoint-) was available and never requested by anyone-- so I don't know if anyone even tried to seriously understand the method, apart from Joe O'Rourke and recentlly by SS. The only error which I myself found, has not been reported by anyone else as yet. The recent paper with Inkulu and Maheshwari gives an "improved" planar SP algorithm, which of course didnt make it to SOCG, but has crossed the 40 page single space) mark (if that is a measure of detailed correctness). In my original version I actively tried to omit all details which would require a few minutes thought--
On Zero Knowledge in Games...
I'm back now from the ESA PC meeting, not to return for at least five more years. ESA has a 'diversity' policy: no one can repeat memberships on a committee within five years (This doesn't apply to PC chairs though). Rumor has it that this is a reaction to a system where new blood wasn't coming into the conference committees at all.
I don't know if institutionalized diversity is necessarily the answer in the long term: maybe it's a good short term measure to get some new blood in. You do need some amount of continuity on committees while trying to encourage fresh participation. SODA/STOC/FOCS appears to do this reasonably well.
While catching up with my blogs (what are they putting in the water in Atlanta, anyway ?), I came across this post from Antimeta. It considers (for example) the situation when reading a letter of reference:
Seriously though, the post also talks about a paper by Edward Epsen that attempts to apply zero knowledge ideas to game theory. Specifically, the author considers a two-player setting where one player either does (is "informed") or doesn't (is "uninformed") know whether the game being played is one of k choices. The second player has a prior belief with probability q that player 1 is informed. It turns out that there's a zero knowledge protocol to drive q to 1. That is, there is a protocol that will convince player 2 that player 1 is informed about the choice of game being played without knowing which game it is.
I'm simplifying: these are games of incomplete information, where players may not even know the payoffs from their actions. According to the author, these were first used by Aumann and others to handle Cold War conflicts (one example given is: "suppose the US convinced the Soviet Union to reduce its ballistic missile stockpile by 100. What percentage of the Soviet stockpile is this?". Obviously it would be hard to determine the answer to the second question, and thus hard to determine the payoff of the first action.
I don't know if institutionalized diversity is necessarily the answer in the long term: maybe it's a good short term measure to get some new blood in. You do need some amount of continuity on committees while trying to encourage fresh participation. SODA/STOC/FOCS appears to do this reasonably well.
While catching up with my blogs (what are they putting in the water in Atlanta, anyway ?), I came across this post from Antimeta. It considers (for example) the situation when reading a letter of reference:
we were trying to figure out whether silences can carry implicatures, or more ordinarily, whether you can say something without words. And of course the answer is yes:The problem is about the communication of meaning, and the interplay with intention. Antimeta goes on to say:Q: "What do you like about John?"
A: [silence]
A is expected to make a contribution to the conversation mentioning some positive fact about John. A's silence violates the maxim of quantity (she hasn't said as much as is expected), so Q can infer that some other conversational principle (one requiring politeness) must conflict with anything that A would be in a position to say. Therefore, Q comes to believe that there is nothing (or at least nothing relevant) about John that A likes.All I can say is: Phew ! Pursuing a Ph.D program in logic and philosophy is no joke.But then I realized that we should think about this (and perhaps the original recommendation letter example) a bit more carefully. It seems that the story given above could work in at least two different ways. In one case, A is struggling for an answer, and the silence just comes about because she can't think of anything she likes about John. In the second case, A knows there is nothing she likes about John and remains actively silent. I think the second case is an example of an implicature carried by a silence, but the first is not.
The explanation of the distinction comes from Grice's earlier classic paper, "Meaning" in which he suggests that speaker A means y by utterance x iff "A intended the utterance of x to produce some effect [y] in an audience by means of recognition of this intention." He comes to this recursive intention account of meaning by way of a bunch of examples, which I think parallel the situation here. If I don't intend you to believe (or consider) something by means of my action, then I didn't mean it, even if it's true. Thus, my silence can reveal my dislike for John, just as an accidentally dropped photograph can reveal where I was the other day, but neither means it. But even just performing the action intentionally isn't enough - Grice suggests that showing someone a photograph doesn't constitute a meaning of what is depicted, because my intention plays only an unnecessary role in the observer's coming to believe the truth of what is depicted.
Seriously though, the post also talks about a paper by Edward Epsen that attempts to apply zero knowledge ideas to game theory. Specifically, the author considers a two-player setting where one player either does (is "informed") or doesn't (is "uninformed") know whether the game being played is one of k choices. The second player has a prior belief with probability q that player 1 is informed. It turns out that there's a zero knowledge protocol to drive q to 1. That is, there is a protocol that will convince player 2 that player 1 is informed about the choice of game being played without knowing which game it is.
I'm simplifying: these are games of incomplete information, where players may not even know the payoffs from their actions. According to the author, these were first used by Aumann and others to handle Cold War conflicts (one example given is: "suppose the US convinced the Soviet Union to reduce its ballistic missile stockpile by 100. What percentage of the Soviet stockpile is this?". Obviously it would be hard to determine the answer to the second question, and thus hard to determine the payoff of the first action.
Sunday, May 28, 2006
On scores for papers: A postscript
The SIGACT reviewing system asks reviewers to assign scores when reviewing papers. It goes something like this (lightly edited):
I think it's a good idea that scores are kept merely as internal markers, and only provide light hints as to the final fate of a paper. I've reviewed papers where the individual review is given choices like 'strong accept, weak accept, weak reject, strong reject', and the categorical nature (as well as implied decision) of these verdicts make it harder IMO for a paper to survive an early dissing by a reviewer. Moreover, if you get a paper rejected with a set of reviews containing three weak accepts, it can be really puzzling to figure out what happened.
More importantly, not revealing scores prevents people from falling into the confusion that paper reviewing is a deterministic objective process; it most certainly isn't. However, at least in my experience, paper discussions can be extremely nuanced and sophisticated, far more so than a mere "objective" score can achieve.
- 9-10: An enthusiastic yes. I will fight strongly for this paper.
- 8-8.99 A strong vote for acceptance. A solid contribution. This paper should be in the top third of the papers in the conference.
- 7-7.99 A vote for acceptance. Not a stellar result, but clearly worth accepting.
- 6-6.99: A weak vote for acceptance. A reasonable contribution to
- an interesting problem - or maybe the contribution is good but
- the authors don't seem to understand what it is and/or express it
- well - or maybe it's a good paper, but the subject area is marginal
- for the conference.
- 5.0-5.99: Ambivalent. I might support accepting this paper, but I don't advocate accepting it. Probably publishable as a journal paper, but a bit too specialized or too incremental or perhaps it has nice ideas but is too preliminary, or too poorly written.
- 4.0-4.99 A competent paper, but not of sufficient interest/depth.
- 2.5-3.99: A solid vote for rejection. It is very unlikely that I could be convinced to support this paper.
- 1-2.49 A strong vote for rejection. A poor paper, unsuitable for any journal.
- 0.01-.99: Absolute reject. Completely trivial and/or non-novel and/or incorrect and/or completely out of scope.
I think it's a good idea that scores are kept merely as internal markers, and only provide light hints as to the final fate of a paper. I've reviewed papers where the individual review is given choices like 'strong accept, weak accept, weak reject, strong reject', and the categorical nature (as well as implied decision) of these verdicts make it harder IMO for a paper to survive an early dissing by a reviewer. Moreover, if you get a paper rejected with a set of reviews containing three weak accepts, it can be really puzzling to figure out what happened.
More importantly, not revealing scores prevents people from falling into the confusion that paper reviewing is a deterministic objective process; it most certainly isn't. However, at least in my experience, paper discussions can be extremely nuanced and sophisticated, far more so than a mere "objective" score can achieve.
Subscribe to:
Posts (Atom)