tag:blogger.com,1999:blog-3722233.post6249579419393281163..comments2022-12-05T10:50:26.666-06:00Comments on Computational Complexity: Focs Wrap UpLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-15525703763876458612008-11-04T11:10:00.000-06:002008-11-04T11:10:00.000-06:00For computational geometry, FOCS/STOC screwed up b...For computational geometry, FOCS/STOC screwed up by (1) having very little attendance at the geometry sessions, (2) accepting a weaker but more broadly accessible geometry paper while rejecting the best geometry paper submitted, and (3) not accepting enough geometry papers to make it worth a geometer's while to go to the conference.<BR/><BR/>Earlier, we drove semantics away by scheduling the semantics session opposite the outing (at the Providence conference in the 80's, long ago).<BR/><BR/>I don't really think there was any way to have avoided this narrowing of focus without accepting more papers, but there was a subset of the community that was dead set against this.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-24872437803660617392008-11-03T15:28:00.000-06:002008-11-03T15:28:00.000-06:00John, I don't know about the slides, you'll have t...John, I don't know about the slides, you'll have to ask one of the authors.<BR/><BR/>Anon3, I'd just like to see a conference that features the best foundational papers in theoretical computer science, without any implicit or explicit bias as to which sub-area the papers belong to. It seems that FOCS and STOC did fulfill this role, once upon a time. Re. the specific observation about Comp. Geom, the point is that these statistics are very unpredictable for some of the non-complexity/algorithms areas, a variance that surely exceeds the natural year-to-year variance...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80108279930879575532008-11-03T08:41:00.000-06:002008-11-03T08:41:00.000-06:00Thanks for these posts, they were very good.Thanks for these posts, they were very good.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35031367123921632052008-10-31T16:57:00.000-05:002008-10-31T16:57:00.000-05:00What you are suggesting seems to needa "Federated ...What you are suggesting seems to need<BR/>a "Federated Computer Science Theory Symposium"? <BR/><BR/><BR/>(One slight inaccuracy: There were a fair number of computational geometry papers at FOCS - 8 by the PC chair's count.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70408758059928477882008-10-31T16:28:00.000-05:002008-10-31T16:28:00.000-05:00Jonathan, thanks for the correction. I'm pleasantl...Jonathan, thanks for the correction. I'm pleasantly surprised that there are people actually reading the technical parts :) The results in the post are all quoted from memory, so it's quite possible there are other inaccuracies.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86606149088123389712008-10-31T16:21:00.000-05:002008-10-31T16:21:00.000-05:00Anon #3, you are correct but I was writing for a g...Anon #3, you are correct but I was writing for a general audience...<BR/><BR/>Technically, the result only rules out certain black-box constructions.Jonathan Katzhttps://www.blogger.com/profile/07362776979218585818noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1066773099490482792008-10-31T16:19:00.000-05:002008-10-31T16:19:00.000-05:00As someone working in computational biology, I fee...As someone working in computational biology, I feel the STOC/FOCS representation for the field has been fair. The main work in the area is less-theoretical in the past, as the focus has switched away from elegant toy problems, and towards obtaining biologically meaningful results by whatever (not necessarily elegant or theoretical) means possible.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78785897501042458692008-10-31T15:59:00.000-05:002008-10-31T15:59:00.000-05:00Jonathan, I haven't read the paper, but I wouldn't...Jonathan, I haven't read the paper, but I wouldn't expect their result to rule out constructions using techniques like NIZKs for well-formedness, which I would consider standard.<BR/><BR/>I would explain these results as ruling out "highly efficient" constructions of IBE from a PKE/TDF component. I see them as more of a guidepost towards a construction of IBE than anything else.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46630119282257760752008-10-31T13:56:00.000-05:002008-10-31T13:56:00.000-05:00Sorry, but I have to correct the cryptography resu...Sorry, but I have to correct the cryptography result. While the initial constructions of identity-based encryption (IBE) were in the random oracle model, we do now have constructions of IBE that do not rely on random oracles. However, the existing constructions all rely on specific number-theoretic assumptions rather than "general" assumptions (e.g., the existence of standard public-key encryption). The talk you mention showed that we cannot expect to construct IBE from certain general assumptions, at least using standard techniques.Jonathan Katzhttps://www.blogger.com/profile/07362776979218585818noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28730640121861688172008-10-31T13:08:00.000-05:002008-10-31T13:08:00.000-05:00Thank you mentioning Learning Geometric Concepts v...Thank you mentioning <A HREF="http://www.cs.cmu.edu/~odonnell/papers/perimeter.pdf" REL="nofollow"><I>Learning Geometric Concepts via Gaussian Surface Area</I></A>. This is a topic of great interest in quantum simulation ... are the slides to this talk available?<BR/><BR/>I am asking for the dumbest of all reasons: the above article has no pictures, gossip, or jokes ... which are not essential in learning a subject ... but they sure help. :)<BR/><BR/>Ditto for Raphael Yuster's closely related (in the mind of engineers) <I>Matrix sparsification for rank and determinant computations via nested dissection</I>.<BR/><BR/>And, thanks for the summary. For what it's worth, I agree that greater FOCS breadth would be welcome.Anonymousnoreply@blogger.com