tag:blogger.com,1999:blog-3722233.post1296771739085676434..comments2024-06-20T12:36:16.541-05:00Comments on Computational Complexity: FOCS IILance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-9451492524583926532007-10-28T04:41:00.000-05:002007-10-28T04:41:00.000-05:00I heard several comments in the halls on the first...I heard several comments in the halls on the first day about the high quality of the talks in general. One talk I really liked was Mihalis Yannakakis' talk on fixed points and approximating Nash equilibria. This is different from the Nash problem that is PPAD-complete in that the goal is to approximate a fixed point rather than find a point that is approximately fixed. Because 3-player Nash includes the Sum of Square Roots problem as a special case, this problem seems much harder (A nice result of the paper is that this version of 3-player Nash is as hard as the general problem of computing an approximation to a fixed point of an arithmetic circuit.)<BR/><BR/>BTW: The Sum of Square Roots problem is not well known but it probably should be: Given positive integers a_1,...,a_n, and k <BR/>is sum_i sqrt{a_i}<=k? It is open whether this is even in NP. Allender et. al. (2006) showed that it can be solved in the 4th level of the Counting Hierarchy P^{PP^{PP^{PP}}} (PSPACE was already known) but that seems to be the smallest complexity class so far. The issue is that the best we know is an exponential upper bound on the number of bits of precision required to separate the sum from k.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6392243848037255542007-10-22T23:13:00.000-05:002007-10-22T23:13:00.000-05:00Correction to anonymous 1: That was Nicole not Ann...Correction to anonymous 1: <BR/>That was Nicole not Anna giving the talk.<BR/><BR/>Best analogy: Nicole Immorlica (balloons)<BR/><BR/>though of course the kudos for the analogy go to all authors.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70962565517830910772007-10-22T00:25:00.000-05:002007-10-22T00:25:00.000-05:00Missing that first talk was a mistake. It was exc...Missing that first talk was a mistake. It was excellent. It followed exactly the lines Terence Tao suggested in his tutorial, a concrete application. <BR/><BR/>Nominations for the official unofficial complexity blog FOCS awards: <BR/><BR/>Best jokes: Andrea Montanari<BR/>Best analogy: Anna Karlin (balloons)<BR/>Best session chair: Kamal Jain<BR/>Best talk: ?? still open..Anonymousnoreply@blogger.com