An Unusual CS Student Blog

As I'm up working/watching a Memorial Day weekend Arrested Development marathon (OK, I'm not working that hard), I found myself wandering over to Justine Bateman's blog.  Like many teens at that time period, I surely had a crush on her during her run on Family Ties.  So I had noticed that last year she had decided to go back to school to study computer science (UCLA -- college to the stars-interested-in-math-and-science, apparently;  I'm talking about you Mayim Blalik and Danica McKellar!).  But I hadn't been reading the blog.  And it's very entertaining, if only because it sounds like a freshman college blog, albeit occasionally with some pointers you might not normally find (like interviews for LA magazines).    This post, about finishing up a big project (making a computer Battleship game), is really familiar to me in tone;  I hear stuff like this from students all the time (and, of course, lived through it myself as an undergraduate). 

The point here -- besides that I now watch and have always watched too much TV -- is that computer science is awesome.*  Awesome enough that a big star of the 1980s has gotten inspired enough to go back to school and learn how to program Battleship, and more.

*And I guess another lesson is that Justine Bateman is awesome too.  Not that she'll ever see this, but Justine -- best of luck to you sophomore year and beyond!   

Grades In

The grades are in for CS 124.  Hooray!

Interesting trend : freshmen, who make up a small fraction of the class, are highly over-represented in the A and A- grades.  This has been happening for some years now. 
Extension of the interesting trend : women freshmen*, who make up a smaller fraction of the class, are even more highly over-represented in the A and A- grades.

I'd be very excited if I were teaching the class again next year -- finding undergraduates who have the potential to be TAs for multiple years is golden -- but I'll be sure to pass the names on to the new guy.**

Other side of the trend :  2nd semester seniors performed substantially below average this year.
But on the positive side :  nobody did so badly they won't graduate.  (At least, not in my class.)  

Getting grades in really makes the class feel over.  Onto summer work!  (Research and writing...)

* Freshwomen if you prefer.
** And any freshman or sophomore in the class who got an A and is interested in TAing should let me know next November or so.

Congratulations to Justin and Jon

Justin Thaler and Jon Ullman had back-to-back thesis defenses today.  Both talks were excellent -- Justin's on his work on verification methods (for cloud computing), and Jon on his work on differential privacy.  While there is still some small paperwork matters (like the actual theses to turn in), I think we should start calling them Doctor Thaler and and Doctor Ullman, just so they start getting used to it.

Congratulations Justin and Jon!

Calling Out Stupidity

While I greatly enjoy working at Harvard, there are many painfully stupid things said and done by people here -- as I suppose is the case anywhere -- that either I don't feel merit commenting on or I don't feel it's appropriate to comment on.  (And, of course, I'm sure that sometime in the past I've done or said things that others find stupid, and I'm very happy they aren't blogged about.)

However, the recent comments by Niall Ferguson are out in the public, and so over-the-top stupid that even he quickly realized how stupid they were.  And I think it's important to point out, prominently, how stupid they are, because the idea that either childless people or gay people somehow have a discounted view of the importance of the future deeply offends me, and somehow the idea that someone prominent in my workplace would say (or believe, or say in stupidity without really believing) such a thing has made my week substantially sadder.  And so I feel the need to point it out, ideally not to sadden anyone reading this, but to emphasize how sad and stupid the comments were.   

A Boy and His Atom

Some researchers at IBM are so good at playing with atoms, they decided to make a movie (called A Boy and His Atom), by moving atoms.  Cool stuff.  Computer science connections:  implications for storage.  Personal connection:  the spouse of the scientist leading the group who made the video is a friend from high school. 

Some Recent Books

If you've been reading the other computer science blogs, you know that there are some new books out.

First is the The Golden Ticket: P, NP, and the Search for the Impossible, by Lance Fortnow, about the P vs. NP problem.  I got sent a review copy;  I haven't read it yet, but I'm testing it out by having my oldest daughter read it and tell me what she thinks, and I'll read it along with her.

Then there's Quantum Computing since Democritus, which covers complexity theory, quantum computing, cryptography, and a bunch of other stuff.

But there's more!  Thomas Cormen, of the famous CLRS Introduction to Algorithms book, has a new book out called Algorithms Unlocked, which seems to be a friendly introduction to the basics of algorithms.


On the popular books front, Eric Schmidt (yes that one) and Jared Cohen have a book out on The New Digital Age: Reshaping the Future of People, Nations and Business.

Also, the book Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers, from some time ago, is out in paperback.



On the textbook side, last year Steven Gortler of Harvard introduced a new textbook for computer graphics that looks really good.  And of course, there's always that Mitzenmacher/Upfal Probability and Computing: Randomized Algorithms and Probabilistic Analysis to buy if it's not already on your shelf...

