I'm very much a novice in these subjects, but Geometry of Interaction and Geometric Complexity Theory seem to speak similar language and have vaguely similar goals. Am I not mistaken? Are there any links between them?
3
-
3$\begingroup$ It might help if you spelled out what geometry of interactions and geometric complexity theory mean to you, and more explicitly pointed out the overlap in language and goals that you are seeing. This would make this question more valuable for other novices (since they can see some definitions and connections) and show to the experts due dillegence on your part of having a basic grounding. $\endgroup$– Artem Kaznatcheev ♦Commented May 10, 2015 at 17:18
-
2$\begingroup$ @ArtemKaznatcheev: even an expert like me would find it hard to explain to a complexity theorist (or somebody who knows what GCT is about) what the geometry of interaction (without "s") is. It was introduced in the late 80s by J-Y. Girard as a proof-thoeretic research program whose goal was (roughly) to overcome the traditional syntax/semantics divide. Today, the term denotes a collection of recipes and techniques that turned out to be useful for studying quantitative properties of programming languages (optimal evaluation, execution time/space, compilation into hardware circuits...). $\endgroup$– Damiano MazzaCommented May 12, 2015 at 8:54
-
1$\begingroup$ It seems that I'm 2 years late but doesn't Thomas Seiller work on both Geometry of Interaction and Geometric Complexity Theory ? Maybe you should take a look at his work. $\endgroup$– BorisCommented Nov 19, 2017 at 11:35
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
No one knows if there are connections between GoI and GCT.
It's quite plausible, since both are used to analyze complexity, and since GoI is formulated in terms of monoidal categories and GCT is based on representation theory. However, to my knowledge there aren't any researchers who understand both well enough to say for certain.
answered May 11, 2015 at 8:38
-
2$\begingroup$ I definitely agree. I know nobody who understands both well enough to be able to tell whether there is a connection or not. In fact, I'd be surprised to meet a GCT expert who has even heard about the GoI. People of the opposite kind exist, Neel and I are examples (I can consider myself a GoI expert vaguely knowing what GCT is about). In any case, we won't be able to do much more than speculate. Personally, I am pessimistic about the existence of a meaningful connection. $\endgroup$ Commented May 12, 2015 at 8:42