Article about DEC Folk

Interesting Wired article talking about a bunch of people I worked with back when I was at Digital Systems Research Center, and their big effect on Google.  It's great to see them get credit for all they've done.

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. 

Yale Daily News, continued

I pointed to this article in the Yale Daily News about computer science when it came out in April.  Giorgos just pointed me back to it again, and I'd have to say, it's worth looking at again for the comments, which I'm still trying to grok.   

MMDS

I'm hanging out at MMDS -- the Workshop on Algorithms for Modern Massive Datasets at Stanford.  The crowd is surprisingly huge, with a greater number of people in "adjacent" areas (math/statistics/machine learning) and industry than is normal for me.   It's very exciting to see such wide-scale interest.

Right now, though, the non-theorists are having to listen to a very theoretical session:

11:00 - 11:30 Ping Li Probabilistic Hashing for Efficient Search and Learning on Massive Data 11:30 - 12:00 Ashish Goel Real Time Social Search and Related Problems 12:00 - 12:30 Andrew Goldberg Hub Labels in Databases: Shortest Paths for the Masses

Fun stuff!

I just enjoyed an interesting aspect of Ashish's talk.  He was putting the social search problem in a framework where you first do preprocessing on the social graph (using distance oracles for shortest paths), and then do incremental updates (corresponding to when someone say does a new Tweet, you update the keywords associated with that user).  I like it because I talk about the preprocessing + query answering approach (using examples like suffix trees, least common ancestor data structures) in my undergrad class.  This preprocessing + incremental update + query answering example in the context of social search would make a nice addition (that students can hopefully appreciate), if I could simplify it in a reasonable way.

On NPR (Morning Edition)

Groupon is being discussed on NPR (Morning Edition), which means we get a phone call again.  Our graphs are reproduced on the site, and John Byers speaks for us (Giorgos and me with John).

Anniversary

Today I get to celebrate that I'm two years done with my three year stint as "Area Dean for Computer Science" (chair).  Whoever the new person is, they're supposed to start July 1, 2013.  I've already starting encouraging the possible successors to step up.  (Indeed, I've already started to become a bit more ambitious.  I'm hoping to line up the next 3 or 4 people for the position;  no tag backs for a decade...)

