Jeff's post on his computational topology class (and the wonderful class outline), prompted me to write about something that I've tried to explain to people before.
Computational topology is arguably the hottest thing in SoCG-land right now, and has been so for a number of years (for curious folk, the "other" hot topic is high dimensional approximate geometry). But if you ask different people, you'll get different answers to the question "what is computational topology ?". I've even had to explain to local students why my computational geometry class is different from the computational topology class being offered. So here goes:
CT I: Using topological ideas to understand the 'shape' of data
This is the version of CT that has taken up the largest fraction of CT mindshare in the SoCG land. Dating back to work by Edelsbrunner and Mucke on alpha-shapes, the field now encompasses a range of ideas for extracting topological structure from data. New topological constructs that have come from this area include various notions of persistence, as well as related work on reconstruction, data smoothing, and visualization.
Afra Zomorodian's thesis (now a book) is a nice introduction to these concepts for a CS audience. Herbert Edelsbrunner is coming out with a book on this topic very soon (Jan 16, 2010! Mark your amazons!), and Valerio Pascucci teaches a class on computational topology at the U.
CT II: Asking computational questions about fundamental topological objects and concepts.
This is closest to the 'Computational X' flavor of work, where a computational perspective is brought to the study of X. There are many interesting problems here, and they have a nice discrete flavor that makes them 'friendly' for theoryCS folk. For example, computing the Betti numbers of a simplicial complex efficiently, or finding homotopy equivalent paths on a surface, or lots of work on graphs on surfaces.
I don't think there's a single book on this topic. JeffE has put together a fantastic course outline (with reading material), and there's also a great book on graphs on surfaces by Mohar and Thomasson. It's worth noting that some of the deeper tools in the Robertson-Seymour graph minor results take us into graphs-on-surfaces-of-large-genus land.
CT III: Using topological ideas in the heart of complexity theory.
Almost no one I know uses 'computational topology' in this sense, and there isn't a coherent and connected body of work to talk about as such. But there are some fascinating results at the core of complexity theory that rely on topological constructions. There's the algebraic complexity work of Yao/Steele/Ben-Or and others, showing that lower bounds for algebraic complexity of certain problems can be related to the sum of Betti numbers of associated surfaces. There's the Kahn-Saks-Sturtevant (and Chakrabarti-Khot-Shi) work on evasiveness of graph properties, and then the work (that I don't quite understand) on topology in distributed computing (that got Herlihy, Saks, Shavit and Zahoroglou the Godel Prize)
This is one of the reasons I think a course in topology (of some flavor, whether it be combinatorial, algebraic or point-set) should be required mathematical background for all theoryCS students.
ghrist also has a large program on applied topology in wireless sensor networks, and his 'euler calculus'
ReplyDeletehttp://www.math.uiuc.edu/~ghrist/
What about Algebraic Geometry? It has considerably more algorithms that Algebraic Topology and can also be seen as more fundamental.
ReplyDeleteWe of course all know now a days about Mulmuley. But is Algebraigc Geometry also useful for mining for patterns in data? For example Algebraic Statistics started by Sturmfels and Diaconis (who also participates in Computational Topology group at Stanford) tries to reason about graphical models observing they are sort of algebraic varieties and applying vast algorithmic machinery that comes with these.
Has anything came out of this?
Your remark on the work of Herlihy et al. was interesting: I've never understood it either, but I have no background in topology. I have seen no writeups of this work by anyone other than the authors of the original papers (though there has been followup work by others), and I wonder whether anyone actually understands it.
ReplyDeleteDid you not understand the Herlihy work because you didn't try, or did you make the effort and still not succeed? Just curious...
Actually, it's more that I understood that work at one point, and have since forgotten. It didn't seem particularly inaccessible to me when I read it the first time: maybe I'll do a post on it sometime.
ReplyDelete