Manuel Blum: Advice to a beginning graduate student

http://www-2.cs.cmu.edu/~mblum/research/pdf/grad.html

by r11t • 16 years ago

55 16 16 years ago

www-2.cs.cmu.edu

jdp23• 16 years ago

A classic from 2001.

I was a grad student at Berkeley in the 80s in Theoretical Computer Science before heading off in a different direction, and got as far as taking my oral prelims from Manuel Blum and Richard Karp. No pressure! Rather embarassingly I forgot the Blum speedup theorem until I was prompted for it. They were both very nice about it though.

forensic• 16 years ago

most of it only applies to a few classical hard sciences - math, physics, chemistry, engineering

a lot of it doesnt even apply to CS in my opinion

p_nathan2• 16 years ago

really? It seems very applicable to CS research.

djcapelis4• 16 years ago

I suppose that depends on what you think of when you say CS research. CS research is very different depending on where you do you work, even the way authors are ordered on papers changes depending on how close to mathematics you work. Parts of this advice seem a better match for the theory side of the field than the systems side, for instance. In the systems side we often find it helpful to tell people to stop trying to overthink things, shut up, and code. (The systems will show you how they work when you're working with them, if you don't understand something: run an experiment.) In the theory side (where the author did his work) it is much more common to tell the students to think more instead.

JonnieCache• 16 years ago

He may have won the turing prize but he's apparently forgotten what linebreaks are for in written english.

sliverstorm• 16 years ago

Didn't he just write an entire article discussing how a PhD must know everything about a domain so small as to be nearly nothing? Practically illustrates what he was talking about- just because he won the turing prize doesn't mean he has to know anything about easy reading & page layout.

HilbertSpace• 16 years ago

I see Blum's advice as very misleading and a disservice to all concerned.

Here is my view (worked for me):

Note that the main goal is the Ph.D. A second goal is, if you wish, a start on capabilities in research.

Okay, for both, especially the first, there is a condition that is essentially both necessary and sufficient: PUBLISH.

Right: F'get about the 'dissertation' for now. Instead, just PUBLISH.

Why? At many of the best research universities, the official criterion for a Ph.D. dissertation is "an original contribution to knowledge worthy of publication". So, publish (did I mention that before?) and remove all doubt.

Note: Typically just publishing is easier than slogging through all the nonsense of dissertation proposal, research on a problem from a dissertation advisor, getting the dissertation approved by a committee, etc.

Now, what to publish?

Pick a problem and solve it. The usual criteria for publication are "new, correct, and significant".

Pick your own problem. Try hard to avoid a problem given by a prof.

How to solve it? First remember that in essentially all fields, the most admired research presents a mathematical solution. So, get one.

How to do that? Study appropriate mathematics. For the 'computing', mostly f'get about CS because for computing problems, compared with the math, it's next to junk.

How to pick a problem? To help meet the 'significant' part, pick a problem with some obvious practical importance. Typically find this problem off campus. E.g., maybe do something in server farm monitoring, performance, cost, response to load uncertainty, etc.

Broad solution direction: Find 'optimal' means for attacking the ubiquitous uncertainty.

How to say that your solution is significant? Get a solution that is provably 'optimal' in some sense. In particular, don't try to plow ground in some theoretical direction starting where all the profs broke their plows. Especially, f'get about P versus NP.

To get a math solution, start by studying, guess what, right, math.

Summary: Pick a practical problem that is clearly of importance. Use math to get 'new, correct, significant' solution. Publish the solution.

If one such paper is enough, fine. Else publish about three papers, likely on the same problem, that is, as one 'research stream', stack up the papers, put on a title page, put a staple in the UL corner, and submit it. Your profs have to admit that your work has been judged 'new, correct, and significant' and definitely is 'worthy of publication'.

For a better start on research, do the same thing but just do it a little deeper, especially in the math.

What math? Linear algebra -- through Halmos. Modern algebra -- pick something, maybe old Birkhoff and Mclane, Herstein, or Lang or something newer. Advanced calculus -- through Rudin. Measure theory and functional analysis -- the real half of Rudin's R&CA and Royden. Optimization -- linear programming, linear programming on networks (often get integer programming for free -- looks NP-complete but it's not), nonlinear programming (especially the Kuhn-Tucker conditions). Probability based on measure theory -- Breiman, Chung, Neveu, Loeve, Chow and Teicher. The above is a bit minimal; more could be from important up to really valuable.

Generally you are trying to find tools in math not yet well exploited for problems in computing. So, if find something relatively new in math, then almost certainly it has not yet been well exploited.

Under no circumstances take seriously anything in math done by any CS prof; in particular, totally flush 'machine learning, artificial intelligence, and data mining' -- good problems but total puke for work. Stay with math from names such as I listed: You'll be flying in luxury at Mach 3 at 40,000 feet while the CS profs are still slogging in mud and covered in puke.

Study some mathematical statistics -- hold your nose at how badly they do the math.

Good way to get tight bounds: Use the martingale inequality, fairly easy to apply and one of the strongest in math. See examples of Talagrand and Rhee. Yes, they got a lot of nice papers getting some tight bounds on, right, even NP-complete problems.

Generally the key is the math, and in the math, especially if go to seminars by the best people, can find 'themes' and 'directions' that can result in research 'paradigms' and lots of papers.

Then get on with making money!

wittgenstein• 16 years ago

"For example, Finite Automata can add but not multiply."

Can someone please explain why this is true? If it can add, how can it not multiply if multiplication is repeated addition?

cscheid• 16 years ago

Roughly because the number of times it needs to sum to get a multiply is not constant; it depends on the input. Think about writing the automaton -- how would you know when to stop? You're only given one automaton to write, and you don't know ahead of time how big either of the input numbers are.

djcapelis4• 16 years ago

You can make the FSM repeat the addition, but you can't give it the memory it needs to know when to stop.

If you need more explanation just try implementing it, you should see where the problem is fairly quickly. :)

sesqu• 16 years ago

So how do you get it to add? Specifically, what representation of arbitrary numbers are we using with our finite automaton? Infinite read-only tape plus infinite write-only tape for output, in base 10? If so, it should be simple to do multiplication by representing the numbers in factorized form and applying our adder.

Manuel Blum: Advice to a beginning graduate student

Related Stories