It's not that I'm unhappy with the job.  (I realize that statement is a no-op;  I have to say that.  I'm trying to get others to take over.)  I'm pleased with what I've been able to do.  We tenured two faculty last year (Hanspeter Pfister and Radhika Nagpal);  we promoted another (Yiling Chen);  we hired a new faculty member (Yaron Singer);  and we've just had a junior faculty search for next year approved.  We're (still) a relatively small department with a lot of demands on us, and I came in with a clear goal for us for faculty growth.  I feel we've been successful in this regard.  There have been some other nice successes, such as the new SEAS Design Fair I helped manage and organize, which I expect will be an annual event.  And I'm able to act as the faculty interface with the administration in various ways, helping, I hope, keep things running smoothly.

But I'll also be happy to step down.  I'm overdue for a sabbatical already (the price of agreeing to a 3-year job).  I'll enjoy getting the time back for other things.  (Though I expect I'm being unrealistic, and that some other committee or administrative task will try to absorb the time.)  I like the "serve 3 years and out" model (though I see weaknesses in it too, in terms of setting up longer term infrastructures).  I enjoy taking on new experiences and challenges, so trying out "management" (if that's what this job is) has been interesting and educational.  But in one more year, another change will be good.

    

Simons Institute Call

Alistair Sinclair asked me to post the call at http://simons.berkeley.edu/cfp_summer2012.html for the Call for Proposals for Simons Institute programs.  The deadline is mid-July.

Worth noting --  two semester-long programs for Fall 2013 are already decided: these are "Real Analysis in Computer Science," organized by Gil Kalai, Subhash Khot, Michel Ledoux, Elchanan Mossel, Prasad Raghavendra and Luca Trevisan; and "Theoretical Foundations of Big Data Analysis," organized by Stephen Boyd, Peter Buehlmann, Michael Jordan, Ravi Kannan, Michael Mahoney and Muthu Muthukrishnan.  Get your tickets now.

New SIGACT Officers

Lance informs me we have newly elected officers at SIGACT.

Chair:  Paul Beame

Members-at-Large:

Venkatesan Guruswami
Rocco Servedio
Avrim Blum
Tal Rabin

Congratulations/condolences to the winners.  I'm sure Paul will do a great job --
he's a regular commenter here, and I always find his opinions incredibly well thought out,
even in (rare) cases where I disagree.  I can't wait to see what he does.

I'd also like to thank Lance for his service as chair the last few years.  He had the unenviable
job of keeping the community happy, preserving the structures that have served us well while
trying to introduce new ideas where there looked to be room for improvement.  I think he's
done a great job, generating some controversy and discussion while keeping everything moving forward.  He (and the other SIGACT volunteers) deserve our thanks.  So, thanks!

Mihai Memorial Blog

I received the following note from Mikkel Thorup and Alexandr Andoni.
I believe it's appropriate to share:

Dear friends of Mihai,

We made a blog in Mihai's memory. Celebrating Mihai's energy and
spirit, please cheer him with a glass of wine (or other spirits), and
send in a picture to be posted on the page:
http://mipmemorial.blogspot.com

Best regards,
Mikkel and Alex

Many of you have left wonderful comments about Mihai here.  I hope you'll copy them over and possibly add to them at the memorial site.  

Sad Passing: Mihai Patrascu

[** UPDATE **]

Dear friends of Mihai,

We made a blog in Mihai's memory. Celebrating Mihai's energy and
spirit, please cheer him with a glass of wine (or other spirits), and
send in a picture to be posted on the page:
http://mipmemorial.blogspot.com

Best regards,
Mikkel and Alex

[** UPDATE END **]



Mikkel Thorup just sent me the following to post regarding Mihai Patrascu. 

---------------

Mihai Patrascu, aged 29, passed away on Tuesday June 5, 2012, after a
1.5 year battle with brain cancer. Mihai's carreer was short but
explosive, full of rich and beautiful ideas as witnessed, e.g., in his 19
STOC/FOCS papers.

Mihai was very happy about being co-winner of the 2012 EATCS Presburger Young Scientist Award for his ground-breaking work on data
structure lower-bounds. It was wonderful that the community stood up
to applaud this achievement at STOC'12. Unfortunately he will not make it to the award ceremony on July 10 at ICALP.  Mihai's appreciation
for the award shows in the last post on his blog
http://infoweekly.blogspot.com/.

I was fortunate enough to be one of Mihai's main collaborators. One of
the things that made it possible to work on hard problems was having
lots of fun: playing squash, going on long hikes, and having beers
celebrating every potentially useful idea.

On this last note, Mihai's wife Mira tells me that she does not want
any flowers and that his funeral will be back in Romania.
However, she wants people to have a glass of wine in Mihai's memory,
thinking about him as the inspired and fun young man that he was.

Verification in the Cloud [Guest Post by Justin Thaler]

[Justin talks about his upcoming work, to be presented at HotCloud.]

For the past few years, Michael and I, along with our awesome collaborators, have worked towards developing practical protocols for verifying outsourced computations. In roughly chronological order, the relevant papers are here , here , here , here , and most recently here . In this last paper (joint work with Mike Roberts and Hanspeter Pfister ), we really tried to push these protocols into practice, largely by taking advantage of their inherent parallelizability: we'll be presenting it at HotCloud next week, and it is the main impetus for this blog post. My hope here is to give a (somewhat) brief, unified overview of what we've accomplished with this line of work, and how it relates to some exciting parallel lines of inquiry by other researchers.

Our main motivation is that of Alice, who stores a large data set on the cloud, and asks the cloud to perform a computation on the data (say, to compute the shortest path between two nodes in a large graph, or to solve a linear program defined over the data). Of course, Alice may be a company or an organization, rather than an individual. The goal is to provide Alice with a guarantee that the server performed the requested computation correctly, without requiring Alice to perform the requested computations herself, or even to maintain a local copy of the data (since Alice may have resorted to the cloud in the first place because she has more data than she can store). In short, we want to save Alice as much time and space as possible, while also minimizing the amount of extra bookkeeping that the cloud has to do to prove the integrity of the computation.

Alice may want such integrity guarantees because she is concerned about simple errors, like dropped data, hardware faults, or a buggy algorithm, or she may be more paranoid and fear that the cloud is deliberately deceptive or has been externally compromised. So ideally we'd like our protocols to be secure against arbitrarily malicious clouds, but sufficiently lightweight for use in more benign settings. This is an ambitious goal, but achieving it could go a long way toward mitigating trust issues that hinder the adoption of cloud computing solutions.

Surprisingly powerful protocols for verifiable computation were famously discovered within the theory community several decades ago, in the form of  interactive proofs , PCPs , and the like. These results are some of the brightest gems of complexity theory, but as of a few years ago they were mainly theoretical curiosities, far too inefficient for actual deployment (with the notable exception of certain zero-knowledge proofs).

We've been focusing on interactive proof methods, and have made substantial strides in improving their efficiency. One direction we've focused on is the development of highly optimized protocols for specific important problems, like reporting queries (what value is stored in memory location x of my database?), matrix multiplication, graph problems like perfect matching, and certain kinds of linear programs. Many of these are provably optimal in terms of space and communication costs, consist of a single message from the cloud to Alice (which can be sent as an email attachment or posted on a website), and already save Alice considerable time and space while imposing minimal burden on the cloud, both in theory and experimentally. But for the rest of this post I will focus on *general-purpose* methods, which are capable of verifying arbitrary computations.

The high-order insights of this line of work are as follows. The statements below have precise theoretical formulations, but I'm referring to actual experimental results with a full-blown implementation. Note that a lot of engineering work went into making our implementations fast, like choosing the "right" finite field to work over, and working with the right kinds of circuits.

1) We can save Alice substantial amounts of space essentially for free. The reason is that existing interactive proof protocols (such as Interactive Proofs for Muggles by Goldwasser, Kalai, and Rothblum, which is the protocol underlying our implementation) only require Alice to store a fingerprint of the data. This fingerprint can be computed in a single, light-weight streaming pass over the input (say, while Alice uploads her data to the cloud), and serves as a sort of "secret" that Alice can use to catch the cloud in a lie. The fingerprint doesn't even depend on the computation being outsourced, so Alice doesn't need to know what computation she's interested in until well after she's seen the input, and she never needs to store the input locally.

