f



Topological Spaces and Computation

Can someone explain the basics of how topology is related to computing?  I
have heard, for instance, that the mathematics of higher cohomology are
being employed in new P != NP research.  I have also heard of category
theory being employed in the study of algorithms.  Can anyone point me to
some references (prefferably online)?  Thanks.



l8r, Mike N. Christoff



0
mchristoff (248)
7/1/2003 9:57:22 PM
comp.theory 5139 articles. 1 followers. marty.musatov (1143) is leader. Post Follow

9 Replies
604 Views

Similar Articles

[PageSpeed] 19

In article <cGnMa.3458$bD1.406618@news20.bellglobal.com>,
Michael N. Christoff <mchristoff@sympatico.caREMOVETHIS> wrote:
>Can someone explain the basics of how topology is related to computing?  I
>have heard, for instance, that the mathematics of higher cohomology are
>being employed in new P != NP research.

Where have you heard this?  I've heard of some connections between topology
and computing, but nothing that quite matches this description.

>I have also heard of category
>theory being employed in the study of algorithms.  Can anyone point me to
>some references (prefferably online)?  Thanks.

One reference is

R.F.C. Walters, Categories and Computer Science, Undergraduate
Lectures in Mathematics, Carslaw Publications, University of Sydney,
Australia, 1991. ISBN 1 875399 01 1
-- 
Tim Chow       tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth.  ---Galileo, Dialogues Concerning Two New Sciences
0
tchow (869)
7/2/2003 12:51:48 PM
Michael N. Christoff wrote:
> Can someone explain the basics of how topology is related to computing?  

I don't know topology, but for sure Recursion Theorem is a topological
property, isn't it?
0
taati (61)
7/3/2003 5:48:46 AM
Hi,

trying to understand current work on denotational (and categorical)
semantics of computation is a task for a whole life (I would even say
for several lives). Just a few introductions:

Gordon Plotkin
DOMAINS
Department of Computer Science
University of Edinburgh
1983
ftp://theory.lcs.mit.edu/pub/papers/Plotkin/domains.dvi

Helmut Schwichtenberg
TYPE THEORY
Mathematisches Institut der Universit�t M�nchen
Sommersemester 1992
http://www.mathematik.uni-muenchen.de/~schwicht/lectures/typeth/ss92/tt.dvi.Z

Jaap van Oosten
BASIC CATEGORY THEORY
BRICS Lecture Series
January 1995
http://www.brics.dk/LS/95/1/BRICS-LS-95-1.ps.gz

Andrea Asperti, Giuseppe Longo
CATEGORIES, TYPES AND STRUCTURES
An Introduction to Category Theory for the Working Computer Scientist
Foundations of Computing Series
MIT Press, 1991
http://www.dmi.ens.fr/users/longo/download.html
ftp://ftp.ens.fr/pub/dmi/users/longo/CategTypesStructures

Try the first chapter of Plotkin's notes to get a hint at the subject.
Be sure to understand the idea of fixpoint. At the end of this chapter
there is an exercise that relates CPOs to topological spaces.

Hope this helps.

Regards.
Jose Juan Mendoza Rodriguez

let name=josejuanmr in
  let isp=lycos in
    let country=es in
      name@isp.country
0
me4 (19624)
7/3/2003 9:39:19 AM
<tchow@lsa.umich.edu> wrote in message
news:3f02d564$0$3935$b45e6eb0@senator-bedfellow.mit.edu...
> In article <cGnMa.3458$bD1.406618@news20.bellglobal.com>,
> Michael N. Christoff <mchristoff@sympatico.caREMOVETHIS> wrote:
> >Can someone explain the basics of how topology is related to computing?
I
> >have heard, for instance, that the mathematics of higher cohomology are
> >being employed in new P != NP research.
>
> Where have you heard this?  I've heard of some connections between
topology
> and computing, but nothing that quite matches this description.
>

http://citeseer.nj.nec.com/fortnow02short.html

Page 16 "Future Directions" mentions this in passing.



l8r, Mike N. Christoff



0
mchristoff (248)
7/3/2003 6:13:17 PM
In article <pl_Ma.5888$bD1.684861@news20.bellglobal.com>,
Michael N. Christoff <mchristoff@sympatico.caREMOVETHIS> wrote:
>http://citeseer.nj.nec.com/fortnow02short.html
>Page 16 "Future Directions" mentions this in passing.

Well, it sounds like he's speculating, and that nobody has figured out any
such connection...at least, nothing that they're telling the world about.
The very use of the term "higher cohomology" sounds suspicious to me; why
mention "higher" when there is apparently no connection even to H^1 of
anything?  It sounds like just a codeword for "fancy math."

You might want to take a look at

http://www.google.com/groups?selm=fhmL9.7553%24Vf3.79135%40vixen.cso.uiuc.edu