Thanks for the Memories....

I'm off to a meeting next week, so today was my last day of class for Computer Science 124 (Algorithms and Data Structures) for the semester.  For two reasons, today feels important. 

First, because I'll be on sabbatical next year, I won't have to teach another lecture for what seems to be something like 18 months.  I haven't had that much time off from teaching since I've started.  I'm looking forward to it, especially as this year the administrative job has slowed research.  I'm hopeful the sabbatical time can be put to use productively on the research side.

Second, more nostalgically, I've taught this class for the last 15 years.  To me that feels like a record of some sort.  When I come back from sabbatical, the plan is that someone else will be teaching the course, and I'll have to find something new and entertaining (for me, and maybe for the students) to teach.  I admit, my preference would be to teach this class pretty much forever.  After 15 years, I finally think I'm starting to understand all the material and how it fits together.  I'll miss the class.  While my head knows that it is probably good for both me and the class to separate, my heart hurts a little, giving it up and moving on.     

Given the excitement of once again being done with teaching for the academic year, I'm sure I'll get by.  (As I explain to the students, the only ones happier than they are that classes are ending are the faculty...)  Things change -- obviously, for me, sometimes very slowly -- and I'm optimistic that whatever I decide to teach next, I can make it a course I'll enjoy teaching for say the next 15 years.

Guest Post by Mark Bun and Justin Thaler

Michael asked me and Mark to write a post on our paper "Dual Lower Bounds for Approximate Degree and Markov Bernstein Inequalities", and we're happy to do so. As the title suggests, our paper focuses on understanding a certain measure of the complexity of a Boolean function, known as approximate degree. Given an n-variate Boolean function f, the approximate degree of f is the least degree of a real polynomial that pointwise approximates f to accuracy 1/3 (the choice of the constant 1/3 is by convention -- the particular constant is inconsequential).

Aside from being a natural complexity measure, approximate degree has a surprisingly wide range of applications throughout theoretical computer science. A very partial list includes:

1) Lower bounds on approximate degree yield lower bounds on quantum query complexity.

2) Lower bounds on approximate degree have recently been used to resolve long-standing open questions in communication complexity (see here for a survey from 2008, and some more recent works here and here).

3) Upper bounds on approximate degree underly the best known agnostic learning algorithms.

Despite the range and importance of these applications, large gaps remain in our understanding of approximate degree. The approximate degree of any *symmetric* Boolean function has been understood since Paturi's 1992 paper, but once we move beyond symmetric functions, few general results are known. One function that has served as a symbol of our lack of understanding is the two-level AND-OR tree, the function computed by a CNF (i.e. an AND of ORs) with all gates having fan-in sqrt(n). Over the last couple of decades, there has been a line of work proving incrementally larger lower bounds on the approximate degree of the AND-OR tree, with the best previous lower bound being Omega(n^{3/8}) due to Sherstov. Our main result in the paper resolves the question completely by establishing an Omega(sqrt(n)) lower bound, matching an O(sqrt(n)) upper bound due to H\oyer, Mosca, and de Wolf. (Sherstov recently independently obtained the same Omega(sqrt(n)) lower bound using related techniques). Our second result is to give a new proof of Paturi's lower bound for symmetric Boolean functions.

Let us say a bit about how our proofs of these two results work. Traditionally, approximate degree lower bounds have been proven by a technique known as symmetrization, which transforms questions about multivariate polynomials into well-understood univariate ones. In Step 1, one supposes there is a n-variate polynomial p that pointwise approximates f to error 1/3, and turns it into a univariate polynomial q in such a way that deg(p) >= deg(q). In Step 2, one shows that q must have high degree, which means p must have high degree as well. Unfortunately, the symmetrization step of moving from p to q often 'throws away' information about p (after all, p is an {n choose d}-dimensional object, and q is only a d-dimensional object), so one sometimes runs into problems in completing Step 2.

Recently, there has been progress in moving beyond 'lossy' lower bound techniques like symmetrization. Our paper uses the following approach, which is completely lossless. You can straightforwardly formulate the approximate degree of a function f as a linear program: the approximate degree of f is at least d if the value of the following LP is larger than 1/3:

min \epsilon

s.t. |f(x) - \sum_{|S| <= d} c_S chi_S(x)| <= epsilon, for all x in {-1, 1}^n

c_S in \mathbb{R}

Here, chi_S(x) is the parity function over variables in the set S. This program is just asking you to construct a degree d polynomial that minimizes the distance to f under the L_{\infty} norm.