2) Our implementation already saves Alice a lot of time relative to doing the computation herself. For example, when multiplying two 512x512 matrices, Alice requires roughly a tenth of a second to process the input, while naive matrix multiplication takes about seven times longer. And the savings increase substantially at larger input sizes (as well as when applying our implementation to more time-intensive computations than matrix multiplication) since Alice's runtime in the protocol grows roughly linearly with the input size. So I'd argue that verifiable computation is essentially a solved problem in settings where the main focus is saving Alice time, and the runtime of the cloud is of secondary importance. At least this the case for problems solvable by reasonably small-depth circuits, for which our implementation is most efficient.

3) We've come a long way in making the prover more efficient. Theoretically speaking, in our ITCS paper with Graham Cormode , we brought the runtime of the cloud down from polynomial in the size of a circuit computing the function of interest, to quasilinear in the size of the circuit. Practically speaking, a lot of work remains to be done on this aspect (for example, our single-threaded cloud implementation takes about 30 minutes to multiply two 256 x 256 matrices, and matrix multiplication is a problem well-suited to these sorts of protocols), but we are in much better shape than we were just a few years ago.

4) All of the protocols (special-purpose and general-purpose alike) are extremely amenable to parallelization on existing hardware. This holds for both Alice and the cloud (although Alice runs extremely quickly even without parallelization, see Point 1). For example, using GPUs we can bring the runtime of the cloud to < 40 seconds when multiplying two 256 x 256 matrices. Obviously this is still much slower than matrix multiplication without integrity guarantees, but we're now just one or two orders of magnitude away from undeniable usefulness.

