tag:blogger.com,1999:blog-3722233.post115118685110760345..comments2022-05-17T19:30:53.024-05:00Comments on Computational Complexity: FREE REPRINTSLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger27125tag:blogger.com,1999:blog-3722233.post-1151424728697474812006-06-27T11:12:00.000-05:002006-06-27T11:12:00.000-05:00Forget about algorithms - how about crypto?! Only ...Forget about algorithms - how about crypto?! Only one crypto researcher on the PC this year (Kilian), and with all due respect to Kilian (whom I deeply respect) he hasn't been all that active in crypto for the past 5 years.<BR/><BR/>In general, many fewer crypto papers are accepted to FOCS/STOC than algorithms papers. Whether one agrees with this bias or not, it makes it hard for theoretical cryptographers when comparing their pulication lists to algorithms researchers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151414066583844462006-06-27T08:14:00.000-05:002006-06-27T08:14:00.000-05:00Isn't it just possible that the accepted papers ar...<I>Isn't it just possible that the accepted papers are simply stronger or more innovative?</I><BR/><BR/>It is possible, and frankly with a more balanced committee this year it is not too unlikely.<BR/><BR/>At the same time it is rather self-serving to dismiss a complain that has been echoed by many people across many different periods as simply "[awesome] anecdotal evidence".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151386476393134192006-06-27T00:34:00.000-05:002006-06-27T00:34:00.000-05:00I have not submitted a paper to FOCS nor am I a me...I have not submitted a paper to FOCS nor am I a member of the PC. I haven't seen the list of accepted papers either. However, the griping I am reading seems particularly overblown and baseless. The complaints about the composition of the PC are absurd and reflect ignorance more than anything. Isn't it just possible that the accepted papers are simply stronger or more innovative?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151383327296113532006-06-26T23:42:00.000-05:002006-06-26T23:42:00.000-05:00I meant to say: I would call some in your list of ...I meant to say: <BR/><BR/>I would call <I>some in</I> your list of people "algorithmic friendly" researchers as opposed to algorithmers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151382715022557862006-06-26T23:31:00.000-05:002006-06-26T23:31:00.000-05:00-everything he does is about algorithms; even his ...<I>-everything he does is about algorithms; even his complexity is driven completely by algorithmic questions. </I><BR/><BR/>I wouldn't go as far as saying _everything_ he does is algorithmic, but I can grant you the overall sentiment. Yet, doing algorithmic inspired complexity theory makes you an applied complexicist, not an algorithmer. <BR/><BR/>I would call your list of people "algorithmic friendly" researchers as opposed to algorithmers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151381926374682122006-06-26T23:18:00.000-05:002006-06-26T23:18:00.000-05:00Somehow Christos seems like a poor choice for your...Somehow Christos seems like a poor choice for your argument--everything he does is about algorithms; even his complexity is driven completely by algorithmic questions. He is perhaps the single most algorithmically-minded person I know.<BR/><BR/>Your criteria are silly (and it's precisely because most of his algorithmic work is published in the "anti-algorithmic" STOC/FOCS...) I'll just list my favorite CHP algorithms papers of the last 10 years<BR/><BR/>An Approximation Scheme for Planar Graph TSP<BR/><BR/>On the k-Server Conjecture<BR/><BR/>Computing correlated equilibria in multi-player gamesAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151379406351739602006-06-26T22:36:00.000-05:002006-06-26T22:36:00.000-05:00AndrewsAroraCharikarChawlaEricksonFleischerKannanK...Andrews<BR/>Arora<BR/>Charikar<BR/>Chawla<BR/>Erickson<BR/>Fleischer<BR/>Kannan<BR/>Kaplan<BR/>Karlin<BR/>Papadimitriou<BR/>Racke<BR/>Rajaraman<BR/>Spielman<BR/><BR/>This list is ridiculous. Let's say, to grab a random example, look at Christos. He has spend the last n years doing high quality computational game theory, and the previous n years before that doing top notch complexity theory. Along the way he published five papers (out of 272) in SODA and 2 in ESA. <BR/><BR/>Under such liberal classification rules, a researcher who published one paer out of 20 in, say, databases, would qualify as a DBer. Clear nonsense.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151378474433619122006-06-26T22:21:00.000-05:002006-06-26T22:21:00.000-05:00either their interpretation is correct, or the ini...<I>either their interpretation is correct, or the initial commenter is a disgruntled FOCS'06 PC member.</I><BR/><BR/>There are other not so unlikely possibilities, e.g.: the person who made the comment is currently attending an algorithms workshop. Today, at lunch, the subject of FOCS results came out and it turned out there were several other well known algorithmers who submitted papers to FOCS this year and all got rejected. <BR/><BR/>Another scenario is that griper belongs to a prestigious CS department with several top notch algorithmers. Again, over lunch today it came out that none of their papers got accepted.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151378444163894532006-06-26T22:20:00.000-05:002006-06-26T22:20:00.000-05:00IMHO, the mere fact that four out of 23 PC members...<I>IMHO, the mere fact that four out of 23 PC members is considered "a lot of algorithms researchers" suggests that there is an anti-algorithms bias.</I><BR/><BR/>Ahh, now it's clear. If your interpretation of algorithms is so narrow then "algorithms" do indeed deserve a smaller representation in the conference.<BR/><BR/>On the other hand, the rest of us recognize that<BR/><BR/>Andrews<BR/>Arora<BR/>Charikar<BR/>Chawla<BR/>Erickson<BR/>Fleischer<BR/>Kannan<BR/>Kaplan<BR/>Karlin<BR/>Papadimitriou<BR/>Racke<BR/>Rajaraman<BR/>Spielman<BR/><BR/>form a very large contigent of people known (and more often than not, well-known) for their work in algorithms (and I even left off the MCMC people!)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151377822448776692006-06-26T22:10:00.000-05:002006-06-26T22:10:00.000-05:00This is pure speculation on your part. Not an unli...<I>This is pure speculation on your part. Not an unlikely guess but far from self-evident as you claim.</I><BR/><BR/>It's not "pure" speculation by far- either their interpretation is correct, or the initial commenter is a disgruntled FOCS'06 PC member. The former seems more likely.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151377447205339122006-06-26T22:04:00.000-05:002006-06-26T22:04:00.000-05:00the FOCS 2006 PC has a lot of algorithms researche...<I>the FOCS 2006 PC has a lot of algorithms researchers. </I><BR/><BR/>Using a functional definition in terms of papers published in algorithms conferences, the FOCS PC has about four full time algorithmers, plus another five or so half time algorithmers. <BR/><BR/>IMHO, the mere fact that four out of 23 PC members is considered "a lot of algorithms researchers" suggests that there is an anti-algorithms bias.<BR/><BR/><I>This makes it a bit tough to blame the complexity researchers this time.</I><BR/><BR/>This is a move in the right direction.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151375444311678242006-06-26T21:30:00.000-05:002006-06-26T21:30:00.000-05:00The previous commenter was clearly basing their as...<I>The previous commenter was clearly basing their assertion on the fact that their paper(s) were not accepted to this FOCS, </I><BR/><BR/>This is pure speculation on your part. Not an unlikely guess but far from self-evident as you claim.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151374891818834612006-06-26T21:21:00.000-05:002006-06-26T21:21:00.000-05:00While I am at least somewhat sympathetic to the ol...While I am at least somewhat sympathetic to the old "FOCS/STOC is anti-algorithms" claim, the FOCS 2006 PC has a lot of algorithms researchers. This makes it a bit tough to blame the complexity researchers this time.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151371498173370002006-06-26T20:24:00.000-05:002006-06-26T20:24:00.000-05:00A minor difference is that a lot of people have re...<I>A minor difference is that a lot of people have reached the conclusion that FOCS is not algorithms friendly, while you are the only one who has ever posited the aisle seat hypothesis.</I><BR/><BR/>The previous commenter was clearly basing their assertion on the fact that their paper(s) were not accepted to this FOCS, as opposed to e.g. basing their conclusion on an analysis of the full accepted papers list.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151367252976405512006-06-26T19:14:00.000-05:002006-06-26T19:14:00.000-05:00Anecdotal evidence is awesome! I have discovered t...<I>Anecdotal evidence is awesome! I have discovered that FOCS is against papers written on airplanes, *but only if you had an aisle seat*. My papers written in window seats were both accepted.</I><BR/><BR/>A minor difference is that a lot of people have reached the conclusion that FOCS is not algorithms friendly, while you are the only one who has ever posited the aisle seat hypothesis.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151356442086348252006-06-26T16:14:00.000-05:002006-06-26T16:14:00.000-05:00Regarding paper prints... I am against it for the ...Regarding paper prints... I am against it for the sake of environment.<BR/>If we have a soft copy we can take print-out when (and only when) necessary. I am a theoretician and I use recycled paper to do my theory work. I also stopped all my paper bills and pay all my bills online.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151354523039213172006-06-26T15:42:00.000-05:002006-06-26T15:42:00.000-05:00Again FOCS results are very hostile to algorithmic...<I>Again FOCS results are very hostile to algorithmic papers.</I><BR/><BR/>Anecdotal evidence is awesome!<BR/><BR/>I have discovered that FOCS is against papers written on airplanes, *but only if you had an aisle seat*. My papers written in window seats were both accepted.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151347993945720462006-06-26T13:53:00.000-05:002006-06-26T13:53:00.000-05:00Again FOCS results are very hostile to algorithmic...Again FOCS results are very hostile to algorithmic papers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151342512257682172006-06-26T12:21:00.000-05:002006-06-26T12:21:00.000-05:00Also, anyone care to comment why it took two weeks...Also, anyone care to comment why it took two weeks after the PC meeting to get the notifications out?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151311010169495222006-06-26T03:36:00.000-05:002006-06-26T03:36:00.000-05:00BTW, FOCS results are out. Is there a published li...<I> BTW, FOCS results are out. </I><BR/><BR/>Is there a published list of accepted papers?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151300889582094212006-06-26T00:48:00.000-05:002006-06-26T00:48:00.000-05:00BTW, FOCS results are out.BTW, FOCS results are out.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151270354409402282006-06-25T16:19:00.000-05:002006-06-25T16:19:00.000-05:00My question is, can the prng-based technique for p...My question is, can the prng-based technique for pir with 2 counterparties be generalized to k counterparties, and if it can does the recurrence multiply by 2 at each recursive application to get from n^(1/x) to n^(1/(x+1)), or does it multiply by k? That result would be very nearly practical.<BR/><BR/>It's surprising how poorly that recurrence works when you plug in real numbers. n^e my ass. It's a good example of how the scale of the real universe actually matters.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151217772609069032006-06-25T01:42:00.000-05:002006-06-25T01:42:00.000-05:00You could always bet that there won't be 2 people ...<I>You could always bet that there won't be 2 people interested in a reprint. But then the better can recruit a friend.</I><BR/><BR/>Then he could just bet $5 that 7 people won't be interested in a reprint, because then the counter betters would be out $0.46 from the whole deal.Macneil Shonlehttps://www.blogger.com/profile/16382866616548432101noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151206060239845092006-06-24T22:27:00.000-05:002006-06-24T22:27:00.000-05:00(I would bet $5.00 I won't get any takers, except ...<I> (I would bet $5.00 I won't get any takers, except that someone may take the bet and request a copy, thus gaining $4.61) </I><BR/><BR/>So, find a mechanism (in the game-theoretic sense), such that if no one really wants a copy, the person you are betting against will get 5.00$, but such that it won't be worth it for that person to send a request himself. If you know the identity of the better, then that is easy.<BR/><BR/>You could always bet that there won't be 2 people interested in a reprint. But then the better can recruit a friend.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1151202488846207062006-06-24T21:28:00.000-05:002006-06-24T21:28:00.000-05:00I can't resist pointing out that Recursive Algebra...I can't resist pointing out that Recursive Algebraic Topology may be a sensible thing to study.<BR/><BR/>Apparently, modern algebraic topology makes heavy use of things called Grothendieck universes, which are rather hefty objects from a logical perspective (they're a bit stronger than, say, the consistency of ZFC set theory), particularly when they're used (like with Fermat's Last Theorem) to prove statements about ordinary arithmetic.<BR/><BR/>There's some debate among proof theorists at the moment about whether those principles could be eliminated from the proof so that, say, FLT could be proven in something like Peano arithmetic. (After all, it would be rather interesting if a straightforward statement like FLT were independent of Peano arithmetic.)<BR/><BR/>Such work would almost inevitably include asking which principles of algebraic topology are not only arithmetic, but computable...that is, Recursive Algebraic Topology.<BR/><BR/>My points being...give it five years, and there might be such a field.Anonymousnoreply@blogger.com