Lisa Randall on the Daily Show

Last night's Daily Show (link to full episode) was on fire.

The first segment was focused on SCIENCE!  The part with Aasaf Mandvi was simultaneously hysterical and very, very, very sad.

The last segment had guest Lisa Randall -- Harvard physicist and author of the new book Knocking on Heaven's Door: How Physics and Scientific Thinking Illuminate the Universe and the Modern Worldas well as the old book Warped Passages: Unraveling the Mysteries of the Universe's Hidden Dimensions -- talking about science also.  While I understand Lisa has many tremendous accomplishments, appearing on the Daily Show is the one I am jealous of.

Students are Awesome(ly Productive Right Now)

What's the use of a blog if you can't brag about your students?  And my students have all been doing great stuff, so I'm excited to let others know about their work. In random order...

Zhenming Liu's paper Information Dissemination via Random Walks in d-Dimensional Space will be appearing in SODA 2012.  It looks at a very natural random walk diffusion question that hadn't been solved.  Here's the arxiv version, and a slightly edited down abstract:

We study a natural information dissemination problem for multiple mobile agents in a bounded Euclidean space. Agents are placed uniformly at random in the $d$-dimensional space $\{-n, ..., n\}^d$ at time zero, and one of the agents holds a piece of information to be disseminated. All the agents then perform independent random walks over the space, and the information is transmitted from one agent to another if the two agents are sufficiently close. We wish to bound the total time before all agents receive the information (with high probability). Our work extends Pettarin et al.'s work, which solved the problem for $d \leq 2$. We present tight bounds up to polylogarithmic factors for the case $d \geq 3$.

Justin Thaler's paper on Practical Verified Computation with Streaming Interactive Proof was accepted to ITCS 2012.  I think part of its "innovation" is how well Justin puts together the theory with the implementation, showing how practical this line of work could be. Here's the arxiv version, and again a slightly edited down abstract:

When delegating computation to a service provider, as in cloud computing, we seek some reassurance that the output is correct and complete. Yet recomputing the output as a check is inefficient and expensive, and it may not even be feasible to store all the data locally. We are therefore interested in proof systems which allow a service provider to prove the correctness of its output to a streaming (sublinear space) user, who cannot store the full input or perform the full computation herself. Our approach is two-fold. First, we describe a carefully chosen instantiation of one of the most efficient general-purpose constructions for arbitrary computations (streaming or otherwise), due to Goldwasser, Kalai, and Rothblum. This requires several new insights to make the methodology more practical. Our experimental results demonstrate that a practical general-purpose protocol for verifiable computation may be significantly closer to reality than previously realized. Second, we describe techniques that achieve genuine scalability for protocols fine-tuned for specific important problems in streaming and database processing. 

Finally, Giorgos Zervas's work on Daily Deals:  Prediction, Social Diffusion, and Reputational Ramifications, which I've already discussed on the blog since it got so much press play, was also just accepted to WSDM.  Giorgos is no longer my student, but working with me and Joan Feigenbaum as a postdoc, so I'll count him in the mix. 

An Exceptional Exponential Embedding

This week in class I get to teach one of my favorite probability arguments, which makes use of a very unusual embedding.  Here's a short description (for the longer description, see the book or the original paper, where the idea is ascribed to Rubin).

The setting is balls and bins with feedback:  I have two bins, and I'm repeatedly randomly throwing balls into the bins one at at time.  When there are x balls in bin 1 and y balls in bin 2, the probability the ball I throw lands in bin 1 is x^p/(x^p+y^p), and the probability it lands in bin 2 is y^p/(x^p + y^p).  Initially both bins start with one ball.  The goal is to show that when p is greater than 1, at some point, one bin gets all the remaining balls thrown.  That is, when there's positive feedback, so the more balls you have the more likely it is that you'll get the next one in a super-linear fashion, eventually the system becomes winner-take-all.