The extended abstract  appearing in HotCloud (which should be viewed largely as an advertisement for the arxiv version) can be found here . We tried hard to give an accessible, if very high level, overview of the powerful ideas underlying interactive proofs, which I hope will be useful for researchers who are encountering verifiable computation for the first time.  Slides describing the entirety of this line of work in more detail can be found here .

I want to close by mentioning two exciting lines of work occurring in parallel with our own. First, Ben-Sasson, Chiesa, Genkin, and Tromer are working toward developing practical PCPs, or probabilistically-checkable proofs (see their new paper here ). The PCP setting is much more challenging than the interactive proof setting we have been working in above: in a PCP, there is no interaction to leverage (i.e. the cloud sends a single message to Alice), and moreover Alice is only permitted to look at *a few bits* of the proof. The latter may seem like an artificial constraint that doesn't matter in real outsourcing scenarios, but it turns out that building a practical PCP system would buy you quite a bit. This is because one can throw certain cryptographic primitives on top of a PCP system (like collision-resistant hash functions) and get a wide variety of powerful protocols, such as succinct arguments for all of NP (i.e., protocols requiring very little communication, which are secure against computationally bounded adversaries). The work of BSCGT appears to still be in the theoretical stage, but is very exciting nonetheless. Check out their paper for more details.

Second is work of Setty, McPherson, Blumberg, and Walfish, from NDSS earlier this year (see their project page here ). They implemented an argument system originally due Ishai, Kushilevitz, and Ostrovsky, and bring the runtime of the cloud down by a factor of 10^20  relative to a naive implementation (yes, I said 10^20; this again highlights the considerable engineering work that needs to be done on top of the theory to make proof or argument systems useful). Our protocols have several advantages not shared by SMBW (like security against computationally unbounded adversaries, and the ability to save the verifier time even when outsourcing a single computation), but this is another big step toward a practical implementation for verified computation. It looks like related work by Setty, Vu, Panpalia, Braun, Blumberg, and Walfish will be presented at USENIX Security 2012 as well (see the conference page here ).

The golden age for negative applications of interactive proofs and PCPs (such as hardness of approximation results) arrived over 15 years ago, and continues to this day. Perhaps the time for positive applications is now.

More Entrepreneurial Harvard?

One thing I noticed talking to CS graduates from Harvard this year is -- entirely anecdotally -- more seem to be going to small start-ups.  This has been an increasing trend the last few years, and strikes me as a big change.  When I was a student, most CS grads went one of the safe and successful routes of going to Microsoft, Wall Street, or one of the name brand consulting firms.  (Some losers went to grad school.)  When I started as faculty, this basic framework still seemed pretty much in place -- the most notable change was that over the years Google took up a good chunk of Microsoft's previous mind-space. 

Assuming it's true (and I think it is), there are many things that could be bringing about the change.  Harvard in many ways is trying to promote it -- in CS our classes are much more "project-based", there's a student Hack Harvard group arranging sponsored Hack Nights, and there are institutional developments like the Harvard Innovation Lab to help promote an innovation culture.  Part of it has to be attributed to the "Facebook Effect" -- we're bringing in more CS-interested people as students, and more of them are interested in startups, probably because some want to change the world, and because "a million dollars isn't cool."

One other thing that I think might be helping?  Harvard's financial aid policies, which changed significantly around 2006, making Harvard much more affordable for lower and middle class attendees.  I imagine it's a lot easier to take a risk right out of school when you're not deep in a debt hole.  At the very least, it's easier to justify to your parents why you're not (immediately) taking that high-paying job after they've paid for four years of private college.

Overall I think this is all to the good.  While startups aren't for everyone, I think Harvard grads as a group have historically been too "conservative" in choosing career paths;  it's exciting to see what may be a change in worldview.  A downside?  We've been sending noticeably fewer of our best and brightest to grad school, as they're seeking other opportunities. 

