This semester my Graduate Complexity Course has nine students in it.
It had not been offered for two years (when it had around 20) so the demand,
such as it is, should have built up. Of my 9 students only about 4 are theorists.
Why did the UMCP Grad Students in theory NOT take grad complexity?
(I am regarded as a good teacher so I'm not the reason.)
The reason is that there were two competing grad theory courses in terms of the requirements - Algorithmic Game Theory and Comp Bio.
This raises the question which I ask, as always, non-rhetorically. Is a theory grad student in ALGORITHMS, who is NOT working in Alg Game Theory better off taking Grad Complexity or Alg Game Theory? Alg Game Theory (or some other
type of algorithms course that is not quite what she does) is perhaps more in their interest and perhaps more the kind of thing she might switch to later. But
`every theory grad student should know complexity theory', or more precisely
`every theory grad student in algorithms should know about lower bounds on algorithms, e.g., PCP, aproximatin lower bounds, maybe a few other things like Unique Game Conj and some concrete lower bounds' This is true philosophically but time is short.
My course has in it (1) Complexity classes L, NL, P, NP, PSPACE, EXPSPACE some problems complete there and all known relations, (2) All of the machinery to do GI NPC implies PH collapses, (3) PCP and lower bounds on approximation.
(DO NOT prove the full PCP theorem). If time permits I may do some concrete lower bounds (PARITY not in constant depth or some Proof Theory lower bounds). OH, I may do SHARP P and Toda's theorem also, but this semester we had some snow days and that ended up not being done, though I did do
Valiant-Vazarani and told them ABOUT SHARP P without proofs.
When Jon Katz teaches it I think he does some Derandomization and no concrete lower bounds (JON- if you are reading this you an comment and correct me).
The question of Comp Theory VS ALG Game Theory is really asking how well rounded one should be and in what sense. Someone who works on Approx Algs who takes Alg Game Theory could say that this DOES make them well rounded. Complexity theory is further away from their interests and from anything they may work on, but `every theory grad student should know it' Or should they?
I am not complaining about having only nine students (I don't have a TA so I
do all of the grading- so in that sense its great!) but I ask YOU the question,
how important is Complexity Theory (my course or perhaps some other course) for a grad student in algorithms to know?
As a graduate student it's not yet my place to debate its importance, but I will say I've always found complexity to be *cool.* It deals with those big philosophical questions that have more of a wow factor than "improve the approximation ratio for X." And I view it as a sort of common language for the rest of theory (crypto, quantum, approximation algorithms, learning theory, etc.), but this could be a consequence of the order I took my courses.
ReplyDeleteI wanted to take it, but didn't feel like it is necessary for my research. Another class took priority because of breadth requirements.
ReplyDeleteI would argue that one should consider taking it BECAUSE it isn't necessary for their research. If it's necessary for your research, you'll likely learn about it on your own. Once at the graduate level my feeling is that at least some classes should cover things that you find interesting but will NOT go out and learn on your own.
DeleteI think it should be mandatory... (not Toda's theorem, not concrete lower bounds, but add probabilistic computations and interactive protocols).
ReplyDeleteI must admit I teached it to undergrads twice :-)
At UIUC, complexity is part of the written qual for theory PhD students so they all take it whether they like it or not :).
ReplyDeleteThe reason why UMD does not have written quals?
DeletePresumably UMD removed written quals to save me -- personally -- the waste of time!
DeleteIn our faculty discussion breadth vs. depth issue comes up frequently. There is a camp that want more freedom for students and their advisors to pick the topic a student should study and there is the another camp that thinks you can't be given a CS degree without knowing some general topics. Complexity theory is cool and important but so are other topics and there are many. Algorithms and in particular AGT and ComBio have an additional plus in that they help students find jobs and positions, complexity theory doesn't.
ReplyDeleteNope-- I will never get a job because I took a class on the side.
DeleteSTEM students nowadays (as it seems to me) are evolving a keen appreciation of three STEM schools:
ReplyDeleteThe Jeremians This prophecy-minded STEM school's sacred texts include Clay Shirky's The End of Higher Education's Golden Age (2014) and Alberts et al Rescuing US Biomedical Research From Its Systemic Flaws (2014). The Jeremian STEM school perceives problems clearly … solutions, not so much.
The Aristotelians This tradition-minded STEM school honors rigorous conclusions elegantly deduced from time-honored postulates. Sacred texts include Dirac's Principles of Quantum Mechanics (1932), The Feynman Lectures (1965) and Lewis and Papadimitriou Elements of the Theory of Computation (1982). The Aristotelian STEM school prefers conclusions that are rigorous and metrics that are euclidean.
The Rising Tide This revolution-minded STEM school honors transgressive texts, such as appear in the April 2014 theme issue of Notices of the AMS, including (for example) Chen et al. OpenFOAM for Computational Fluid Dynamics, and Bohun Introduction to Modern Industrial Mathematics. The Rising Tide STEM school prefers literature that is wide open, tools that are free, conclusions that follow from non-traditional ("burning arrow") postulates, and enterprises that grow exponentially. The Rising Tide folks foresee (annoyingly) that their STEM revolution already is irretrievably underway.
Conclusion Who's right? It scarcely matters, because the vigor and integrity of the STEM community requires balanced elements of prophecy, tradition, and revolution. This said, young STEM researchers nowadays sense — correctly as it seems to me — that the Rising Tide STEM school offers the most substantial prospects of creating dignified, family-support jobs in the required global-scale abundance.
A better question is why Complexity is being offered so infrequently at UMCP. Is it a lack of interest? A lack of professors capable or willing to teach it? An administrative problem?
ReplyDelete- I've taught complexity only twice, and the topics varied a bit each time. (You can see the lecture notes for the last time I taught the class here: http://www.cs.umd.edu/~jkatz/complexity/f11/). The last time I taught, I did cover derandomization as well as parity not in AC0.
ReplyDelete- Complexity is offered infrequently at UMD for a combination of many reasons. Bill and I have been the only ones to teach it the last 10 years; when I teach a grad course I tend to do grad crypto, and Bill prefers to teach special-topics courses. IN addition, the fact that few students take it when it is offered makes us less likely to offer it more often.
A clarification: Bill and I are not the only ones to teach complexity at UMD in the past 10 years... (thanks, Bill, for correcting me!)
Delete"IN addition, the fact that few students take it when it is offered makes us less likely to offer it more often."
DeleteThis is because of the exact problem offered in the original post -- since it is offered so seldom, students interested in taking it might give it up for a course that may reap "immediate benefits" whereas on the other hand if it were offered more often then students would not have to make these choices, and more students would take it over all.
This should not be. Please indulge me this rant: Algorithmic Game Theory and Comp Bio ARE and SHOULD BE electives for theory students. Complexity theory is ESSENTIAL. If one knows complexity theory well, one can very easily make contributions in comp bio and algorithmic game theory. However, the other way around is a tough road. I am so tired of CS programs sacrificing fundamental aspects of CS education for whatever the hot topic du jour is whether that be Algorithmic Game Theory, Comp Bio, Machine Learning, or Big Data (shudder). (An aside rant: I think ML and Big Data are actually just statistics with a sales job on top and most really excellent, theoretical statisticians are too humble and too knowledgeable to claim more than they have actually done as is the case in these two hot fields.) I am also really tired of seeing so many candidates with these hot topic buzzwords on their CVs. It's just too insincere and nauseating and it is diluting real scientific work. Thank you for your indulgence. Rant over.
ReplyDelete