We use the following "exponential embedding".  Consider the following process for bin 1.  At time 0, we associated an an exponentially distributed random variable X_1 with mean 1 = 1/1^p with the bin.  The "time" that bin 1 receives its next ball is X_1.  Now it has two balls.  We then associate an exponentially distributed random variable X_2 with mean 1/2^p with the bin.  And so on.  

Do the same thing with bin 2, using random variables Y_1, Y_2, ...

Now, at any point in time, due to the properties of the exponential distribution -- namely, it's memoryless, and the minimum of two exponentials with mean a_1 and a_2 will be the first with probability proportional to 1/a_1 and the second with probability 1/a_2 -- if the loads in the bins are x for bin 1 and y for bin 2, then the next ball will fall into bin 1 is x^p/(x^p+y^p), and the probability it lands in bin 2 is y^p/(x^p + y^p).  That is, this exponential process is equivalent to the initial balls and bins process.

Now let X = sum X_i and Y = sum Y_i.  The infinite sums converge with probability 1 and are unequal with probability 1.  So suppose X < Y.  Then at some finite "time" in our exponential embedding, bin 1 receives an infinite number of balls while bin 2 just has a finite number of balls, and similarly if Y < X.  So eventually, one bin will be the "winner" and take all the remaining balls. 

In my mind, that's a beautiful proof. 

ITCS Review

The list of accepted papers for ITCS (Innovations in Theoretical Computer Science) is up. 

Some thoughts:

1)  I have expressed reservations in the past about ITCS, based on the idea that it was creating another conference similar to FOCS and STOC, where instead we should be "fixing" FOCS and STOC, for example by expanding it.  I suppose my reservations this year are muted.  While the titles don't suggest to me that ITCS is necessarily a home for more "innovative" papers than FOCS/STOC, there seems to be no inclination to expand these conferences, so why not have yet another conference where 40 very good papers can go?  (Indeed, why not make it a bit larger?  I'm not sure how many submissions there were;  hopefully someone can confirm, but I'd guess the acceptance rate was roughly 20-25%?) 
2)  Another issue was ITCS was in China it's first two years, making it seem a bit "exclusive".  (Not to Chinese researchers, of course;  and not to authors, who were given funds for the trip.  But it is a far distance to go for others.)  This year, it will be at MIT, which hopefully will attract people from up and down the East Coast (weather permitting), and help it build up a longer term audience. 
3)  5 out of the 40 papers have Quantum in the title.  Should this be telling us something?
4)  Talk I'm most looking forward to:  Compressed Matrix Multiplication by Rasmus Pagh.  (I've already read and enjoyed the paper.)  But I'm also looking forward to seeing Algorithms on Evolving Graphs, if only based on the title. 

An Apple a Day

Reviewing papers for a conference is a slow, time-consuming process.  Suppose you had 20 reviews due and about 4 weeks to do them.  What's your approach?

I take the tortoise approach.  I first try to do a quick pass over all the papers to at least have some idea of the topics and themes I'll be dealing with in the papers.  This lets me find papers that, at least on a fast first reading, seem unusually good or unusually bad, and lets me see if any papers are sufficiently related that they should be compared to each other implicitly or explicitly when I do my reviews.  But then, I try to set aside time to do one review a day, more or less.  I'll enter the review, press the button, and put it up for others to see.  I won't go back and revise things until the first round is over unless another paper I'm reading or another review I see makes me rethink substantially.  At the end, I'll go back and check that my scores seem consistent, given that I've seen my full set of papers.  Slow forward progress, with an eventual finish line.

Doing a paper a day does mean I limit the time I put into each review.  While there's some variance, I almost never let myself go down a rabbit hole with a paper.  That's not always a good thing;  sometimes, finding a bug in a proof or a similar serious flaw in a paper takes several hours of careful thought, and unless I pick up that's there a problem right away, I often miss it while going on to the next review.  (This is just one good reason for why we have multiple reviewers!)     

