
Re: topology and computer science
Posted:
Apr 25, 2000 10:52 PM


The original posting was kind of vague and misleading, but there are a number of connections between topology and computer science. For some involving computational geometry, you might want to check out a report I coauthored, "Emerging challenges in computational topology", http://arXiv.org/abs/cs.CG/9909001
Other connections include
 Graph theory sprang out of topology, and is central to theoretical computer science.
 Topological invariants have been used to provide lower bounds on the amount of computing time needed to solve various problems. A standard example is the problem of determining whether any two of n numbers are equal to another  the set of ntuples with two equal disconnects the set of all other ntuples into n! connected components, from which one can conclude that log_2(n!)=Omega(n log n) time is required in certain models of computation  of course one can use hashing to solve this sort of problem more quickly but that would be outside these models.
 Topological analysis of distributed computation (about which I don't know much, sorry)  David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/

