Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Wednesday, February 08, 2006
Surprising Gasarch
In the fourth Complexitycast, Bill
Gasarch returns and discusses his Surprising Results post
and his recent guest blogger experience.
MP3
(25:42, 4.4MB)
hep-th/0602072 Title: Computational complexity of the landscape I Authors: Frederik Denef (KU Leuven), Michael R. Douglas (Rutgers and IHES) Comments: JHEP3 Latex, 53 pp, 2 .eps figures
so, i think any result can be surprising. here's how:
1.no prior experience to problem. 2.amazing lecturer/mentor/whathaveyou 3.historical perspective on the problem 4.buildup of result in stages (not necessarily everything the community went through, but enough so that students are impressed) 5.proper motivation (why the problem was so important. i.e. why they got funded) 6.enough intelligence to follow the professor and reasoning and appreciate what is going on (not saying but my computer is sooooo fast it can sort a million integers in a second, those kids need their knees broken)
seriously, median-finding in O(n) time was amazing when i first saw it. so was every convex hull algorithm. so was fibonacci heaps because it was motivated by the buildup of the single source shortest paths problem. so was dynamic programming, even though i'd seen that one before it was made magical again before my eyes. ditto for every single result in computational geometry (in the class i took).
note the CLRS book fucks up the fib heap/sssp order.
of course, really this comes down to your mentor/professor and some ability and willingness on the part of the student to be taken on a trip.
+100 points for whoever guesses my professor.
(also of note: i was bored by most of complexity theory when i took it because the magic wasn't there. also you have to go a lot farther to make tapes and turing machines seem applicable to modern computers. you must make the students suspend their disbelief for a few months there in that class.)
The complexitycast mentions the issue that people never respond to specific questions. I've noticed this too. This shows up on Usenet as well - the easiest way to get an answer to a question is to say something wrong.
The other thing I've noticed is that trying to do a two-part post and ask for comments on the second part doesn't work. Usually I end up with comments on the first part (if any comments at all). The best example of this was a post I did talking about a microeconomic model that derives tenure for academics from some assumptions about the labor market -- I really wanted to think about a model for predicting what academics work on, modelling bandwagoning in topics, etc., and use that as an example of such a model. Instead, everyone started talking about tenure. Oops.
Incidentally, a friend of mine did his senior thesis in comparative literature on "the epistle dedicatory." That is, the letters at the front of Renaissance books thanking the patron. At the time I thought it was just an amusing piece from the past...but that was before I started writing papers! (I am exaggerating.)
Finally, my two votes for surprising results: 1) 1998's random oracle counterexamples by Canetti, Goldreich, and Halevi, showing that the Random Oracle Model is not sound, and 2) 2001's result by Barak et al. showing obfuscation is impossible. For me, 1) was a surprising theorem, in that I would not have believed it was true had you asked me at the time. 2) was a unsurprising theorem with a surprising proof, in part because of the way it extends to several different natural formalizations of the vulgar notion of "obfuscation."
I don't consider commenting on a blog unless I feel I have something to contribute or a question.
As far as money goes, maybe it was even worse before. Adam Smith writes about students being given permits to beg in The Wealth of Nations. (I can't find the reference)
Will there be a Heisenberg effect? Now that readers have heard your comments on commenters will that change the kinds of comments left?
ReplyDeleteCheck the arXiv.org for following link.
ReplyDeletehep-th/0602072
Title: Computational complexity of the landscape I
Authors: Frederik Denef (KU Leuven), Michael R. Douglas (Rutgers and IHES)
Comments: JHEP3 Latex, 53 pp, 2 .eps figures
so, i think any result can be surprising. here's how:
ReplyDelete1.no prior experience to problem.
2.amazing lecturer/mentor/whathaveyou
3.historical perspective on the problem
4.buildup of result in stages (not necessarily everything the community went through, but enough so that students are impressed)
5.proper motivation (why the problem was so important. i.e. why they got funded)
6.enough intelligence to follow the professor and reasoning and appreciate what is going on (not saying but my computer is sooooo fast it can sort a million integers in a second, those kids need their knees broken)
seriously, median-finding in O(n) time was amazing when i first saw it. so was every convex hull algorithm. so was fibonacci heaps because it was motivated by the buildup of the single source shortest paths problem. so was dynamic programming, even though i'd seen that one before it was made magical again before my eyes. ditto for every single result in computational geometry (in the class i took).
note the CLRS book fucks up the fib heap/sssp order.
of course, really this comes down to your mentor/professor and some ability and willingness on the part of the student to be taken on a trip.
+100 points for whoever guesses my professor.
(also of note: i was bored by most of complexity theory when i took it because the magic wasn't there. also you have to go a lot farther to make tapes and turing machines seem applicable to modern computers. you must make the students suspend their disbelief for a few months there in that class.)
The complexitycast mentions the issue that people never respond to specific questions. I've noticed this too. This shows up on Usenet as well - the easiest way to get an answer to a question is to say something wrong.
ReplyDeleteThe other thing I've noticed is that trying to do a two-part post and ask for comments on the second part doesn't work. Usually I end up with comments on the first part (if any comments at all). The best example of this was a post I did talking about a microeconomic model that derives tenure for academics from some assumptions about the labor market -- I really wanted to think about a model for predicting what academics work on, modelling bandwagoning in topics, etc., and use that as an example of such a model. Instead, everyone started talking about tenure. Oops.
Incidentally, a friend of mine did his senior thesis in comparative literature on "the epistle dedicatory." That is, the letters at the front of Renaissance books thanking the patron. At the time I thought it was just an amusing piece from the past...but that was before I started writing papers! (I am exaggerating.)
Finally, my two votes for surprising results: 1) 1998's random oracle counterexamples by Canetti, Goldreich, and Halevi, showing that the Random Oracle Model is not sound, and 2) 2001's result by Barak et al. showing obfuscation is impossible. For me, 1) was a surprising theorem, in that I would not have believed it was true had you asked me at the time. 2) was a unsurprising theorem with a surprising proof, in part because of the way it extends to several different natural formalizations of the vulgar notion of "obfuscation."
I will never forget one exam question,
ReplyDeletewhich even after I showed I did not believe
was true...
Let C be the 1/3 cantor set on [0,1]
C + C = [0,2]
Although not a big result, it really shocked
my normally dead-on intuition.
I don't consider commenting on a blog unless I feel I have something to contribute or a question.
ReplyDeleteAs far as money goes, maybe it was even worse before. Adam Smith writes about students being given permits to beg in The Wealth of Nations. (I can't find the reference)