Perhaps another reason this is not always a good strategy: I'm told it's noticed that my reviews are actually done on time, and apparently this leads to people asking me to be on PCs.  

John Byers on WBUR

Listening to my co-author, John Byers, streamed live on WBUR, discussing our work on Groupon.  Ben Edelman is another participant in the show.

Here's the link.   

Listen

A colleague outside theory (but inside computer science) recently brought up an interesting question with me that seemed like a possible research-level issue.  We had some back and forth, trying to figure out what we each meant (naturally, our "vocabularies" are a bit different in how we describe the problem), what the actual question was, and if there was a direction to go.  After a couple of rounds of this, he thanked me.  Paraphrasing:  "I appreciate your patience.  My experience is other theorists are often immediately dismissive to these sorts of questions."

I was taken aback.  First, I'm not sure patient is a word commonly used to describe me.  Second, this colleague is a first-rate genius (with the track record to prove it).  Who wouldn't listen to what they have to say?  Quite frankly, I was happy they were interested in talking to me!

But it's been gnawing at me.  If a high-powered colleague outside theory has this impression of theory and theorists, how do we appear to others?  Was this an isolated opinion, or a common feeling?

I know 20 years ago, back when I was in graduate school, the theory/systems divide was quite large, at least at Berkeley.  There seemed to be minimal communication among the faculty groups.  Indeed, in part that was one reason that, at the time, the LogP paper seemed like such a big deal;  Dick Karp had successfully crossed over and worked with the systems side to build a model for parallel computation!  It was, sadly, notable, if only because such collaborative work had seemed so rare.

I've generally felt that while this theory/systems divide was still much larger than I might personally like that there had been a lot of progress since my grad student days.  I feel I can point to a significant number of examples.  But perhaps I'm holding the unusual opinion.  Maybe there's still not enough listening going on, in at least one direction.
 

Reading Confidence Men

My current spare time reading* is Confidence Men, Ron Suskind's book on Wall Street and the Presidency.  Without "taking sides" with regard to Larry Summers, I have to admit enjoying reading this paragraph:

"It all boils down to the classic Larry Summers problem:  he can frame arguments with such force and conviction that people think he knows more than he does.  Instead of looking at a record pockmarked with bad decisions, people see his extemporaneous brilliance and let themselves be dazzled.  Summers's long career has come to look, more and more, like one long demonstration of the difference between wisdom and smarts."

In Summers's defense(?), there are lots of people who would fit this description...

* As a parent who tries to read what my kids are reading, my future spare time reading looks to be the similarly political but less timely Mockingjayand the new-to-me series Artemis Fowl.  Recommendations for 8-10 year-old readings welcome.

Submissions, A Comparison

I just got my set of NSDI papers to review, and have been looking them over.

One thing that immediately strikes me as I give them a first quick pass is how nice it is that the submissions are 14 double-column pages.  The authors have space to present a meaningful introduction and a reasonably full description of and comparison with related work.  They can include (detailed) pseudocode as well as description of their algorithms.  They have space for a full page (or more) of graphs for their experimental results, and even more space to actually explain them.  The papers actually make sense, in that they're written in sequential order without having to flip over to "appendices" to find results.  The phrase "this will appear in the full paper" appears rarely -- not at all in most papers.  The papers are, as a consequence, a pleasure to read.  (Well, I can't vouch for the actual content yet, but you get what I mean.)

As a reviewer, it's also nice that if I tell the authors they've left out something that I think is important, I'll generally have confidence they'll have space to put it in if the paper is accepted, and that it's a reasonable complaint to make, in that they ostensibly had space to cover my issue.  (There are some papers which fill the 14 pages and perhaps won't have something obvious that could be removed, but experience suggests they'll be rare.)    

