tag:blogger.com,1999:blog-3722233.post1508511855142931431..comments2023-02-08T10:05:26.048-06:00Comments on Computational Complexity: The Putnam Exam: Some ThoughtsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-3722233.post-1125102808277597952009-03-25T11:42:00.000-05:002009-03-25T11:42:00.000-05:00IMO, many math and tcs students would prefer to re...IMO, many math and tcs students would prefer to read failed attacks on problems, not just the successful ones. They want to (at least I did) learn *why*, not just what is true; they want to see research in action. I think books can be written better than they are, to help readers understand things deeper. Maybe some day authors will put exercises like: Try proving the theorem using this other idea/method and explain why it fails.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-65541364457009469432009-03-24T19:24:00.000-05:002009-03-24T19:24:00.000-05:00In math, the opposite is often true - people try t...<I>In math, the opposite is often true - people try to cover their tracks and stick to the bare definitions, theorems, and proofs. </I><BR/><BR/>This is a common canard and is not true. It is true that referees and editors of math journals will not as a rule tolerate pages of fluff -- as a result math papers often look terse by comparison (to say theoretical CS papers). On the other hand the typical math paper is better written (often adhering to the two months in the drawer rule) with proper motivations/intuitions etc. -- but it is true that they also have a higher expectation on the part of the reader.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72487242848506449742009-03-24T14:27:00.000-05:002009-03-24T14:27:00.000-05:00Is mathematics about mere "problem solving" or und...<I>Is mathematics about mere "problem solving" or understanding properties of structures that makes problem solving possible (and indeed trivial) ?</I><BR/><BR/>Understanding the properties of structures is part and parcel of problem-solving. I never implied that I was distinguishing the two (though I agree that this skill is not exercised by Putnam competitions).<BR/><BR/>One does not need to repeat the entire line of false starts to motivate the right path.<BR/>We motivate the group definition by immediately providing a number of examples that group theory unifies. We motivate non-Abelian groups by giving natural examples such as matrices or permutations.<BR/><BR/>The issue of the way math courses are frequently presented is reflected in one of the standard styles of mathematical papers vs the usual standard in CS theory papers. In CS theory papers, one frequently sees extensive motivating discussions for definitions, intuitions for proofs, etc included in the write-up. In math, the opposite is often true - people try to cover their tracks and stick to the bare definitions, theorems, and proofs. A great math writer like Timothy Gowers, who gives both motivations and intuitions, is the exception rather than the rule.<BR/><BR/>Wouldn't math teaching be much better if it were taught with these motivations and intuitions?<BR/><BR/>Anon 6Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51040403077956565672009-03-24T12:33:00.000-05:002009-03-24T12:33:00.000-05:00A more serious correlation would be if many of the...<I>A more serious correlation would be if many of these famous mathematicians who are past IMO/Putnam winners are currently involved in these contests</I><BR/><BR/><A HREF="http://www-math.mit.edu/~rstan/" REL="nofollow">Richard Stanley</A> and <A HREF="http://en.wikipedia.org/wiki/Hartley_Rogers,_Jr" REL="nofollow">Hartley Rogers</A> are the coaches of the MIT Putnam team. <A HREF="http://www-math.mit.edu/~kedlaya/" REL="nofollow">Kiran Kedlaya</A> also proctors the exam and is additionally involved in high school math contests. Akamai (read: <A HREF="http://people.csail.mit.edu/ftl/" REL="nofollow">"Tom Leighton"</A>) gives scholarships to math contest winners. These are just a few I know about in my vicinity.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3011394004084315822009-03-24T10:56:00.000-05:002009-03-24T10:56:00.000-05:00... stultifying nature of writing down layered def...<I> ... stultifying nature of writing down layered definitions in the typical advanced math course ... </I><BR/><BR/>There is a pedagogical issue here. Of course, instead of defining abstract groups a course could meander through the questions about symmetry of roots of polynomials etc. that motivated Galois and others to arrive at the notion of groups even if they did not call it so. Similarly, for analytic functions and L^2 spaces, or for that matter the definition of real numbers not to mention the complex numbers, and so forth. But each of these notions took almost a human life span or more to take shape -- and it would be unrealistic take a Lamarckian approach to math pedagogy. Its important I guess to emphasize this right at the beginning of a math course. Not everything can be or will be motivated. <BR/>So LEARN THIS NOW AS ALL YOUR MATHEMTATICAL FOREFATHERS DID DURING THEIR MATHEMTICAL APPRENTICEHOOD and have faith that it will be USEFUL LATER.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23027246060442540932009-03-24T10:41:00.000-05:002009-03-24T10:41:00.000-05:00This is the part that is stultifying. Internalizin...<I>This is the part that is stultifying. Internalizing the definitions is important but it is a step removed from the actual problem-solving.</I><BR/><BR/>There is a deeper issue here. Is mathematics about mere "problem solving" or understanding properties of structures that makes problem solving possible (and indeed trivial) ? If mathematics is to be considered as a serious scientific discipline, and not a mere collection of little tricks, then I believe it should be the latter. If you believe this, then the little tricks you get trained for IMO or the Putnam are indeed orthogonal to mathematics research. The correlation between research mathematicians and IMO winners is just that those who have the temperament to become mathematicans are the natural candidates for math teams at the school or college level. A more serious correlation would be if many of these famous mathematicians who are past IMO/Putnam winners are currently involved in these contests which would testify to their faith in these contests. I believe this number is quite small but I might be mistaken on this.<BR/><BR/>As a side not, I think G.H. Hardy devoted a lot of energy trying to (apparently unsuccessfully) abolish the Cambridge Tripos (which could be seen as a British equivalent to Putnam).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90330151714674297112009-03-23T21:58:00.000-05:002009-03-23T21:58:00.000-05:00To Anon 6:You do realize that those courses are no...<I>To Anon 6:<BR/><BR/>You do realize that those courses are not "pushing around definitions" for the sake of pushing around definitions, don't you? Definitions are supposed to help you see clearer and better, allowing you to soar higher like a bird.</I><BR/><BR/>I am not denying the beauty and value of the mathematics involved. Fundamental algebra, Galois theory, Fourier analysis, analytic functions, etc, were all highly appealing. There are great insights involved in coming up with these definitions. However, courses present most definitions as a fait accompli. "We will go to the next definition because it will be useful in the proof of a theorem about a problem that we haven't yet stated." The problem-solving detective game and failed attempts to prove theorems that led to the definitions is buried. Problem sets are designed for students to explore properties of the definitions so that they internalize them. This is the part that is stultifying. Internalizing the definitions is important but it is a step removed from the actual problem-solving.<BR/><BR/>Anon 6Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51591185342801363302009-03-23T19:56:00.000-05:002009-03-23T19:56:00.000-05:00Certainly being a good problem solver does not dec...<I> Certainly being a good problem solver does not decrease your problem-creation ability. <BR/></I><BR/><BR/>Sure, but neither does it greatly increase it. The correlation is decent but far from perfect.<BR/><BR/>Based on people I've known, here are some reasons why Putnam winners may not become researchers:<BR/><BR/>(1) Some just have many interests and are good at many things. Eventually they are going to specialize in something, and there's no reason it has to be mathematics.<BR/><BR/>(2) Some people love the puzzle aspect of contests, the fact that you know there's always a beautiful solution and you just have to figure out the trick. They may just not enjoy working on research problems, which might (and often do) turn out to be unsolvable or ugly or not the right question after all. It's a very different experience.<BR/><BR/>(3) Some people love the competitive aspect more than the subject area. When the opportunity to win disappears, they lose interest (or move on to another area with a well-defined notion of winning, such as making money on Wall Street).<BR/><BR/>(4) Even when someone does love the subject area, it can be hard to adjust to not being the best. If you are the top contest problem solver in your year in the whole country (or even world), but turn out to be only the tenth best researcher, it's tough. Instead of feeling happy about being among the world's best researchers, you can end up feeling sad about no longer being the very best. It's irrational but all too human, and sometimes it is psychologically easier just to do something else.<BR/><BR/>(5) Attention span: some people are really good at focusing intently on one thing for an hour or two but have trouble maintaining their enthusiasm throughout a six-month research project. It's easy to get frustrated or impatient.<BR/><BR/>(6) Opportunity: becoming either a contest winner or a great researcher is correlated with certain opportunities, such as having a great coach or mentor. This isn't necessary, but it helps a lot. Most people never have such luck, and those who do usually have it in one area but not the other (otherwise they'd be doubly lucky). So if you had a fantastic olympiad coach but inadvertently choose a lousy advisor, you're less likely to become a top researcher.<BR/><BR/>(7) A few people win contests through raw talent, but most Putnam fellows combine talent with considerable training and practice. This training is relatively straightforward in its approach. It's not at all easy (you have to be very smart and very hard working), but at least you basically know what to do to improve. By contrast, what should you do to become a good researcher? It's a lot less clear, so some Putnam fellows will lose some of the advantage they got from diligent practice. (Hard work still pays off, but it pays off the most when it's clear what you should be working on.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2632292205439239562009-03-23T16:11:00.000-05:002009-03-23T16:11:00.000-05:00Personal Opinion: The reason for shift from Physic...Personal Opinion: The reason for shift from Physics to Combinatorics is the problems in Physics needs some fixed methods to solve them, either you have learned it, or it is nearly impossible to solve the problem, where as in combinatorics, you always have very simple looking problems which need real creativity, and I think IMO and IMC are better than Putnam, maybe due to attendance of students from old Eastern Block. I have checked the list of Gold Medal winers in IMO and saw many Fields Medal winners among them. I think problem solving is orthogonal to theory/concept building, but the norm is bounded.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2312726070745214462009-03-23T15:37:00.000-05:002009-03-23T15:37:00.000-05:00To Anon 6:You do realize that those courses are no...To Anon 6:<BR/><BR/>You do realize that those courses are not "pushing around definitions" for the sake of pushing around definitions, don't you? Definitions are supposed to help you see clearer and better, allowing you to soar higher like a bird.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82161766460707423112009-03-23T13:13:00.000-05:002009-03-23T13:13:00.000-05:00My best score on the Putnam was as a freshman afte...My best score on the Putnam was as a freshman after having done math contests throughout high school. It declined steadily each subsequent year as the stultifying nature of writing down layered definitions in the typical advanced math course took its toll. There is little real problem-solving cleverness required in most such courses, but a lot of pushing around definitions.<BR/><BR/>CS theory in my senior year became a welcome return to some of the aspects of math that I had so enjoyed in high school math competitions.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47420258134424964282009-03-23T13:00:00.000-05:002009-03-23T13:00:00.000-05:00Many of the people who participate and win the Put...Many of the people who participate and win the Putnam exam are the same people who've been doing math competitions in high school, and are simply applying the problem-solving skills they already have rather than spending large amounts of time preparing for Putnam specifically. So the choice between studying for Putnam versus doing research is not one most people have to make -- for the first two years, one can do well based on what you already know and minimal practice, and afterwards, as one's competitive skills deteriorate due to insufficient "professional training", one is usually more ready and acquainted with mathematics to shift to research.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83479162090815037112009-03-23T12:11:00.000-05:002009-03-23T12:11:00.000-05:00The older exams asked more about physics. [...] Wh...<I>The older exams asked more about physics. [...] Why this trend?</I><BR/><BR/>It might be because of changing attitudes toward physics and about mathematics itself. V.I. Arnold starts <A HREF="http://pauli.uni-muenster.de/~munsteg/arnold.html" REL="nofollow">this interesting talk</A> with "Mathematics is a part of physics", and blames Bourbaki (etc.) for the change. :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32723417023809094972009-03-23T11:29:00.000-05:002009-03-23T11:29:00.000-05:00I spent a good portion of my childhood participati...I spent a good portion of my childhood participating in various math competitions, including Putnam. I agree that preparation for such competitions requires love/understanding of math, but, after you reach amateur level, it becomes much more like "professional training": you read different problems, memorize techniques, and generally start working on speed rather than creativity. You also need a good coach. Indeed, without a coach I was 33rd in my junior year. Then we had a great coach at NYU, and I won it the following year. Then I did not practice for a year, went to proctor the Putnam at MIT next year, and I barely solved half of the problems (no training for a year kills your speed).<BR/><BR/>To sum up, after some basic training you reach the level of being able to solve most problems, but slowly (say, between an hour and a day depending on the difficulty). At which point you only train for the speed.<BR/><BR/>Regarding the use for research, I found the sets of skills required largely orthogonal. In a competition, you know there is a relatively short solution, and you try to find it as soon as you can. In research, you do not even know what is the right question, let alone if it has short/elegant solution. I struggled a lot during my first few years at MIT, thinking that the love for puzzles would somehow be useful for me. Only when i completely stopped "wasting" time on the puzzles, the research somehow picked up.<BR/><BR/>Nowadays, I try to stay away from Putnam-like problems at all cost: they are addictive and take time from research :).<BR/><BR/>Yevgeniy DodisAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30895016100366194312009-03-23T10:49:00.000-05:002009-03-23T10:49:00.000-05:00I know that, if nothing else, it helps you keep yo...I know that, if nothing else, it helps you keep your thoughts on math, particularly if you're spending a semester fulfilling other requirements...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59282285214424400742009-03-23T10:33:00.000-05:002009-03-23T10:33:00.000-05:00I think that for people going into any field with ...I think that for people going into any field with a lot of complex Math would benefit by preparing for and participating in the Putnam competition. Far too often in the class setting, you're not presented with enough diversity of problem type to train you and get you used to making comprehensive use of all that you know and have been exposed too. And bering better able to pull from all that you've done before is a valuable asset.Anonymousnoreply@blogger.com