tag:blogger.com,1999:blog-3722233.post271743129929561379..comments2023-12-07T03:00:23.146-06:00Comments on Computational Complexity: How Much is a Proof?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger15125tag:blogger.com,1999:blog-3722233.post-47895265266854616572008-10-17T20:03:00.000-05:002008-10-17T20:03:00.000-05:00I was not misquoting. Back when Anon#9 was Anon#6...I was not misquoting. Back when Anon#9 was Anon#6 they wrote "In fact, a very low percentage of a professor's time is spent on research." and when they continued as Anon#9 they gave that percentage as "35% for research".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33645227144556891282008-10-17T10:27:00.000-05:002008-10-17T10:27:00.000-05:00Wow, Anon#9 must do some amazing math. Even ignori...<I>Wow, Anon#9 must do some amazing math. Even ignoring whether the percentages have any link to reality, according to this poster we are told that 25% is "a large percentage" and 35% is "a very low percentage".</I><BR/><BR/>That's hardly a fair complaint, since large/low is obviously meant in comparison with popular conceptions rather than in absolute terms. Plus you are misquoting: 35% was described as "not exactly low but is lower than one might expect" rather than "very low".<BR/><BR/>I disagree with the precise percentages in that comment, but the underlying sentiment is not so wrong.<BR/><BR/><I>But to claim there's any benefit in unprofessional scientific writing is wrong.</I><BR/><BR/>I certainly agree, but people are good at rationalizing all sorts of misbehaviors. I've known of a few older professors who actually argued that it is good not to prepare too much for class, on the grounds that seeing how an expert works out the details from scratch is illuminating to the students (despite leading to a much less polished presentation). There's a little bit of truth to this, but it is mainly nonsense. The same is true for writing: there's some small benefit to being forced to reconstruct a poorly written argument, but it is outweighed by the enormous drawbacks.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48102559091634318782008-10-17T07:39:00.000-05:002008-10-17T07:39:00.000-05:00Wow, Anon#9 must do some amazing math. Even ignor...Wow, Anon#9 must do some amazing math. Even ignoring whether the percentages have any link to reality, according to this poster we are told that 25% is "a large percentage" and 35% is "a very low percentage".Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15447280158888775072008-10-17T04:33:00.000-05:002008-10-17T04:33:00.000-05:00Anon #9: IANAP, but I think you're pulling those n...Anon #9: IANAP, but I think you're pulling those numbers from nowhere. A professor who's taught the same course for years doesn't have to spend as much effort on it as one who's teaching it for the first time -- certainly some work has to be done, but there's no good reason it should be more than 1 + epsilon times (lecture hours) + (office hours).<BR/><BR/>And amount of time spent on admin stuff varies widely between professors -- it's a function of how many students they have, what kind of positions they hold within a department, and all sorts of other, less-quantifiable factors.<BR/><BR/>Plus, of course, these things are not mutually exclusive and in fact are often parallelizable -- thinking about research during office hours, for example, is a trivial task.Johnhttps://www.blogger.com/profile/18079824074256670713noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8323013621466202812008-10-17T03:33:00.000-05:002008-10-17T03:33:00.000-05:00All authors, without exceptions, should write full...All authors, without exceptions, should write full detailed proofs. All statements in a published paper should be precisely and formally presented, accompanied with a full, formal, detailed proof.<BR/><BR/>Any other option is unprofessional: it doesn't serve any purpose. Reader might get lost; statements might have fatal mistakes; the actual statements of theorems might cause confusion; referees might be mislead, etc.<BR/><BR/>Not everybody can write in such a way. But to claim there's any benefit in unprofessional scientific writing is wrong.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30930811067967649292008-10-16T22:15:00.000-05:002008-10-16T22:15:00.000-05:00The most challenging papers I had to read in tcs a...The most challenging papers I had to read in tcs are the ones written by Leonid Levin (extremely concise) and by Peter Gacs (lengthy but still very complicated) ... at least they're challenging for good reasons :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-4400357855357713382008-10-16T21:46:00.000-05:002008-10-16T21:46:00.000-05:00Please tell me that you aren't implying that a lar...<EM>Please tell me that you aren't implying that a large percentage is spent on teaching.</EM><BR/><BR/>Umm, yes actually.<BR/><BR/>Regardless of how good a teacher someone is, they are spending at least 10 hours per week per course. I don't know how many hours they work per week, but let's peg this as 25% of their time. <BR/><BR/>For the record, I'd estimate 40% of a prof's time dedicated to "admin", which includes advising, departmental admin, grant writing, refereeing, etc.<BR/><BR/>That leaves 35% for research, which is not exactly low but is lower than one might expect.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78439096688015046322008-10-16T20:41:00.000-05:002008-10-16T20:41:00.000-05:00The general advice in this post seems like a good ...The general advice in this post seems like a good thing to spread far and wide, at the very least through other conference CFPs...<BR/><BR/>Is there any intrade market for how many theorems someone will prove a year? or for when P vs NP will be (dis)proved?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26153253696201389112008-10-16T19:27:00.000-05:002008-10-16T19:27:00.000-05:00"In fact, a very low percentage of a professor's t..."In fact, a very low percentage of a professor's time is spent on research."<BR/><BR/><BR/>Please tell me that you aren't implying that a large percentage is spent on teaching.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90608882926986160502008-10-16T17:06:00.000-05:002008-10-16T17:06:00.000-05:00I would guess that nobody proves 100 theorems a ye...I would guess that nobody proves 100 theorems a year.<BR/><BR/>In any case, Lance (and everyone else) does more than prove theorems. Lance teaches, gives talks, does service, writes expository articles (and blog posts), advises students, etc., etc.<BR/><BR/>In fact, a very low percentage of a professor's time is spent on research.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35201021165589727272008-10-16T15:04:00.000-05:002008-10-16T15:04:00.000-05:00When I saw the title of this post, I thought it me...When I saw the title of this post, I thought it meant: "How much does a proof cost?", which is in fact an interesting question. For example, Lance may prove 100 theorems a year, and get paid 100k. So one proof costs 1k dollars. What's this number for an average graduate student?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88293195894401143532008-10-16T12:38:00.000-05:002008-10-16T12:38:00.000-05:00Why not have online discussions to better explain ...Why not have online discussions to better explain proofs and/or seek clarification from the proof authors?<BR/><BR/>Wouldn't this make more sense than trying to guess which parts of the proof readers will find difficult and that should be explained in more detail?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65575097622597667222008-10-16T09:35:00.000-05:002008-10-16T09:35:00.000-05:00The last SODA call for papers had some text in the...The last SODA call for papers had some text in the call for papers to the effect that full details must be present, in the paper or in an appendix. I hadn't been a big fan of appendices in the past but I thought that was a good idea, as a way to force authors to write the full details up front as they should rather than only writing the extended abstract.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19344160169999025172008-10-16T08:46:00.000-05:002008-10-16T08:46:00.000-05:00Golden rule might not work here: Noam Nisan can wr...Golden rule might not work here: Noam Nisan can write proofs with gaps, but<BR/>Lance Fortnow can't!GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-22555943857789928262008-10-16T08:08:00.000-05:002008-10-16T08:08:00.000-05:00Also, writing out proofs clearly and in full detai...Also, writing out proofs clearly and in full detail is often good for the authors themselves. I have seen many bugs at the exact point at which the authors wrote "clearly.." or "obviously..."Anonymousnoreply@blogger.com