So I wonder again why theory conferences have 10-page single-column submission formats ("appendices allowed"!), or, even worse, for conferences like ICALP and ESA, they have final page counts of 10-12 pages in the over-1/2-blank-page LNCS format.  (Really, it's just about enough space for an abstract, introduction, and pointer to your arxiv version.)  Interestingly, for my accepted SODA papers this year -- which went with 10 page submissions, "full versions" attached on the back, but had 20 pages for accepted papers -- both sets of co-authors didn't want to bother when the final submission deadline came around to filling the 20 pages, figuring people could just be pointed to the arxiv (or eventual final journal) version.  Why create yet another version of the paper according to arbitrary page limitations?  I certainly couldn't suggest a good reason.  

On the theory side, as I've maintained for years, we're doing something wrong with our submissions, with artificial page limits creating more mindless work for authors and making decisions more arbitrary than they need to be.

 

Goodbye to Steve Jobs

My Mac laptop froze today.  It was an unusual occurrence;  I turned the machine off, and for a minute it wouldn't turn back on again.  I was in a panic. 

Then it went back to normal. 

After the fact, I was wondering if my machine was having its own minute of silence.  Then I had the morbid idea -- what if Steve Jobs had the power to arrange for all Mac products and iProducts to stop working when he died?  It would be a disaster for so many of us -- not just the loss of individual data, but the loss of the platforms and devices he made reality, that so many of us use and love.

Steve Jobs may be gone, but his legacy lives on.

New York Times

Our work on daily deals is mentioned and linked to in Sunday's New York Times (front page).  (John Byers even got a quote in!)  It was also mentioned in this week's print edition of Time magazine.  (Behind a paywall, so here's a jpeg.) 

Sadly, the name Mitzenmacher doesn't appear on these items.  ("...researchers from Boston University and Harvard..." seems to be a common phrase), so I continue to toil happily in relative obscurity.

My brother points out that this is all just an example of why print media is disappearing.  He says most anyone who might have seriously cared about our work would have heard about it two weeks ago on the Internet.  The print media is just getting to it now?   They're two weeks behind.  

Allerton Part 2 : Venue Change?

Yesterday, I thought the best talks I saw were by Devavrat Shah and Dina Katabi.

Dev was talking about how to track where rumors start.  The model is you have a graph of nodes that have been infected (by a rumor, or disease, or whatever), and based on the the shape of that graph, you want to figure out where the process started.  To get a picture of what I mean, suppose you were looking at a grid graph, and the infected area looked roughly like a circle.  You'd expect the infection started somewhere near the middle of the circle.  They've placed this in a mathematical framework (a distribution for the time to cross an edge, starting with tree graphs, etc.) that allows for analyzing these sorts of processes.  This seems to be the arxiv version of the work. 

Dina talked about 802.11n+, which they describe as "a fully distributed random access protocol for MIMO networks. 802.11n+ allows nodes that differ in the number of antennas to contend not just for time, but also for the degrees of freedom provided by multiple antennas."  By making use of nulling and alignment, they can extend 802.11 so that instead of competing for time slots, multiple antenna systems can compete for degrees of freedom within a time slot, allowing those devices with multiple antennas to take full advantage (and in particular allowing them to overlap transmissions with devices with fewer antennas).  I would have heard about it earlier, I guess, if I had gone to SIGCOMM this year.  The project page is here.

There's a whole session this morning on "mean field analysis" and games.  Mean field analysis (in my loose interpretation) means pretend your system gets big and turn it into a differential equation -- apparently a useful way to tackle various large-scale distributed agent/learning systems.  It's what I used to study load-balancing systems way back for my thesis (and still find an occasional uses for today).  Interesting to see it used for another set of problems.  Ramesh Johari's student (I didn't catch which one) gave a talk on a really interesting model of dynamic auctions with learning where you could gain some real insight using a mean-field analysis.  (How much should agents in an auction "overbid" when they're learning their value for winning an auction?  It depends on how much they think they'll gain in the future based on what they learn about their true value.)  This seems to be a preliminary version of the work. 

Now for the "negative" -- something I'm going to suggest to the Allerton folks.  It's time, I think, to find a different location.  The Allerton conference center is very beautiful, but it's not suitable, in many respects, for this event any more.  I was told there were about 330 registered attendees from outside UIUC, plus an additional 120 or so from UIUC.  It's a bit hard to turn that into a true count;  many (most?) UIUC people probably drop by 1 day, most attendees probably 1.5-2 days of the three.  But Allerton really wasn't designed for a crowd that large.  If you're not in one of the "big rooms", and people want to come to your talk, many times they can't get in.  For example, the social network session was remarkably popular;  the room could seat 40 people, and there were about 20+ people crowded around and outside the doorway -- which was not only not ideal, but it was also disruptive, as the open door meant a lot of noise in the room.  Actually, the acoustics aren't particularly good in any of the rooms, even the big ones.  Attendance in the early am is very low, in part I think because people staying "in town" have a non-trivial drive to get to Allerton. 

When the event was smaller, like 200-250 people, everyone coped with these problems.  It's really not working now.

I can understand there's an attachment to the Allerton center -- and how could it be the "Allerton conference" (next year is it's 50th year!) if it wasn't at Allerton?  But this has been an issue for years, and only seems to get worse.  There must be a conference venue on or near UIUC campus that would work as well -- at the very least, my opinion is it's time to look....