and the articles leading up to it for some ideas people have had about the
connection between topology and computation.  Robin Forman has also given
some talks about this topic, the basic idea being that computational paths
can be thought of as discrete vector fields.  I don't think he's published
anything about it though.
-- 
Tim Chow       tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth.  ---Galileo, Dialogues Concerning Two New Sciences
0
tchow (869)
7/3/2003 6:52:00 PM
"Michael N. Christoff" <mchristoff@sympatico.caREMOVETHIS> writes:

> <tchow@lsa.umich.edu> wrote in message
> news:3f02d564$0$3935$b45e6eb0@senator-bedfellow.mit.edu...
> > In article <cGnMa.3458$bD1.406618@news20.bellglobal.com>,
> > Michael N. Christoff <mchristoff@sympatico.caREMOVETHIS> wrote:
> > >Can someone explain the basics of how topology is related to computing?
> I
> > >have heard, for instance, that the mathematics of higher cohomology are
> > >being employed in new P != NP research.
> >

There are two links i can see:

-Category theory is used extensively for logics ( linear logic is
all about category theory) and these are tools which come from 
algebraic geometry and topology.

-The ever so brilliant Gromov used to organize a seminar where he
had geometry specialists listening to talks from theoretical computer
scientists. He believes there is a link. I do not know if these seminars
went anywhere, though.

http://www.fields.utoronto.ca/programs/scientific/96-97/singularity/geocomplexity.html

mentions this.


-- 
Laurent Oget, Ph.D. 	laurent@oget.net	http://oget.net
Senior Engineer		Zvolve Systems Inc 	http://zvolve.com
Chercheur Associ� 	Liafa			http://liafa.jussieu.fr
0
loget (1)
7/3/2003 8:30:01 PM
"Michael N. Christoff" <mchristoff@sympatico.caREMOVETHIS> wrote in message
news:cGnMa.3458$bD1.406618@news20.bellglobal.com...
> Can someone explain the basics of how topology is related to computing?  I
> have heard, for instance, that the mathematics of higher cohomology are
> being employed in new P != NP research.  I have also heard of category
> theory being employed in the study of algorithms.  Can anyone point me to
> some references (prefferably online)?  Thanks.
>
>
>
> l8r, Mike N. Christoff
>

Check out this research group at Stanford University:
http://math.stanford.edu/comptop/

Jon


0
7/5/2003 10:29:52 AM
"Michael N. Christoff" <mchristoff@sympatico.caREMOVETHIS> wrote in message news:<cGnMa.3458$bD1.406618@news20.bellglobal.com>...
> Can someone explain the basics of how topology is related to computing?  I
> have heard, for instance, that the mathematics of higher cohomology are
> being employed in new P != NP research.  I have also heard of category
> theory being employed in the study of algorithms.  Can anyone point me to
> some references (prefferably online)?  Thanks.
> 
> 
> 
> l8r, Mike N. Christoff

Two concrete examples of the use of topology in computing are:

* Mulmuley's almost-proof that P != NC uses methods from algebraic
topology including the Collin's decomposition
* Recent results on the evasiveness of graph properties also use
techniques from combinatorial topology

Of course I am ignoring the extensive area of computational topology
that deals with computational problems on topological objects, as well
as things like alpha shapes, flow shaps, Morse Theory for which your
best reference is work by Herbert Edelsbrunner, Joel Hass, and many
others.
0
suresh (7)
7/8/2003 9:22:15 PM
suresh@research.att.com (Suresh Venkat) writes:
| "Michael N. Christoff" <mchristoff@sympatico.caREMOVETHIS> wrote:
| > Can someone explain the basics of how topology is related to
| > computing?  I have heard, for instance, that the mathematics of
| > higher cohomology are being employed in new P != NP research.  I
| > have also heard of category theory being employed in the study of
| > algorithms.  Can anyone point me to some references (prefferably
| > online)?  Thanks.

| Two concrete examples of the use of topology in computing are:

| * Mulmuley's almost-proof that P != NC uses methods from algebraic
| topology including the Collin's decomposition
| * Recent results on the evasiveness of graph properties also use
| techniques from combinatorial topology

| Of course I am ignoring the extensive area of computational topology
| that deals with computational problems on topological objects, as well
| as things like alpha shapes, flow shaps, Morse Theory for which your
| best reference is work by Herbert Edelsbrunner, Joel Hass, and many
| others.

There are also a few papers that use topology for proving decision
tree lower bounds.  See, for example, Yao's FOCS 1992 paper "Algebraic
Decision Trees and Euler Characteristics", or Bjorner, Lovasz, and
Yaos' STOC 1992 paper "Linear Decision Trees: Volume Estimates and
Topological Bounds".

-- 
Jeff Erickson                                         jeffe@cs.uiuc.edu
Computer Science Department                  http://www.uiuc.edu/~jeffe
University of Illinois at Urbana-Champaign
0
jeffe1 (14)
7/8/2003 10:41:25 PM
Reply: