tag:blogger.com,1999:blog-3722233.post113347131090750298..comments2024-08-03T11:58:59.111-05:00Comments on Computational Complexity: The First Saturday in DecemberLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger21125tag:blogger.com,1999:blog-3722233.post-1133840265531946772005-12-05T21:37:00.000-06:002005-12-05T21:37:00.000-06:00I tend to doubt that "in math one would have no pr...<I> I tend to doubt that "in math one would have no problem publishing a completely different proof of a known result".</I><BR/><BR/>Then you need to become more familiar with the inner workings of math. One of the reasons they welcome new proofs is that they highlight heretofore unknown links. If one can prove a calculus result, using unexpectedly simple geometry, then the fact that the connection is in itself important. <BR/><BR/>If the proof is just a variation, of course it won't be published, but if it is completely different it certainly would.<BR/><BR/><I> Such a result would almost certainly not appear in a top journal.</I><BR/><BR/>And no one claimed that was the case, so your comment is not to the point. <BR/><BR/><I>As for the flip side, people have already commented numerous times on this blog that a simpler proof of the parallel repetition theorem would be publishable.</I><BR/><BR/>Oh wow! A new simpler proof of a result that takes 6 lectures or more is publishable, who would have thunk it?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133813278700068732005-12-05T14:07:00.000-06:002005-12-05T14:07:00.000-06:00I don't think that's quite fair: I tend to doubt t...I don't think that's quite fair: I tend to doubt that "in math one would have no problem publishing a completely different proof of a known result". Such a result would almost certainly not appear in a top journal, and whether it was publishable at all would depend on the importance of the problem and the extend to which the proof was simpler.<BR/><BR/>As for the flip side, people have already commented numerous times on this blog that a simpler proof of the parallel repetition theorem would be publishable. We have also seen the excitement over Dinur's simplified proof of the (known) PCP theorem.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133742773681098832005-12-04T18:32:00.000-06:002005-12-04T18:32:00.000-06:00From Wiles lecture:Secondly the creation of new ma...From Wiles lecture:<BR/><BR/><I>Secondly the creation of new mathematics enables us to dramatically simplify and clarify the old results. Calculus is now routinely taught in high school; however, in the seventeenth century it could not have been understood except by a very, very few eminent mathematicians in the world. This is not because people are smarter now, but because our language is clearer. The language of mathematics has been purified by the many new uses to which it has been put.</I><BR/><BR/>Sadly CS has not yet learned the value of simplified notation. While in math one would have no problem publishing a completely different proof of a known result, I've personally had a novel proof of a known result using elementary techniques and it got rejected from all conferences and journals it got submitted to.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133734179151104722005-12-04T16:09:00.000-06:002005-12-04T16:09:00.000-06:00Oops the Wiles link does not appear entirely in my...Oops the Wiles link does not appear entirely in my previous message.<BR/><BR/>http://www.claymath.org/<BR/>Popular_Lectures/Andrew_Wiles/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133734046063828892005-12-04T16:07:00.000-06:002005-12-04T16:07:00.000-06:00As Michael said, success at math contest is a good...As Michael said, success at math contest is a good predictor of raw math ability, but not necessarily a good predictor of personality traits that are necessary to become a good researcher. Patience and persistence are not the only qualities required to become great researchers: Intellectual courage and independent thinking are extremely important too. In "Recoltes et Semailles", Grothendieck attributed his own success as a researcher to his independent thinking, and he claimed that he was not a quick learner. <BR/>Also you can see Andrew Wiles' opinion on this matter in his speech to IMO contestants:<BR/>http://www.claymath.org/Popular_Lectures/Andrew_Wiles/<BR/><BR/>Also the full text(in french) of Grothendieck's<BR/>"recoltes et semailles" is available from:<BR/>http://www.math.jussieu.fr/~leila/biographic.php<BR/>He talks about the importance of independent thinking especially in chapter 2.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133729665078664862005-12-04T14:54:00.000-06:002005-12-04T14:54:00.000-06:00If you're only good at one, then you need to find ...<I> If you're only good at one, then you need to find good co-authors to make up for what you lack. </I><BR/><BR/>Or, if you're like me, and not particularly good at either, you become an expert in finding <B> really </B> good co-authors...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133708380706952712005-12-04T08:59:00.000-06:002005-12-04T08:59:00.000-06:00I don't think anyone is saying there is no correla...I don't think anyone is saying there is no correlation at all. Of course there is! The point is how strong is this correlation? <BR/><BR/>And like the previous post said, it boils down to the following. Research requires at least two abilities: (1) formulating an interesesting problem and (2) being able to solve it. However, the exams only measure (2), the aptitude for solving problems. <BR/><BR/>Now, some people are better at formulating problems, some are better at solving them and some are good at both. If you are good at both, then you can not only win the Putnam exam, but you will most likely have great success in research. If you're only good at one, then you need to find good co-authors to make up for what you lack.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133673774111876142005-12-03T23:22:00.000-06:002005-12-03T23:22:00.000-06:00Actually some of the Putnam supposed "droupouts" w...Actually some of the Putnam supposed "droupouts" were recruited by the NSA and had successful stealth research careers there. This appeared in an interview with an NSA honcho about a decade ago in one of Intelligencer, Monthly,Notices or other similar such.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133657569437430082005-12-03T18:52:00.000-06:002005-12-03T18:52:00.000-06:00Most people seem to be making claims like "math co...Most people seem to be making claims like "math competitions don't predict research success." C'mon. Obviously there's *some* correlation. Also obvious, it isn't a resoundingly strong correlation. People do well on these tests are probably more likely to be successful than the average jerk on the street, but they sure aren't guaranteed to be.<BR/><BR/>Remember, balanced or subtle opinions are for cowards!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133650188513860922005-12-03T16:49:00.000-06:002005-12-03T16:49:00.000-06:00In my opinion, the reason these exams do not predi...In my opinion, the reason these exams do not predict research ability is simply because they only test how well one can solve problems. Research, on the other hand, requires (among other things) one to also be able to ask the right questions.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133597848941129132005-12-03T02:17:00.000-06:002005-12-03T02:17:00.000-06:00Hmm..when I was in high school or college I never ...Hmm..when I was in high school or college I never heard about these math contests. Too bad because I love math.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133552852949812592005-12-02T13:47:00.000-06:002005-12-02T13:47:00.000-06:00I will side with Lance again...to the extent that ...I will side with Lance again...<BR/><BR/>to the extent that I think these contests are at best an OK predictor of research success. I think a test like the Putnam is a strong predictor of raw mathematical ability, and a strong predictor of contest /puzzle math ability. These characteristics are at least weakly correlated with research ability. But there are other qualities as well -- persistence and patience have been mentioned, but also the ability to work well with others, the ability to write well, the ability to recognize what problems are most interesting, the ability to synthesize previous work -- all of these skills are important too. <BR/><BR/>I know many, many high school math geeks -- very top math contest people -- who did not become famous researchers. Some were lured away by money (Wall Street called many away in the 90's). Some just didn't end up being that good at research. They were bright enough, certainly, but were in hindsight obviously lacking in one or more of those other less obvious skills.<BR/><BR/>Of course, I also think these math contests are a VERY good thing -- they get people interested in and excited about math. There are so many high school mathematics competitions -- at least there were in California when I was a wee lad. Why in college do we become limited to just the Putnam? There are more college programming contests than math contests these days, it seems. Should someone be doing something about that?Michael Mitzenmacherhttps://www.blogger.com/profile/06738274256402616703noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133501401860487602005-12-01T23:30:00.000-06:002005-12-01T23:30:00.000-06:00The problem solving in the high school contests wa...The problem solving in the high school contests was a real boost to my interest in the subjects where I participated (mathematics, physics, chemistry, CS).<BR/><BR/>My IMO team from 1990 has produced 3 math PhDs, 1 CS PhD (me), 1 physics MSc, and 1 medical doctor (a math grad school drop-out who suddenly decided that he wanted to do something more immediately meaningful).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133500539497620562005-12-01T23:15:00.000-06:002005-12-01T23:15:00.000-06:00I'd have to say that math contests are what got me...I'd have to say that math contests are what got me into TCS. It seems to be a particularly natural transition from doing well on contests like the Putnam contest and doing well in TCS. The kinds of problems that appear on math contests in general (not just the Putnam contest) have a nice connection with the kinds of approaches one sees in TCS (and in combinatorics), much more so than with most of the rest of mathematics. <BR/><BR/>High school math contests got me interested enough to become a math major but the standard algebra, analysis, geometry focus of the math major seemed to take me further and further away from the heart of this interest. I never did great on it but my Putnam scores were best in my freshman year and declined in each of the other years I took it. It was only seeing TCS in my senior year that I realized that there was a natural outlet for this interest.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133494526255728212005-12-01T21:35:00.000-06:002005-12-01T21:35:00.000-06:00That's North American universities. Toronto and Wa...That's <B>North</B> American universities. Toronto and Waterloo have both done quite well over the years (see <A HREF="http://en.wikipedia.org/wiki/William_Lowell_Putnam_Mathematical_Competition" REL="nofollow">this </A> link for example).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133487378037888232005-12-01T19:36:00.000-06:002005-12-01T19:36:00.000-06:00The putnam (or similar such tests) are not perfect...The putnam (or similar such tests) are not perfectly correlated with success at mathematics research, certainly. I don't think any test can possibly measure a lot of the factors that go into making a successful researcher.<BR/><BR/>With that said, it is about as good of an indicator as a test is likely to be. I suspect if you took say all the prefect math GRE scorers and compared it to the equivalent number of highest scorers on the putnam, the putnam high scorers would have on average had more impressive academic resumes.<BR/><BR/>In any case the real point in taking the putnam is in my opinion not the fame of it. It's that most of the questions are pretty fun. Maybe not in a testing environment, but they're exaclty the sort of things I'd enjoy puzzling through with an officemate on a lazy day. Maybe that's why I'm an (aspiring) mathematician?<BR/><BR/>The problems are also nice because they're on average satisfyingly difficult for questions which are so elementary.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133483404708936172005-12-01T18:30:00.000-06:002005-12-01T18:30:00.000-06:00Here's a nice page with all Indian teams up to 200...Here's a nice page with all Indian teams up to 2001 (wonder why they stopped updating). Note the large number of names familiar to us in the TCS community. <BR/><BR/>http://www.iisc.ernet.in/mocell/PEOPLE/teams.htmlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133482909968118672005-12-01T18:21:00.000-06:002005-12-01T18:21:00.000-06:00In addition to aptitude, research requires patienc...In addition to aptitude, research requires patience and persistence. While these math contests single out candidates who have the aptitude, those among them who have patience and persistence will go on to become successful researchers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133480928717593082005-12-01T17:48:00.000-06:002005-12-01T17:48:00.000-06:00I know many people who have participated in the Pu...I know many people who have participated in the Putnam, as well as other mathematical contests. However, some of them did not even go on to pursue research in mathematics. For them, the interest was more in the competition rather than the math. These contests measure competitiveness as well as mathematical problem solving ability. You need both to do well in the contests, but research is an entirely different ballgame.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133480109609954382005-12-01T17:35:00.000-06:002005-12-01T17:35:00.000-06:00Here are two interesting links:Link 1: http://www....Here are two interesting links:<BR/><BR/>Link 1: <BR/>http://www.iisc.ernet.in/mocell/PEOPLE/halloffame.html<BR/><BR/>Link 2:<BR/>http://www.maa.org/awards/putnam.html<BR/><BR/>It's amazing how many of these people are now successful researchers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133479854597545052005-12-01T17:30:00.000-06:002005-12-01T17:30:00.000-06:00But if you take the number of people who have done...But if you take the number of people who have done well in these international and national-level mathematical competitions, an overwhelming number of them are successful mathematical/TCS researchers. <BR/><BR/>So your conclusion is not completely correct.Anonymousnoreply@blogger.com