And now, back to the airport...

Allerton 2011

I woke up at an absurdly early hour this morning to get on a plane and go to the Allerton conference.  I'm giving a talk this afternoon on Invertible Bloom Lookup Tables (arxiv link) (joint work with Michael Goodrich).  It's a "lookup table", not a Bloom filter, because you want to be able to store key-value pairs;  you query for a key, and get back a value.  It's invertible, because besides being able to do lookups, you can "invert" the data structure and get back all the key-value pairs it contains (with high probability, assuming you haven't overloaded the structure).  This paper is really on the theory, but if you want to see a cool use for IBLTs, there's a paper by Eppstein, Goodrich, Uyeda, and Varghese from this year's SIGCOMM (Efficient Set Reconciliation) with a compelling application.

Allerton is a different sort of conference, as I've discussed before (like here and here, among others).  A mix of invited and submitted papers, a wide diversity of topics, lots of parallel sessions.  It seems absurdly crowded this year -- I had to park in the ancillary parking because the lot was full, and the rooms where the talks are held all seem to be bursting.  (The conference, unfortunately, really has outgrown the space where the conference is held.)  I'm guessing well over 300 registered;  I'll have to check.  The conference gives me a chance to catch up with colleagues who are more on the EE/networking side;  I've seen other CS theorists here in years past, but I haven't noticed anyone yet. 

If you're here, maybe come by my talk this afternoon, or say hi if you see me hanging around.

Set Competition

As an applied probability exercise, I had my class compute empirically the probability of a game failing on the nth round for the game of Set.  (See my previous post about this;  here failure means there's no set on the nth round, and they were asked to implement the "choose a random set" strategy if there was more than one.)  They were also supposed to try to calculate the probability of using all 81 cards in sets through the course of the game -- what we might call a perfect game.

Some students explored a bit and noted that changing from the random strategy could significantly increase the probability of a perfect game.  So I think the next time I decide to use this assignment, I'll turn it into a competition.  Students will have to develop a strategy that maximizes the probability of achieving a perfect game.  Prizes will go to the best strategy (which hopefully could be easily determined after a few billion runs or so -- I suppose I'll have to introduce some sort of computational limits on the strategy to ensure that many runs can be done in a suitable time frame), and the best "succinct" strategy -- that is, the best strategy that can be described in English in at most a few reasonable sentences. 

