tag:blogger.com,1999:blog-3722233.post519908491948294394..comments2020-05-27T23:17:32.309-04:00Comments on Computational Complexity: How has the STRUCTURES, OH- I mean CCC Conference changed: Lets look at the Call For PapersLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-88169193901719811812011-05-09T23:26:06.181-04:002011-05-09T23:26:06.181-04:00Bill,
You showed the 2008 list in column-major...Bill, <br /><br />You showed the 2008 list in column-major order. In writing out the revisions of the 2007 list from the PC, I assumed that it would be read in row-major order. In that case, "other concrete computational models" would be read after "circuit complexity" and "communication complexity". (BTW: This did not represent order of importance at all.) <br /><br />"Computational Randomoness" and "Kolmogorov complexity" seemed to have too much overlap so the PC chose to make the split clearer.<br /><br />Yes. It was tradition to keep the first topic and the sense in Timothy Chow's comment seems correct: As I understand it, it refers to how the entire web of complexity classes gives a structure within which we can classify computational problems. This includes containments, collapses, reducibility, etc and may be expressed as in the <a href="http://www.math.ucdavis.edu/~greg/zoology/diagram.xml" rel="nofollow">complexity zoo diagram</a>.<br /><br />When "Structures" started in 1986, the "concrete" side of complexity was very well represented in STOC/FOCS (Barrington's simulation of NC^1 by constant width BPs and Hastad's parity lower bound were among the highlights of that year's STOC) but other aspects of complexity were not and those were emphasized in the call. It was clearly a mistake and some of the papers at the first Structures were definitely "concrete". (e.g., James Lynch's paper on AC^0 lower bounds for small cliques was at the first one and Kalyanasundaram and Schnitger's original randomized CC lower bounds for disjointness were at the second.)Paul Beamenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91651108177584625572011-05-08T07:38:36.575-04:002011-05-08T07:38:36.575-04:00It is interesting that the terms "sampling&qu...It is interesting that the terms "sampling", "validation", and "verification" appear in none of the lists ... and yet in practice, these three are among the most ubiquitous, most difficult, and most interrelated computational challenges that we face.John Sidleshttp://faculty.washington.edu/sidles/ENC_2011#forGilKalainoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13406425470395487462011-05-05T23:25:08.420-04:002011-05-05T23:25:08.420-04:00Rocco- THANKS, you inspired me to look in to this ...Rocco- THANKS, you inspired me to look in to this and I added to the post a pointer to a list of all learning theory in CCC papers I could find.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75910608103146036012011-05-05T22:51:47.212-04:002011-05-05T22:51:47.212-04:00FYI: There was a nice article on TCS in last week&...FYI: There was a nice article on TCS in last week's New Yorker! Check it out: http://www.newyorker.com/reporting/2011/05/02/110502fa_fact_galchen <br />(subscription required)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52146627222747105612011-05-05T21:49:59.606-04:002011-05-05T21:49:59.606-04:00To answer one of Bill's questions, there have ...To answer one of Bill's questions, there have been at least a half-dozen papers on complexity and learning at CCC in the past decade. <br /><br />I searched for the string "learn" in the CCC proceedings tables of contents going back to 2001. There were papers whose titles include the term "learning" or "learnability" in 2001, 2002, 2005, 2006, 2008, 2009 and 2010, including Oded Regev's invited talk and survey paper on "The Learning with Errors Problem" in 2010. <br /><br />I imagine that looking beyond just paper titles would turn up additional CCC papers that are <br />related to learning.<br /><br />-- RoccoAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4826453266738008892011-05-05T11:40:29.093-04:002011-05-05T11:40:29.093-04:00I always thought that "structure of complexit...I always thought that "structure of complexity classes" referred to things like Ladner's theorem or the Berman-Hartmanis isomorphism conjecture, i.e., properties of a complexity class beyond its mere existence as an arbitrary set of strings.Timothy Chowhttp://alum.mit.edu/www/tchownoreply@blogger.com