I'd be eager to hear from recent (and not-so-recent) grads their thoughts on the current startup culture...

CS 124 -- Some Student Comments

Overall, I feel I've had a very successful year, but I do have to admit:  my undergraduate class, CS 124, could have been better this spring.  I wasn't prepared for the class doubling in size from the previous year, and I had too many other things going on to make modifications on the fly.  The most common complaint was that the turnaround time to get back assignments was too long, and I agree.   I hope to find time to make some changes before next year rolls around that will help with that.  (Lots of perennial complaints about timing of things like the midterm, too -- see this previous post if you care.)  

Some interesting takeaways from the comments, which, as always, have high variance.  Answers below come from the question:  "What would you like to tell future students about this class?"  My favorite so far:

"CS124 isn't too bad for an introduction to some basic algorithms, but it could be a lot more rigorous. Fairly light workload."

What's funny if I can't tell if the student is being serious or sarcastic, the comment is such an outlier.  It's either from someone who really did well in the class and felt insufficiently challenged (there's usually a few), or someone who is making some kind of joke.  Other comments are more realistic, with different levels of "appreciation" for the difficulty:

"It is hard."
"A lot of hard work but it's worth the effort."
"The hardest class taken this far in college; painful (to be fair though I did lean a lot but not sure how efficient the process is...)"
"Often pretty difficult, but totally worth it."
"It's incredibly difficult (on a scale from 1 to impossible, it's harder than impossible)..."
"Start the psets early, and focus on them, because they are immensely rewarding. However, they are extremely brutal."


Brutal, nice adjective there.  

Some people feel algorithms is part of your health foot diet:

"This course is computer science vegetables."
"It's broccoli; you just gotta take it."  

Hmm.  I do make my kids eat their vegetables, including broccoli.  Still, perhaps not the most appetizing comparison. 

 Several people mention that the class is good preparation for job interviews.

"The material from this course is so valuable to have for tech recruitment season."
"124 is no doubt a tough class but it is also super useful. In fact, if you want a job in CS you MUST take this course. Multiple problem set questions appeared on my interviews and the algorithmic thinking helped me solve any other problem they asked. "
"Programming interview questions focus on algorithms. This class has been so helpful in getting me a job." 
"Very difficult, but very rewarding. Teaches you how to do algorithms and helps with job interviews."

I am absolutely unembarrassed about CS 124 being (in part) vocational training.  I didn't design the class to prep students for job interviews, but I'm glad to hear that it does, and very happy it plays that role.  Maybe we need to somehow move the class to the fall instead of the spring, so students can get the full class in before interview season.

Finally, of course, some of the highest variance comes in students' feelings toward the actual teacher:

"Mitzenmacher is actually a really great lecturer and motivates everything that we learn in class." 
"Professor Mitzenmacher is an excellent lecturer and he really does seem to care about his students." 
"Mitzenmacher.... definitely generates enthusiasm for the material, and lectures were very engaging and were well-motivated by relevant real world examples."

All of you, come find me after class so I can give you extra credit.  On the other hand, there are also plenty of comments like....

"Mitzenmacher's approach to teaching seems to be "present the material and not care about students' struggles.".... The material itself is quite interesting, but just be prepared for a professor like Mitzenmacher."  
Ouch. 
"I am baffled as to why Prof. Mitzenmacher is still allowed to teach this class. His lazy attitude toward teaching was frustrating and not conducive to learning."
Double-ouch. 

(I have all sorts of funny, sarcastic things to say here about not being "allowed to teach this class", but I'm sure they'd just get me in trouble later, so other faculty can mentally fill in their own joke here.)
 
To close it out, these seem like the best things to tell students who are thinking of taking my course:

"Good luck and enjoy the ride! Even though it almost killed me, I'm genuinely sad it's over."  
"Brace yourself."

Indeed.  

Non-travel

For the past few years, I've been the chair for one of the international review panels for Country X's research funding bodies.  (It's probably all a matter of public record, but no need to name Country X for this.)  I agreed to serve (and chair) the committee with one restriction -- I didn't want to fly out for an all day panel, which is apparently their standard approach.  Not that Country X isn't a wonderful destination -- were I single and/or without 3 children, I might well enjoy the chance to fly thousands of miles to Country X on their dime and spend a day or two hanging out and seeing the sights with nothing more stressful on the agenda than going through reviews for some research proposals.  But that's not the case.

Year 1 I think they were a little concerned, but I think now they're happy I'm willing to do it and are OK with the process.  Recently we had this year's meeting, over several hours on Skype, and it all worked just fine.  The size is about that of a small-ish NSF panel -- about a half dozen panelists, usually about ten or so proposals to review.  That's a very nice size for an electronic meeting -- I recognize it can get harder for multiple reasons as things get bigger.  I don't believe the lack of face-to-face presence changes the outcomes significantly -- whatever the sources of noise are, I don't think the noise is necessarily bigger with this approach.

On the plus side, we must have saved the funding agency on the order of $10,000 or more.  Air fare, hotel, etc. isn't cheap for an "international panel".  I'm sure they can find better uses for the money -- like supporting research!

I keep hoping to hear that at some point the NSF will experiment with an electronic as opposed to face-to-face panel, if only to see how it goes.  From Boston I can deal with taking an early flight to DC for a 1-day panel, but I really try to avoid 2-day panels now, and I'm aware what a drag the trip can be for west coast colleagues.  I think the NSF could corral more reviewers (like me) if serving on a panel was easier and less time-consuming, by which I really mean doesn't require a flight.     

Summer School on Massive Data Mining in Copenhagen

Rasmus Pagh asked me to advertise the following summer school he is organizing.  Looks like a good deal to me:

SUMMER SCHOOL ON MASSIVE DATA MINING

August 8-10, 2012, IT University of Copenhagen, Denmark

The summer school is aimed at PhD students and young researchers both from the algorithms community and the data mining community. A typical participant will be working in a group that aims at publishing in algorithms conferences such as ESA and SODA, and/or in data mining conferences such as ICDM and KDD. Speakers:

Michael Mahoney, Stanford University
Toon Calders, Eindhoven University of Technology
Suresh Venkatasubramanian, University of Utah
Aris Gionis, Yahoo! Research

Early registration fee (before June 15) is €90.
Organizing chair: Rasmus Pagh

Website: www.itu.dk/people/pagh/mdm12/

That Time of Year : Annual NSF Reports

I received my notice a few weeks back that it's time to fill out my annual grant reports for NSF.

I'd like to complain about it;  it's a pretty boring process, and their interface isn't that great.

But, really, I can't complain.  The NSF provides me (and my students) with money to do our work.  In return, they ask for what seems like very reasonable reporting of how that money is being used.  What have I been working on?  Who I have been working with?  Where has the work been published?  What other outcomes of the research -- in industry or education -- has there been?  These seems like very worthwhile questions for them to be asking.

One thing I don't really know is what is done with these reports after I enter them.  I hope they're useful.  I have had an NSF program manager discuss my reports with me, so I do have evidence they're being read.  (I must admit, after a program manager let me know they actually read these reports some years ago, I started taking them more seriously!)

So, strangely, this year, as I'm going through the mundane task of filling out my annual reports, I actually find that it's leaving me with a feeling a gratitude.  Thanks, NSF, for letting me and my students do all this really fun stuff!  I know I complain about the NSF when I feel there's something worth complaining about, so it only seems fair to express the gratitude when I'm feeling thankful for all they do.

 

A Little Truly Offensive Bragging (On Behalf of Harvard CS)

So which US school was the only one in the top ten for the ACM International Collegiate Programming Contest this year?

No, not MIT, Princeton, or Carnegie Mellon (tied for 18th), nor Stanford (good effort!, tied for 13th) - but Harvard, at number 7.  (Results here.) 

Congratulation to our team Spencer Liang, Alex Zhai, and Neal Wu.  (Neal has also been busy as a TF for CS 124 this year...) 

Of course, also congratulations to the many other teams, in particular the top two (who both solved 9 of the problems;  the winners won on time):

St. Petersburg State University of IT, Mechanics and Optics
University of Warsaw

Grading, Correlation vs. Causation

Final grades are finally in, thank goodnees.  With 100+ students, even entering the grades is non-trivial. 

Once again, freshman in my undergraduate Algorithms and Data Structures class receive A's at a substantially higher rate than other students.  (Way, way higher.)  My conclusion:  it's best for your grade if you take my class as a freshman.

Grading is No Fun

I'm told my exams are not nearly as much fun as I like to think they are.  (It's a very rare occurrence when someone turns in their exam early at my 3-hour final.)  I can say that this year they weren't much fun to grade. 