It's also interesting to think about optimal strategies in the offline case, where the permutation determining how the cards will be dealt out is given in advance.  I keep thinking maybe there's a way to effectively calculate whether a perfect game can be found for a given permutation, and then thinking there can't be.  (Though, admittedly, I haven't thought a lot yet.)  So maybe it makes sense to run the competition for both the online and offline versions of the problem.  

Beyond Worst Case Analysis Workshop

I'm just off a plane coming home from the Beyond Worst Case Analysis Workshop at Stanford.  It went really well, and I really enjoyed it.

I think a variety of things made it work.  First, and I apologize to Tim Roughgarden for saying it, but the execution was superb -- someone should make him organize more things.  Great room, great food, great staff on hand (thanks to Lynda Harris for being incredibly helpful), and a great collection of speakers.  Also, an excellent location.  Stanford is relatively easy to get to with 2 major airports nearby (but avoid the cabs -- it's now over $100 to take a cab from SFO!), and the location guarantees an audience of Stanford, Microsoft, and Google folks.  (While not everyone was there all the time, I understand well over 100 people were registered.)

To the content.  It was a great program -- apparently the talks will be on the web later, so you may want to check them out if you weren't there.  My favorites would have to be Dan Spielman's talk on smoothed analysis (perhaps because Dan just always gives great talks), and Kevin Leyton-Brown's talk on statistical methods (using learning theory) to predict an algorithm's performance on new instances.  (Can you predict the running time of your satisfiability algorithm accurately before running it on a specific instance very quickly just by taking a careful look at the problem?  The answer seems to be -- yes you can!)

There was a panel that focused on questions like "Where could we point students to work on these sorts of problems.  What are the currently most glaring examples of algorithms whose properties are poorly explained by existing theoretical models, where there might be hope for progress?"  and "To what extent can "real-world data" be modeled? Is it important to model accurately the properties of "real-world data"?"  While the panel ended up being fairly uncontroversial -- I'm afraid no fights or even major disagreement broke out --  I found it very interesting to listen to the others on the panel give their opinions and insights on these questions.

I think people got into the spirit of the workshop.  Kevin, an AI person by trade, found it amazing that  theorists were getting together to talk about heuristics and experiments.  (Kevin's talk was followed by Dick Karp talking about his work on tuning and validating heuristic algorithms -- though of course not all talks were on that theme.)  It will be interesting to see if this workshop inspires any specific new research -- but even if not, it was well organized, well put together for content, and well worth the trip. 

My talk slides are here.  

Guest Post on NYCE (Giorgos Zervas)

GUEST POST by GIORGOS ZERVAS

I was at NYCE 2011 this past Friday. It was a thoroughly enjoyable and productive experience. I feel like I got a conference's worth for the cost of and time commitment of a long commute.

The day started with three hour-long plenary talks, followed by lunch and a poster session, followed by an hour of 10 minute talks, and concluded with two more plenary talks. (And all of that for about $20.)

It turns out a lot can be squeezed into 10 minutes. Halfway into the first speaker's talk, with 5 minutes left on the clock, I was almost convinced he was running out of time. Everyone worked great around the time constraint to succinctly deliver their talks.

The plenary talk roster was varied and exciting (at least by one other account). I particularly enjoyed Jonathan Levin's talk on eBay experiments (pdf of the paper) in part because I was least familiar with it, and in part because I think I can use his key method. Here's the gist: instead of relying on random observations look for experiments that have been conducted on your behalf by market participants. To use his eBay example, auctions have a bunch of parameters: the item, its starting price, its reserve price, and so on. Quite often it turns out you can find sets of auctions ("experiments") that are identical in all but one parameter. This allows you to directly quantify the effect of the varying parameter. To say I wish I'd thought of this is an understatement -- I am trying to convince myself that I actually didn't. (I didn't.)

Of interest -- likely to myself only -- was the passing mention of Swoopo in two plenary talks. Their sudden demise still puzzles me. While writing our Swoopo paper they were running about 200 auctions a day. A few months after EC'10 when I checked again they were running about one hundred. They were responding to reduced demand but why were "entertainment shoppers" driven away? The business model certainly did not die as others have successfully taken Swoopo's place. One possibility is that the barrier to entry in this type business is low. Around Swoopo's peak there were people making money off penny-auction scripts they'd sell for a few hundred bucks. Hundreds of clones sprung. Buy a script and some hosting, run auctions, and ship directly from Amazon. In an interesting parallel the daily deals business also seems to have a very low barrier to entry judging from the hundreds of Groupon clones. I am still kicking myself for stopping data collection after our Swoopo paper was done.

Back to NYCE itself, if there is one thing I'd maybe have wanted to see more of is student talks (especially of the 10 minute variety). I guess the poster session made up for this but as someone with a poster to present I didn't have to chance to walk around and see others'. Which reminds me, thanks to everyone who stopped by my poster, and to the organizers for putting everything together!

Travels and Teaching

I'll be at the Beyond Worst Case Analysis workshop next week, and Allerton the week after.  For each, I'll have to miss a class.  I also have some other travels that may involve missing classes this semester as well -- I'll be missing more class than usual this semester, but they're for good reasons.

I'll have Justin and Giorgos cover a lecture for me (thanks, guys!), but next week I'm doing an experiment:  I'm substituting videos for my class.  I've pointed them to 2005 MSRI workshop Models of Real-World Random Networks, and having them watch some talks.  One is my survey talk on power laws, so it's still "me" teaching, but then I have a few impressive "guest lecturers" from the workshop to cover the rest; all the talks focus on power laws in some way.  I've even put together an "in-class" exercise for them to do on the subject -- out of class, of course.     

I wonder if this is a good approach or not.  I'll have to ask the students.  It's not ideal, but either is cancelling class.  Has anyone else started using videos as a solution to the missed lecture problem?  Are there ways to make it a more useful experience?

By the way, looking back, that 2005 MSRI workshop had a bunch of interesting talks.  Worth checking out sometime if you're interested in the area.  I looked younger then. 


Reminder : Giorgos has a poster at the New York Computer Science and Economics Day today.  Go check it out!

This Week, I Am Part of an Internet Meme

My frequent co-authors John Byers, Giorgos Zervas, and I posted an extended version of a current submission to the arxiv (as people do), which showed up last Friday or thereabouts.  Daily Deals: Prediction, Social Diffusion, and Reputational Ramifications discusses some analysis we did on daily deal sites (Groupon, LivingSocial), including interactions between daily deal sites and social network sites (Facebook, Yelp).  

The work got a plug Monday on the MIT Technology Review. They naturally focused on our most "controversial" finding, and I quote them:

"A Groupon deal might boost sales but, it can also lower a merchant's reputation as measured by Yelp ratings, say computer scientists who have analyzed the link between daily deals and online reviews."

Apparently, many people are interested in statements of that form, especially business types, and that's where the fun started.  We got some e-mails from people who work for firms that use statistical analyses in planning marketing efforts who had seen the article (and wanted our not-yet-released data set).  We noticed the review article was getting tweeted.  We started tracking a tweet feed to find out where else it was showing up.  (As a very partial list, Business Insider, Chicago Tribune, The Independent, Search Engine Journal.)  Monday we were worried that people might try to actually call us up and talk with us, but fortunately, that hasn't happened.  Instead of feeling pressured, we've just been able to enjoy watching.  

It's amusing to see how these things spread through the Internet. A lot of sites are just cutting and pasting from the MIT Tech Review. I know this because, in what I personally find to be the most amusing of mistakes, they refer to Giorgos as "Georgia Zervas". Giorgos does seem to have multiple name spellings (he also uses Georgios), but Georgia is not quite right. (It is, however, my new nickname for him*.)  Georgia Zervas, according to Google, has popped up almost 200 times in the last 3 days.  

We weren't really expecting this.  I think part of the reason we didn't expect much reaction is pre-summer we put up a placeholder with some initial data:  A Month in the Life of Groupon.  This didn't seem to get much notice.  Indeed, we had submitted it to NetEcon, and were essentially told by reviewers the paper was too boring.  I must admit I disagreed, then and now, with the reviewers.  But, to be fair, that version of the paper didn't contain the data sets and analysis for LivingSocial, the Facebook Likes, and the Yelp reviews;  it just had Groupon data (though we made clear this was an "appetizer" and more was to come).  John actually completely disagrees with me.  I quote:  "For the record, I agree with the NetEcon reject decision.  They should be applauded for making us do more work."  My take was the bar for a workshop paper was too high if this wasn't sufficiently interesting.  Giorgos wonders if by John's logic we're hoping the paper gets rejected again.  

Also, we didn't get nearly the same sort of attention for our previous similar-in-spirit work analyzing penny auction sites like Swoopo (entitled Information Asymmetries in Pay-Per-Bid Auctions:  How Swoopo Makes Bank).  Daily deal sites are MUCH bigger, and I suppose the results for Swoopo are a bit harder to summarize for mass consumption.

Anyhow, Giorgos will be at the New York Computer Science and Economics Day this Friday with a poster on the subject.  Stop by and talk with him!  (Giorgos recently completed his PhD at BU, and is doing a Simons postdoctoral fellowship with Joan Feigenbaum, while also hanging out some with me at Harvard as an affiliate of our Center for Research on Computation and Society.)   
  
* Don't worry Giorgos.  I'm kidding.  Sort of.

SODA Accepts -- The Count

People in various have been noting the SODA accepts, but nobody has been talking about the numbers.  I count 138 papers accepted.  I can't find now how many submissions there were;  I recall it was over 600 abstracts, but I think it cut down to 520-540 or so.  So this seems like just over 25%.

Is that a good number?  Too many?  Too few? 

I admit, I have trouble believing that there weren't at least 40, 50, maybe 100 of those rejected submitted papers that were of sufficient quality that it would have been just fine to have them in.  I could be wrong -- I wasn't on the committee -- but I'd guess there was more good stuff out there.

For those papers that were rejected, where will they go?  ICALP and ESA deadlines are pretty far off;  there aren't a lot of good homes for algorithmic papers until then.  (STOC/FOCS may not be appropriate;  other conferences and workshops have, I think, weaker reputations that may make them less desirable, especially for up-and-coming students and younger faculty.)  It seems like there's a hole in our schedule.  Rather than fill it with yet another conference, wouldn't the community be better off accepting more?

Rabin's Birthday Celebration

While I was not blogging, we spent the few days before the semester started with an 80th birthday workshop for Michael Rabin.  Impressively, we were able to pull it off despite the best efforts of Hurricane Irene, thanks to the many speakers who made an extra effort to get there, well beyond the call of duty.  Because some speakers couldn't make it (flight cancellations), and we were worried about storm cleanup, we postponed the start until Monday afternoon, but other than that, it went fantastically well.  (A credit to the organization of Les Valiant!)   

Richard Lipton described it all in this blog post, so I don't have to.  (The only negative thing in his post is that he refers to me as Mitz -- clearly because it's the easiest way of distinguishing me from the guest of honor, he doesn't call me that regularly -- which feels strange to me as I haven't been called that regularly since middle school.) 

If any coding theory people are reading this, I thought I'd point out that the slides for my talk (as well as the slides for many of the other talks), which was on coding theory, are available here.  In particular my talk is about how Michael Rabin's JACM paper on the Information Dispersal Algorithm was remarkably prescient, setting up some basic ideas and foundations for both the later work in LDPC codes and network coding.  While the paper is far from unknown (Google scholar has it at well over 1000 citations), I'm not sure how widely appreciated the paper is in the coding theory circles;  it was a pleasure for me to go back and reread it with new eyes to prepare for this talk.