Tuesday, August 07, 2012

Like a Movie Meteor...

The new semester is hurtling toward me.

This semester I get to teach one of my graduate courses, the one I named Algorithms at the End of the Wire sometime over a decade ago, when that seemed like an appropriate title.  Students seem to have learned that the appropriate subtitle for the course is something akin to:  "Things Professor Mitzenmacher is working on, is interested in, or otherwise likes."  Standard topics therefore include ranking and search engines (Pagerank + variants), data sketches and summaries, coding, and compression.

Since I teach it every other year, I try to introduce new topics into the mix where appropriate.  Generally, I'm looking for two things:

1)  Topics that have an interesting mix of theory and practice.  The class is based on paper-reading, so it's particularly fun (for me) to try to find a topic where I can assign one theoretical paper and one practical paper.  This yields interesting room for comparisons and contrasts, induces (I can only hope) interactions between systems and theory students in the class, and (again I can only hope) ensures that everyone gets something out of at least one of the papers.
2)  Topics in my bailiwick.  Networking (including social networking!) is always good;  connections between "EE theory" and "CS theory" are nice;  big data topics, including database or cloud style applications are very welcome.

So what papers in the last 2-3 years, say, really need to be added to the class reading list?  Where are the new and exciting places where theory and practice are meeting to produce exciting breakthroughs (that, ideally, can be covered in couple of lectures)?  Or, as another way to think about it, what should I really be learning about?  Please let me know in the comments.    
PS:  Yes, I haven't been blogging much.  I've been having a perfectly enjoyable summer without blogging.  I've been busy with vacation, kid time, other lazy time, consulting work, the occasional bit of "Area Dean" administration, and, of course, my day job -- a few papers have been submitted, a few more are at various stages in the pipeline.  But I suppose with the summer tailing off I'll have more reason to be blogging again. 


Rasmus Pagh said...

Practical/application paper:

Four degrees of separation, really. http://vigna.di.unimi.it/ftp/papers/FourDegreesReally.pdf

Theoretical paper:

HyperANF: Approximating the neighbourhood function of very large graphs on a budget.

Anonymous said...

Practical/application paper:
SmartRE: An Architecture for Coordinated Network-wide Redundancy Elimination (http://pages.cs.wisc.edu/~akella/papers/sigcomm228-anand.pdf)

Theoretical paper:
Memory-Assisted Universal Compression of Network Flows (http://users.ece.gatech.edu/~abeirami3/INFOCOM12-NetComp.pdf)

Anonymous said...

I'll be a student in your class this fall.

Interval estimation for binomial proportions and for the difference between binomial proportions comes up all the time at the end of the wire. E.g., in choosing which web site design is better, which ad is more compelling, etc.

Here are a couple of papers on these topics. They both favor the Wilson interval.

Interval Estimation for a Binomial Proportion, Statistical Science 2001 V16, No2, 101-133, Brown, Cai, DasGupta

Interval Estimation for the Difference Between Independent Proportions: Comparison of Eleven Methods, Statistics in Medicine 17, 873-890 (1998), Newcombe

Anonymous said...