The issue was the large class size -- the final number was 110 (about twice the size of last year).  You'd think with more TAs it might not take too much longer to grade... but apparently there are non-linearities in there somewhere.  Anyhow, grading took about 6 hours today.  For any students who happen to be reading, I figure they'd appreciate knowing that, at least temporally speaking, I had to suffer about twice as long as they did. 

For faculty types out there, I'm curious... how much grading do you do?  For my undergrad class, I help grade the midterm and final, and take on grading the first programming assignment myself (1 of 8 class assignments).  Is this a lot, a little, more or less normal?  Comments welcome. 

Attribute-Efficient Learning (Guest Post by Justin Thaler)

[Editor's comment:  Justin has been having quite a year;  after a paper in ITCS, he's recently had papers accepted to ISIT, ICALP, HotCloud, and COLT.  In this guest post, he tells us about the COLT result.]

Rocco Servedio, Li-Yang Tan, and I recently had a paper accepted to COLT on attribute-efficient learning, which is a clean framework introduced in 1990 by Avrim Blum that captures the challenging and important problem of learning in the presence of irrelevant information. Think of a infant trying to learn whether or not an object is safe to touch. The infant's brain may be inundated with sensory information, but there may only be a few characteristics of the object that matter (is it sharp? Is it sitting on a heat source?). Or think of a scientist trying to identify the genetic causes of a certain disease that depends on the (possibly complicated) interactions of a small number of genes: the scientist may collect a massive amount of genetic data from study participants, yet only a small amount of this information is actually relevant to the function being learned (i.e., the mapping of genes to a subject's phenotype).

Thus, the goal of an algorithm for attribute-efficient learning is to run in time polynomial in the total number of attributes, n, using a number of examples which is polynomial in the description length of the function f to be learned. The latter can be substantially smaller than n if most of the attributes are irrelevant.

In its most general form, the problem of learning in the presence of irrelevant information is captured by the "junta problem". In this setting, you make no assumption other than that the function being learned depends on only k << n of its n attributes, and your goal is to learn the function in time substantially smaller than the trivial O(n^k) obtained by exhaustively checking all k-element subsets of the attributes. The uniform-distribution variant of this problem has been called the "most important open question in uniform distribution learning" in the groundbreaking paper of Mossel, O'Donnell, and Servedio (see also Lipton's blog post on the subject here).  Greg Valiant has recently made progress on this problem here.

Our goal is simultaneously more and less ambitious than MOS. On the one hand, we want to attribute-efficiently learn under arbitrary distributions, not just the uniform distribution. On the other hand, we are willing to assume not just that our functions depend on few attributes, but that the relevant attributes interact in structured ways. Specifically, we focus on attribute-efficient learning of decision lists, a problem first posed by Blum in his 1990 paper. This natural function class is (one of the few) known to be efficiently PAC-learnable, but it seems to lie on the boundary of tractability in the more challenging attribute-efficient setting. The problem has already been studied by a number of authors, see e.g. here, here, here, and here.

