The Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: topology and computer science
Replies: 16   Last Post: Apr 27, 2000 10:01 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
eppstein@euclid.ics.uci.edu

Posts: 128
Registered: 12/8/04
Re: topology and computer science
Posted: Apr 25, 2000 10:52 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply



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
co-authored, "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 n-tuples with two equal disconnects the
set of all other n-tuples 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/







Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.