|
A high level overview of GCT Dr. K.V. Subrahmanyam Chennai Mathematical Institute. 05-09-07 Abstract Recently Ketan Mulmuley has put up a number of papers (GCT IV, jointly with Milind Sohoni, GCT V jointly with Hari Narayanan, and GCT VI and many more in the pipeline) expanding on his and Milind Sohoni's approach to separating complexity classes, via algebraic geometry and representation theory. The main idea therein is the notion of a flip - a flip which shows how - proving the non-existence of algebraic circuits of a fixed size computing a given function can be accomplished - by showing the existence of mathematical objects with positivity properties. The existence of mathematical objects with these properties implies that, all the representation theory problems which arise in GCT, have polynomial time solutions, due to a methodology called ``Saturated Integer Programming'', introduced in GCT VI. Ketan has also put up a paper wherein he gives a high level view of GCT; why he believes this approach will work, why there is probably no simpler approach, why this is not naturalizaable, the problems involved, and what are the problems which remain to be solved. This is an overview meant to be understood assuming, almost nothing. My hope is to present this paper, from scratch, in about 3 hours, assuming nothing.
|
