I am taking over teaching our graduate CS theory course. I will be teaching to PhD students who will not become theoreticians. I want to emphasize concepts and broad knowledge, not formal proofs or training students to do formal proofs. The plan for most classes is to get the students to understand the statement of one theorem, and the significance of that theorem, with the remaining time devoted to some intuitive explanation of why the theorem is true. I want the the course to be at least a little bit broader than a standard complexity class. For example, possible topics that are not standard complexity topics:
- Impossibility of distributed consensus with faults
- von Neumann minimax theorem
- no minimum energy for computation
1) Public Key Crypto and Diffie Helman Key Exhange.
ReplyDeleteMaybe do a mini history-of-crypto so that they see this solves a 2000 year old open problem.
2) The book THE TURING OMNIBUS has many topics that
may be good.
3) Communication Complexity results:
EQ requires n+1 bits deterministically, but can do with O(log n) if
allow rand and prob of error \le 1/n.
"I want to emphasize concepts and broad knowledge, not formal proofs or training students to do formal proofs."
ReplyDeleteWhy? Are "concepts and broad knowledge" inconsistent with "formal proofs"? Shouldn't any computer science graduate student be comfortable with formal proofs? A course that covers a few important proof techniques (ie, ways of thinking) in depth seems much more interesting and useful than a laundry list of Very Important Results.
Shouldn't any computer science graduate student be comfortable with formal proofs?
ReplyDeleteShouldn't any high school graduate be comfortable with formal proofs?
Of course, I guess it depends on what you mean by "comfortable".
The ability to write non-trivial formal proofs comes from high IQ. There's little to teach here.
But anyone can understand the concept of formal proofs and write simple ones. High school graduates should already have such skills.
Why just "complexity"? If this is "the" theory grad course (for non-theorists), shouldn't you cover some algorithms as well?
ReplyDeleteIt might take two classes, but I'd suggest (at least one direction) of Shannon's theorem. Besides being an important result, it fits Jeff's criterion of covering an important proof technique (the probabilistic method), as well as some cool combinatorics.
Reed-Solomon codes.
Spend a day on Bloom filters. It's embarassing that they continue to escape our undergraduate textbooks; make sure your graduate students know them. (Concept: Hashing is good, very very good.)
I somehow always found IP=PSPACE to be a fundamentally compelling complexity result that also fits both the concepts/formal proof goal.
LP and geometric view of
ReplyDeleteoptimization including Ellipsoid method and its consequences. Formal proofs are not necessary but the ideas are easy to convey.
One or two classes on parallel algorithms and complexity? Seems like an apt topic these days.
A class on expanders? Show existence via probabilistic method.
Explain one or two applications, perhaps to P2P.
Anonymous recommends: LP and geometric view of optimization including Ellipsoid method and its consequences.
ReplyDeleteThis is a good idea IMHO. And then build upon it with a geometric survey of compressive sampling and sparse reconstruction methods, including (e.g.) RIP sampling matrices.
Then build further with geometric descriptions of model order reduction, iterative methods for solving large system of equations ...
The result would be a course focussed upon the theme of geometric methods in CS ...
Has any reader ever taught or taken such a course? :)
Pardon my unfamiliarity with CS lingo, but what are the differences betweens a formal proof and a mathematical proof? Aren't logic and TCS branches of mathematics?
ReplyDeleteWe also have an algorithms course using CLRS. So this course should cover CS theory, broadly defined, minus what is in CLRS.
ReplyDeleteKirk Pruhs
Shannon's theorems (or is that the bailiwick of another part of the department?)
ReplyDeletePCP and some of the related inapproximability results (these might be doable, since you're not emphasizing proofs).
If theory also encompasses the theory of programming languages, as I think it should, then you could teach about language expressivity: in addition to the aforementioned impossibility of consensus, I recommend to introduce Palamidessi's impossibility results on encoding mixed choice in asynchronous pi-calculus, and some of the game- and pi-calculus based full-abstraction results for sequential languages.
ReplyDeleteMy own perspective on science and technology is conditioned on Jonathan Israel's two-volume (so far) history of the eighteenth century Enlightenment, and also by the early history of the Royal Society ... both can be read as essays on the power of mathematics, science, and engineering for catalyzing federative activities.
ReplyDeleteIt seems to me that similar federative themes are emerging as being of central importance in this, the twenty-first century.
A survey of CS theory organized around the theme "sharing" might cover two or three fundamental theorems from each of the following topics: (1) cryptography (shared secrets), (2) error-correcting codes (shared information), (3) model order reduction (shared descriptors), (4) efficient simulation (shared confidence), (5) game theory (shared benefit), (6) imaging (shared vision), and (7) QIT (shared quantum entanglement!).
The pedagogic advantage of this federative perspective is that it naturally unites CS skill-sets that are hugely in-demand by employers with theorems from among the trendiest topics in theoretical CS.
You should have at least one example showing why randomized processes are more powerful than deterministic ones, a little bit of the first moment method would be good too
ReplyDeleteI have been reading "The Lady Tasting Tea".
ReplyDeletehttp://www.amazon.com/Lady-Tasting-Tea-Statistics-Revolutionized/dp/0805071342
It has some good statistics stuff in it. Its more reading.. but is a great launching point for what is possible to present.