If you take the dual of this program, what you'll find is that the dual is asking you to construct a function p that has *zero* correlation with every degree d polynomial, but has large correlation with f. We call such a polynomial a "dual polynomial" for f, as one can think of p as a polynomial with no monomials of degree d or less. A dual polynomial for f is a 'witness' to the fact that f has large approximate degree. By strong LP duality, any approximate degree lower bound entails the existence of a good dual polynomial; it might just take a lot of work to find it! Both of our results -- our Omega(sqrt(n)) lower bound on the approximate degree of AND-OR, and our new proof of Paturi's result -- work by constructing explicit dual polynomials.

In the case of the AND-OR tree, we take a dual polynomial for AND, and a dual polynomial for OR, and we combine them in a certain way to get a dual polynomial for AND-OR. Our proof is a refinement of a technique of Sherstov -- Sherstov had already showed in a very general context the 'right' way to put together dual polynomials for simpler functions F, G to get a dual polynomial p for their 'block-composition' F(G, G, ..., G), but his earlier analysis could not handle the case that F=AND and G=OR. Prior work broke down because it was not known how to argue that p had high correlation with AND(OR, OR ..., OR). We manage to show this by exploiting some special properties of the AND function and the OR function (specifically, the key properties are that AND has low block sensitivity at all inputs except the All-True input, and dual polynomials for OR have 'one-sided error'. It's difficult to give much more detail than that in a blog post, so see the paper for the full discussion.)

We construct our dual polynomial for symmetric functions as follows. \v{S}palek , building on work of Szegedy, had already constructed a dual polynomial for the OR function i.e. a symmetric function with a 'jump' from +1 to -1 at the bottom Hamming layer of the hypercube. We give a relatively simple construction of a dual polynomial for the Majority function i.e. a symmetric function with a 'jump' from +1 to -1 near the middle Hamming layer of the hypercube. We then show how one can interpolate between these two 'extreme' constructions to give a dual polynomial for an arbitrary symmetric function f. Our final dual polynomial closely 'tracks' (in a sense that can be made precise by complementary slackness) an optimal approximating polynomial for symmetric f's, and we are planning on adding a section to the arxiv paper explaining this intuition.

Finally, we use LP duality to reprove some classical Markov-Bernstein type inequalities from approximation theory (not to be confused with Markov's Inequality or Bernstein's Inequality from elementary probability theory). Markov-Bernstein inequalities bound the derivative of a univariate polynomial q on real inputs in the interval [-1, 1] in terms of deg(q) and the maximum value q takes on this interval. Typically, these are the inequalities used to complete Step 2 in the outline of symmetrization arguments given above. We show how to formulate the problem of maximizing the derivative of a bounded polynomial as an LP, and give clean solutions to the dual LP that 'witness' various asymptotic versions of the Markov-Bernstein inequality. The connection between Markov-Bernstein inequalities and LPs has certainly been known before, but to our knowledge no one has proved these inequalities by analytically constructing dual solutions to these LPs, and we think our dual witnesses shed some new light on these well-known results.

Looking ahead, we're very optimistic than more open problems in the analysis of Boolean functions can be cracked using methods based on LP duality. Approximate degree is not the only measure of the complexity of a Boolean function f that can be characterized by a linear program: there's also polynomial threshold function (PTF) degree (i.e. the minimum degree of a polynomial that sign-represents f), PTF weight-degree tradeoffs (i.e. tradeoffs between the degree of a PTF for f vs. the size of its coefficients), and weight-degree tradeoffs for polynomials that approximate f pointwise to accuracy 1/3. All of these complexity measures have important applications in learning theory, communication complexity, and beyond, but remain poorly understood even in the context of simple function classes like AC^0.

This work was not done in a vacuum, and we are extremely grateful to Karthekeyan Chandrasekaran, Troy Lee, Sasha Sherstov, Robert \v{S}palek, Jon Ullman, Andrew Wan, and the anonymous ICALP reviewers for valuable comments and conversations! As well as to Ryan O'Donnell and Li-Yang Tan for suggesting the problem of constructing explicit dual witnesses for the LPs capturing Markov-type inequalities!

Congratulations to Mark Bun and Justin Thaler

Luca Aceto reported the paper awards for ICALP 2013.  But I find it necessary to give a special shout-out to Harvard Ph.D. students Mark Bun and Justin Thaler, who got the Track A Best Paper Award for their work:
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. 

I've asked Justin and he has agreed that he and Mark will write up a post about their paper that will appear in a few days.  But since it was announced I wanted to congratulate them now!  

This brings up an interesting question:  they won the Best Paper award, but not the Best Student Paper award.  Which makes some sense in one way -- if the "Best Paper award" dominates the "Best Student Paper award" (by definition), then there's not need to give the same paper two awards;  it has the nominally higher honor.  On the other hand, you might say that if they won the Best Paper award, by definition they should also have the Best Student Paper, so they should win both.  How do you think awards in that case should be distributed?