tag:blogger.com,1999:blog-3722233.post3440108870323155526..comments2024-08-02T19:37:12.269-05:00Comments on Computational Complexity: What did he know and when did he know it?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-3722233.post-88969302634725762972012-06-29T17:00:39.965-05:002012-06-29T17:00:39.965-05:00because you read the theorem incorrectly. reread i...because you read the theorem incorrectly. reread it, slowly. then check your graph and see that it's still true of your graph. (that it contains a vertex of degree <=5).<br /><br />a counterexample would be a planar graph all of whose vertices have degree 6 or higher.steve uurtamohttps://www.blogger.com/profile/03414011093442846802noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-9111346553161651182012-06-29T13:01:21.449-05:002012-06-29T13:01:21.449-05:00Please excuse my ignorance, but a graph with a cen...Please excuse my ignorance, but a graph with a central vertex of degree n (n > 5 say) connected to n vertices of degree 1 is planar but has degree greater than 5. Why is this not a counter example to your claim?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66692637100769953832010-05-30T09:22:43.927-05:002010-05-30T09:22:43.927-05:00I had an Arts teacher (named Karla) who didn't...I had an Arts teacher (named Karla) who didn't know who was Frida Kahlo, one of the most important XX century artist. She was a High School teacher at CESO (Centro de Ensino Setor Oeste), Brasilia, Brazil.<br /><br />João CarlosAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86401143406562853262010-05-15T13:30:18.014-05:002010-05-15T13:30:18.014-05:00A former graduate student of (physicist) Julian Sc...A former graduate student of (physicist) Julian Schwinger, whom I will call "B" told me this story ... in the 1950s "B" was working towards a math PhD ... took a required graduate course in algebra ... the concluding question of the final exam was "Give the eigenvectors, eigenvalues, and matrix inverse of this concrete 2x2 matrix".<br /><br />"B" was the only student who calculated the correct answer ... the other students had grasped only the theorems, *not* the concrete calculation methods ... and after a serious talk with his math adviser ... "B" switched to the then-young discipline of field theory.<br /><br />It worked for "B"! :)John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13370243511846729702010-05-15T10:49:46.584-05:002010-05-15T10:49:46.584-05:00i really wonder what applied mathematics program y...i really wonder what applied mathematics program you've been hanging around. maybe they should rename it to something else.<br /><br />look, not everyone has had a real course in all of the following areas: (algebra, number theory, logic, complexity, analysis, algorithms, ...). everyone has a different idea about the important theorems there, and about which subsets should be easy for which fields.<br /><br />it's super easy to find semi-contradictory sounding statements about these inclusion relations.<br /><br />but really, it just sounds like bragging.<br /><br />as a friend of mine used to ask, "are you bragging, or complaining?"steve uurtamohttps://www.blogger.com/profile/03414011093442846802noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-53742829947691293382010-05-13T11:47:53.874-05:002010-05-13T11:47:53.874-05:00I wholeheartedly agree with Dan's comment and ...I wholeheartedly agree with Dan's comment and I am a little disappointed that this seems to have been taken by some as an opportunity to point out other peoples ignorance, rather than our own. I know that there is a vast amount I don't know, and even more that I don't know I don't know. If anything I can take consolation in the fact that as the amount I know I don't know grows, it is at least chipping away at that more dangerous category of things I don't know I don't know. Still, I would be quite annoyed if people started pointing out how ridiculous it is that I don't know X.<br /><br />As regards the PhD example above, I think that is a rather unfair example. Having sat through a few vivas, it becomes pretty clear that people get caught out by the simple questions. I guess this is because their brain tells them it must be a trick, and they just lock up. It isn't necessarily dependent on whether they could or cannot answer the question without the pressure of the viva.Joehttps://www.blogger.com/profile/11034966968414912132noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-681600583882794462010-05-13T10:15:12.036-05:002010-05-13T10:15:12.036-05:00A prof I talked with recently told me the story of...A prof I talked with recently told me the story of an UK PhD candidate in a math department who, when defending, was asked, as a question of common knowledge, to show the shortest proof he knew on irrationality of sqrt(2). Turns out, he didn't know any. (This may be a bed time scary story for PhD candidates, though)Michanoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78936894234867870412010-05-13T03:28:15.887-05:002010-05-13T03:28:15.887-05:00Found out 3 days ago that (for integer linear prog...Found out 3 days ago that (for integer linear programs) the scary-sounding "Lagrangian relaxation" has the same value as the corresponding (real) linear programAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56229138499199851152010-05-13T00:42:35.421-05:002010-05-13T00:42:35.421-05:00I had a geography teacher in high school who had n...I had a geography teacher in high school who had never heard of the Rosetta stone.Gilberthttps://www.blogger.com/profile/12848246894741812189noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2880222501823644242010-05-12T21:53:35.280-05:002010-05-12T21:53:35.280-05:00One just has to get used to the idea that there ar...One just has to get used to the idea that there are a lot of things that we really all should know, but not enough time in which to learn them.<br />The list of things I think I should learn about grows depressingly quickly.<br /><br />Heck, some of the things we think we know aren't even true: It's only finite planar graphs that need to have vertices of low degree.Dan Spielmanhttps://www.blogger.com/profile/02430505190600344820noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21134603538154615972010-05-12T21:26:03.679-05:002010-05-12T21:26:03.679-05:00I didn't know a thing about truly interesting ...I didn't know a thing about truly interesting algorithms until I'd already spent a career programming solutions that worked fine for customers. That's because I never had to solve Google-sized problems, which are now the norm.Geoff Knauthhttps://www.blogger.com/profile/12025560607512616605noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43176484639015777392010-05-12T17:54:18.108-05:002010-05-12T17:54:18.108-05:00http://www.phdcomics.com/comics/archive.php?comici...http://www.phdcomics.com/comics/archive.php?comicid=1056<br /><br />:)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13537431413573843242010-05-12T17:33:01.606-05:002010-05-12T17:33:01.606-05:00Bill's question seems to generate a lot of non...Bill's question seems to generate a lot of nonpositive responses, e.g. embarrassing stories of lack of knowledge.<br /><br />How about a slightly more positive question: are there examples where someone KNOWING something from slightly outside their tiny area of expertise led to significant new results?Joshhttps://www.blogger.com/profile/12723950176543566251noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60278278038846296802010-05-12T15:19:52.429-05:002010-05-12T15:19:52.429-05:00In basic automata theory, I worked a while without...In basic automata theory, I worked a while without noticing that, when an alphabet has 3 or more letters, one can produce words of arbitrary length without "squares", i.e. consecutive repeated sequence.Michanoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39848964220166558572010-05-12T13:53:43.356-05:002010-05-12T13:53:43.356-05:00A related question is "what do some subfields...A related question is "what do some subfields of computer science not know that they should (and when will they learn it)?" I work in natural language processing. Although many people in NLP apply techniques from machine learning and formal language theory, I would say the average NLP researcher has surprising gaps in their knowledge about the ML fundamentals and basic complexity results--even those that are relevant to their work. In my own embarrassing case, I discovered Hammersley & Clifford Theorem was a year after I wrote a paper about conditional random fields. On the formal language side of things, parsing (our field's bread and butter!) and FSA-CFG intersection are basically the same algorithm, just a different interpretation of the results. The number of people in NLP who do not know this is probably extremely high.Chrishttps://www.blogger.com/profile/02873949286995651782noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89371648401215698912010-05-12T13:11:43.806-05:002010-05-12T13:11:43.806-05:00I didn't learn the maxflow-mincut theorem unti...I didn't learn the maxflow-mincut theorem until at least five years after my PhD. I knew there were things called "flows" and "cuts"; I just didn't understand what they were.<br /><br />Another embarrassing example: I didn't learn Boruvka's MST algorithm in any of my algorithms classes; for some reason, my algorithms textbooks and teachers only talked about Prim's and Kruskal's algorithms, even though Boruvka's is older, it's arguably simpler, it's more parallelizable, it runs in linear time on planar graphs, and it's the foundation of all more recent MST algorithms.<br /><br />Oh, wait, that's (almost) everybody.JeffEhttps://www.blogger.com/profile/17633745186684887140noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48822137184201679772010-05-12T12:42:22.083-05:002010-05-12T12:42:22.083-05:00Several of these I just don't believe.
What ...Several of these I just don't believe. <br /><br />What does it mean that someone is "working in" statistical learning theory if they don't know what variance is? In particular, it means that they have never taken even an introductory college course on statistics or probability, nor are they familiar with tail bounds, and cannot have read very many papers.<br /><br />I'm also skeptical of someone who you claim is an "applied mathematician" who does not know about Cantor's theorem. Do they have a PhD? In what field? It is impossible to take an undergraduate analysis class without learning this, and hard to imagine that without even a basic undergrad math background, you could go on to a PhD in math.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13769393870678506332010-05-12T12:25:33.016-05:002010-05-12T12:25:33.016-05:00Knowing too much is not necessarily good and can d...Knowing too much is not necessarily good and can destroy your creativity. This is why mathematicians produce their best work only when they are young.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56432399998789100992010-05-12T12:13:31.480-05:002010-05-12T12:13:31.480-05:00Our lab took on two junior-year electrical enginee...Our lab took on two junior-year electrical engineers as summer interns. It turned out that they had *never* measured an electrical voltage ... voltage for them existed only the output of SPICE simulations.<br /><br />In a similar vein, it is now commonplace for astronomy grad students *NEVER* to schedule telescope time ... for their generation of astronomers, observational research is predominantly database mining.<br /><br />Neither of these two cases reflects ignorance on the part of students; rather they reflect ongoing selective sweeps with respect to the profession-defining questions that Lance explored last week. e.g. "What is an electrical/quantum systems engineer?" ... "What is an astronomer?" <br /><br />It will not surprise me if many responses to this post reflect selection sweeps, because these are becoming ubiquitous in modern academia.<br /><br />A funny (and purely mathematical) example that comes to mind is "Grothendieck's Prime": the number 57. :)John Sidleshttp://www.mrfm.orgnoreply@blogger.com