Electronic Version 17 (1992), 351-369

Michael D. Hirsch

Proving lower bounds for the cost of solving problems on a computer is a very difficult problem-not least because it is a global problem: one must minimize cost over all possible algorithms. As with many other global problems, a topological approach has proven fruitful. We give two applications of topology to the problem of proving lower bounds. The first is to the computation of the topological complexity of a problem. We define the New Point Problem and compute tight bounds for its topological complexity. The second application is to finding lower bounds on one way communication complexity of two processors.

• AtlasImage format
• DVI file
• PostScript file

volume 17: table of contents
topology proceedings Electronic Version