tag:blogger.com,1999:blog-3722233.post6586719894031462416..comments2023-10-04T04:25:54.403-05:00Comments on Computational Complexity: Analysis in ComplexityLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-53427208132363087932008-08-25T14:47:00.000-05:002008-08-25T14:47:00.000-05:00good to see the field drawing and encroaching vari...good to see the field drawing and encroaching various other techniques. It is fun to keep changing and expanding.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10259203519757512792008-08-07T11:24:00.000-05:002008-08-07T11:24:00.000-05:00Anon 4 is right, assuming Avi's talk is about the ...Anon 4 is right, assuming Avi's talk is about the partial derivatives method for arithmetic circuit lower bounds. That method is really algebraic, rather than analytic. Perhaps the scope of the workshop "Analytic Tools in Computational Complexity" is broader than the title implies?<BR/><BR/>-Amit CAChttps://www.blogger.com/profile/14911233583375020356noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61944391554394987992008-08-04T10:12:00.000-05:002008-08-04T10:12:00.000-05:00I started graduate work in complexity right before...<I>I started graduate work in complexity right before the algebraic revolution that drove Razborov-Smolensky's circuit lower bounds, .... But now, two decades later, algebraic techniques are producing diminishing returns and we have seen a growth in using real analysis in complexity .... Avi Wigderson is giving a two-hour survey on "The Power of Partial Derivatives." Hard to have imagined a connection between partial derivatives and complexity.</I><BR/><BR/><BR/><BR/>I think you misunderstood something. Wigderson's talk on partial derivatives is precisely an example of the algebraic techniques used in complexity (i.e., partial-derivatives of <I>multivariate polynomials</I>); this was found highly useful in recent years, in contrast to what you said above.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67924472554750065902008-08-04T08:55:00.000-05:002008-08-04T08:55:00.000-05:00Well, just to help get this very interesting topic...Well, just to help get this very interesting topic underway, it seems to me that these trends are very good news for complexity theory, for the following (mainly heuristic) reasons.<BR/><BR/>We note that algebraic geometry provides a natural arena for uniting algebraic methods with analytic methods.<BR/><BR/>Then a physically reasonable approach to both computation and simulation is to specify a state-space---whether classical or quantum---that does accomplishes computational work implicitly, by virtue of the state-space geometry.<BR/><BR/>This geometrically expresses the main idea of model order reduction. From a discrete point of view, circuit designers apply this same idea whenever they lay out a circuit that accomplishes as much of a computation as possible implicitly.<BR/><BR/>One virtue of adopting this "<A HREF="http://en.wikipedia.org/wiki/Chow's_theorem#Serre.27s_GAGA" REL="nofollow">GAGA</A>" point of view regarding computation and simulation is that it specifies a fertile mathematical arena within which both algebraic and geometric techniques can be brought to bear simultaneously.<BR/><BR/>These ideas are particularly well-suited to the study of quantum systems, because it is easier (and more natural) to associate algebraic structures with Kählerian state-spaces than with Riemannian state-spaces.<BR/><BR/>The recent work of <A HREF="http://arxiv.org/abs/quant-ph/0701004" REL="nofollow">Dowling and Nielsen</A> is an enjoyable and thought-provoking introduction to these ideas.<BR/><BR/>I definitely hope this thread (and conference) will draw a lot of comments! :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13955053503703723602008-08-04T08:52:00.000-05:002008-08-04T08:52:00.000-05:00What about those of us who went into computational...<I>What about those of us who went into computational complexity because we enjoyed discrete math? </I> quite some tools from analysis has been deployed in discrete mathematics too ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57487766676845373262008-08-04T08:30:00.000-05:002008-08-04T08:30:00.000-05:00It would be nice to have some of the material avai...It would be nice to have some of the material available online.Anonymousnoreply@blogger.com