What did we manage to show? We give both positive and negative results. On the positive side, we build on a construction of Klivans and Servedio to give an algorithm achieving new tradeoffs between the running time and sample complexity for learning length-k decision lists over n Boolean attributes. Like most known positive results on PAC-learning under arbitrary distributions, we achieve this by constructing "uncomplicated" polynomial threshold functions (PTFs) computing any decision list. (For the uninitiated, a polynomial threshold function is exactly what it sounds like: it is a function of the form sign(p(x)), where p is an n-variate polynomial, and the complicatedness of a PTF refers to the degree of p, and the size of its coefficients). For technical reasons we actually construct something slightly more expressive than a PTF, which we call a generalized PTF, and which is just as useful for learning purposes.

We have two results on the negative side. First, we give new lower bounds on the complexity of PTFs that compute a specific and important decision list called ODD-MAX-BIT, building upon an elegant argument due to Beigel. Our lower bound strongly suggests that brand new techniques will be needed to improve on our positive result. (Parenthetically, the ODD-MAX-BIT function has played important roles in complexity theory in the past, from oracle separations to circuit lower bounds -- you can learn about many of these prior results just by typing ODD-MAX-BIT into Google).  In brief, Beigel's lower bound is tight for relatively low-degree PTFs computing ODD-MAX-BIT, but is loose or vacuous for higher-degree PTFs. Our new lower bound significantly improves upon Beigel's at higher degrees and comes close to matching our upper bound (the main gap is that our upper bound uses generalized PTFs, while our lower bound applies only to honest-to-goodness PTFs).

Our final result is to extend Beigel's lower bound, which applied only to thresholds-of-monotone-conjunctions, to thresholds of significantly more general classes of functions.

In closing, I would like to say a little about about the ideas underlying our constructions, as there is a common intuition underlying both our positive and negative results. The positive result works by breaking the decision list into "chunks", closely approximating each chunk (in the $L_{\infty}$ norm) with a low-degree polynomial, and then putting the approximations together to get a PTF for the entire decision list. The negative result shows that this approach is intrinsic: it also breaks the decision list into chunks, and shows that you can take any PTF p for ODD-MAX-BIT and turn it into a low-degree polynomial q closely approximating each chunk. We then use a new Markov-type inequality to conclude that q has to be "complicated", and hence p has to be complicated as well.

Our Markov-type inequality seems quite natural, and similar statements have apparently been known to approximation theorists for some time now. I wanted to state the result here in the hopes that it will find some other applications in TCS.

Markov's classical inequality is a statement about the derivative of a univariate polynomial in terms of its degree. In contrast, we give a bound on the derivative of a univariate polynomial in terms of both its degree and the *size of its coefficients*. For comparison:

Markov's Theorem: Let p : [-1,1] --> [-1,1] be a real polynomial with deg(p) <= d. Then max  |p'(x)| <= d^2, where the maximum is taken over all x in the real interval [-1, 1].

Our Markov-type Inequality (what I state here is a bit of a simplification of what we actually show): Let p : [-1,1] -> [-1,1] be a real polynomial with deg(p) <= d and coefficients of absolute value at most W. If max |p(x)| >= 1/2, then max |p'(x)| = O(d*log(W)), where again the maximums are taken over all x in [-1, 1].

Notice our bound is tighter than Markov's when W is smaller than 2^d.

The way I like to think about our Markov-type inequality is as follows. Since the Chebyshev polynomials are a tight example for Markov's inequality, one can interpret Markov as saying that, in order to maximize the derivative of a polynomial P of degree d which stays bounded on the interval [-1, 1], the best approach is to "spend all the allowed degree on a Chebyshev polynomial." There is also a simple example showing that our new inequality is asymptotically tight for a wide range of W's -- the tight example involves composing a Chebyshev polynomial with a monomial.  So our new Markov-type inequality is saying that in order to maximize the derivative of a polynomial of degree d and weight W which stays bounded on the interval [-1,1], the best approach is to "spend all of the allowed weight on a Chebyshev polynomial T, and then spend any remaining allowed degree by composing T with a low-weight, high-degree polynomial (namely, a monomial)."  It actually turns out that this same intuition underlies our positive result, which allowed us to improve over the Klivans-Servedio construction when the degree of the (generalized) PTF is relatively high.