Thursday, December 22, 2011

MIC and MINE, a short description

I thought I should give a brief description of MIC and MINE, the topic of our Science paper.  Although you're probably better off, if you're interested, looking at our website, http://www.exploredata.net/.  Not only does it have a brief description of the algorithm, but now we have a link that gives access to the paper (if you couldn't access it previously) available on this page, thanks to the people at Science.

Our starting point was figuring out what to do with large, multidimensional data sets.  If you're given a bunch of data, how do you start to figure out what might be interesting?  A natural approach is to calculate some measure on each pair of variables which serves as a proxy for how interesting they are -- where interesting, to us, means that the variables appear dependent in some way.  Once you have this, you can pull out the top-scoring pairs and take a closer look. 

What properties would we like our measure to have?

First, we would like it to be general, in the sense that it should pick up as diverse a collection of possible associations between variables as possible.  The well-known Pearson correlation coefficient, for example, does not have this property -- as you can see from this Wikipedia picture 




it's great at picking up linear relationships, but other relationships (periodic sine waves, parabolas, exponential functions, circular associations) it's not so good at.

Second, we would like it to be what we call equitable.  By this we mean that scores should degrade with noise at (roughly) the same rate.  If you start with a line and start with a sine wave, and add an equivalent amount of noise to both of them in the same way, the resulting scores should be about the same;  otherwise the method would give preference to some types of relationships over others. 

I should point out that the goal behind these properties is to allow exploration -- the point is you don't know what sort of patterns in the data you should be looking for.  If you do know, you're probably better off using a specific tests.  If you're looking for linear relationships, Pearson is great -- and there are a large variety of powerful tests that have been developed for specific types of relationships over the years.

Our suggested measure, MIC (maximal information coefficient), is based on mutual information, but is different from it.  Our intuition is that if a relationship exists between two variables, then a grid can be drawn on the scatterplot that partitions the data in a way that corresponds to  that relationship.  Suppose we have a grid, with x rows and y columns;  then this grid induces a probability distribution, where the probability associated with a box on the grid is proportional to the number of data points it contains.  Let I_G be the mutual information of the grid.  We aim to maximize I_G/ log min(x,y) -- this is the MIC score.  (We bound x, y values to avoid trivial cases like every point having its own box;  see the paper for more details.)  MIC values are between 0 and 1, and we can approximately compute MIC values heuristically.  Our work shows via a mix of proofs and experiments that MIC appears to have the properties of generality and equitability we desire.   

Based on the approach we use to find MIC, we suggest several other possible useful measures, and we refer to the collection as MINE (maximal information-based nonparametric exploration) statistics.  For example, MIC - Pearson^2 turns out to be a useful measure for specifically finding nonlinear relationships.  When MIC is high (close to 1) and Pearson is low (close to 0), there is a relationship that MIC has found but it is not a linear one;  for linear patterns, both MIC and Pearson are high, and so this measure is close to 0.  Other measures we have measure things like deviations from monotonicity -- useful for finding periodic relationships.

Should MIC/MINE prove useful, I believe there's lots of theoretical questions left to consider.  The approach is currently essentially heuristic, although we do prove a fair number of things about it.  Proving more about its properties would be useful, as well as improving the complexity to compute the relevant measures. 


Next up:  more about the experience of working on this project.

Sunday, December 18, 2011

Congratulations to Hanspeter Pfister

Despite our really very good track record for the last decade or so, there are some people out there who remain under the misimpression that it's impossible to get tenure at Harvard.

So I'm very happy to announce that Hanspeter Pfister has achieved the impossible, and is now a tenured Harvard Professor. 

Hanspeter works in graphics and visualization, doing the usual sort of things like replacing your face in videos and designing 3-d printers that work like a Star Trek replicator.  But he has also developed a large number of collaborations with domain scientists, finding interesting and important visualization problems in things like diagnosing heart disease and mapping the brain.

We're all happy he'll be staying around.  Hooray for Hanspeter!

Friday, December 16, 2011

This Week, I Am A Scientist

This week, I am a scientist;  I know this, because I have an article in Science. 

It's nice to have something to point to that my parents can understand.  I don't mean they'll understand the paper, but they'll understand that getting a paper in Science is important, more so than my papers that appear other places.  And because they're probably reading this, I will also point them to the Globe article appearing today about the work, even though the article rightly focuses on the cool and unusual fact that the lead authors are two brothers, David and Yakir Reshef.

I had been planning to write one or more posts about the paper -- both the technical stuff and the great fun I've been having working with David, Yakir, my long-time colleague Hilary Finucane, the truly amazing systems biology professor Pardis Sabeti, and others on this project.  (See Pardis's Wikipedia page or this site to see how Pardis rocks!)  But between Science's "news embargo" policies and my own end-of-semester busy-ness, I blew it.  I'll try to have them out next week.  But for now, for those of you who might be interested, here's the link to the project web page, and here's the abstract:

Detecting Novel Associations in Large Data Sets

Abstract: Identifying interesting relationships between pairs of variables in large data sets is increasingly important. Here, we present a measure of dependence for two-variable relationships: the maximal information coefficient (MIC). MIC captures a wide range of associations both functional and not, and for functional relationships provides a score that roughly equals the coefficient of determination (R2) of the data relative to the regression function. MIC belongs to a larger class of maximal information-based nonparametric exploration (MINE) statistics for identifying and classifying relationships. We apply MIC and MINE to data sets in global health, gene expression, major-league baseball, and the human gut microbiota and identify known and novel relationships.

Thursday, December 15, 2011

Consulting

As I've probably mentioned, I generally enjoy my consulting work.  Besides the obvious remunerative aspects, consulting provides challenges, insights, and experiences that are quite different from academic work.

On the other hand, taking red-eyes and having to get up at 4 am for a 6 am flight to a meeting in another city -- both of which I had to do this week -- I could happily do without.
  

Wednesday, December 14, 2011

Grading

Some folks at the NSDI meeting were nice enough to say that it was nice that I was blogging again.  Sadly, I've been under-the-gun busy for the last several weeks, but it was a reminder that I should be getting back to this now and again.

One thing that's taken my time the last week is grading.  I was teaching my graduate course this semester, on randomized algorithms and probabilistic analysis, using my book as the base.  Unfortunately, I teach this course at most every other year, which means it's hard if not impossible to find a suitable TA.  (As for my own students, Zhenming is on an internship this semester;  Justin's on fellowship and essentially required not to TA.  Also, both have been extremely busy this semester doing really great work, so why would I want them to TA instead of doing their research now anyway?)  So this year I didn't have one.  Which means I graded things myself.

It's been a while since I've graded a whole course.  I do grade exams (with the TAs) and one full assignment (myself) every year in my undergraduate class.  But grading every week is really at least as bad as having to do homework every week.  I'd say worse;  very little interesting thinking involved, just a lot of reading, checking, and moving papers or files around in a time-consuming fashion.  Somehow, though, I don't think the students sympathize.  

I think I remember one graduate class in Berkeley where a student (or maybe a group of students) were required to take on the grading every assignment.  I like that plan.  In fact, right now I like any plan that doesn't involve me grading the next time I teach this class.  One plan is of course no/minimal homework, or homework without grades.  However, I do believe students learn by doing homework, and I've found that in most circumstances a grade is the motivator that makes them get the homework done, so I'll have to find a plan that involves grading somehow.         

Tuesday, December 06, 2011

Plane Work

I dislike flying, but I have a few flights coming up.

I find that engaging in "real thinking" about problems while on a plane is generally beyond me.  (I'm jealous of all of you that somehow manage this.)  Similarly (or Even) writing code takes more focus than I can manage on a plane.  But I do try to make my plane time useful.

Luckily, it's the end of the semester, so I think I'll be bringing the last homeworks and final exams to grade on board this time around.

Reviewing (conference) papers is something I manage on plane flights.  I'm sure that says something about the level of my reviews.  On the plane my goal isn't to read the paper in same depth that I'd read a paper I'm trying to understand for my research;  it's to assign a score (sort) and write down useful comments.  (Which, I guess, is my goal for conference reviews off the plane as well.  And why I wouldn't do journal reviews on planes.)  If you get a review you don't like, I suppose now you can always assume you can assign the blame to the fact that I was on a long plane flight.  But I don't think I'll have any reviews this month.

Reviewing proposals is even better than reviewing conference papers on a plane.  I often get foreign governments sending me proposals to review for them, and they often pay some nominal amount.  If I know I have a flight coming up, I sometimes say yes.  It makes me feel like I'm doing something useful on the flight, and even getting paid for it.     

When all that fails, I try to read a mindless book.  (It's always good to have one on hand for those interminable periods where your electronic devices must be turned off.)    I slipped up and started reading V is for Vengeance at home.  (I think I've read all the Kinsey Millhone books from A, but I started at around H, and can't recall if I found all the earlier ones.  I wonder what she'll do after Z?)  I've been saving Mockingjay for a plane flight though.  (I try to read what my kids read.  So I'm also quite familiar with Percy Jackson.)  I've read most of Robert Parker's books in the air.     

Finally, sometimes, I fall asleep.  I've gotten reasonably good at sleeping on flights.  Then I don't get the work I thought I'd get done on the plane done.  But it definitely feels like a good use for the time.

Saturday, December 03, 2011

The End (of the Semester) is Nigh

If you've missed it (which probably means you're not a theorist and/or a blog-reader), you should check out the (entertaining) controversies of the last week or two, starting with Oded's guest post on the decline of intellectual values in Theoretical Computer Science, and then whether a lowering of the matrix multiplication exponent counts as a "breakthrough" (see follow-up blog posts here, here, and here).

I've enjoyed watching them develop, but have been happy to let them go on without putting a big target on my back.  I've also been too busy getting through my last lectures, making up a final exam, trying to get some grant proposals ready on ridiculous deadlines, and dealing with administrative issues like prepping slides for an end-of-semester faculty retreat.  Occasionally I try to fit in meeting with students and (last of all) working on research.  I know the end of the semester is a mad rush for students, finishing projects and papers and getting ready for exams.  Sadly, I feel the same way this year.  Another week or two and it will be all over, and like the students I think I'm ready to let things go for a couple of weeks of holiday time. 

But probably I'll stay up late after the kids are in bed and try to do some of that research stuff.  There are some fun problems that have been waiting for attention most of the semester, and I'd like to see what happens if I'm finally able to give them some. 

Thursday, December 01, 2011

Letters of Recommendation Time. Ugh.

I don't mind writing letters of recommendation for students.  It's part of the job.  It's a good thing to do. 

I just mind dealing with the new e-application sites.  I'd rather hand my letter off to an admin and have them send it.  The good old days...

To see what I'm talking about, I'm now a huge non-fan of Embark -- here's their "help page", which explains that I may have to wait 5+ minutes for my pdf to upload, without really explaining why

Monday, November 21, 2011

Round Two Reviewing : An Exercise in Conditional Probabilities

We're in "round 2" of reviews for NSDI, and it's brought up a problem for me I've noticed before.  I worry that, subconsciously, I'm inclined to give papers I read on the second round a higher score, since I'm swayed by the fact that they've in fact made it to the second round. 

I wonder if anyone in the PC world has done any testing of this to see if it's a real phenomenon.  Are second round reviews on a set of papers statistically different from the first round of reviews?  I would bet yes, even controlling for the fact that the papers made it to the second round.  In particular, I'd suspect it's much harder for people to give a score of 1 (=reject) to a second round paper.

One could imagine attempting to test for this by sticking a few obvious rejects from the first round into the second round reviews.  Indeed, perhaps one should make this part of the process:  randomly select a few clear rejects to go into round two, and announce that you're doing this to the PC.  Then they might not feel so averse to assigning a score of 1 in the second round.

One joy in the second round reviews is once you submit a review you get to see the first round reviews.  So far, I feel I've been calling them fairly;  when I haven't liked a second round paper, the first round reviews seem to confirm my opinion.  So perhaps (with some effort) I'm keeping my subconscious at bay successfully, and not conditioning on the fact that it's a round 2 review. 

Wednesday, November 16, 2011

Public University Budgets

Another topic that arose in conversations during my visit to Wisconsin was the issue of budgets, and in particular the large-scale cuts that many of the best US public school are having to deal with.  It's not hard to find information on this.  My first search on Google yielded this article about what's going on in Wisconsin (taking choice quotes, not the full article;  it's from June).

Wis. Gov. signs budget cutting education $1.85B

Democrats assailed the budget as an attack on middle class values since it cuts funding for public schools by $800 million, reduces funding to the UW system by $250 million and cuts tax credits for poor people.

It also reduces the amount schools can collect from property taxes and other revenue combined, which translates into another education cut of about $800 million. While schools are seeing deep cuts, Walker's budget extends tax breaks to manufacturers, multistate corporations and investors.

"As a state, we can choose to take the easy road and push off the tough decisions and pass the buck to future generations, or we can step up to the plate and make the tough decisions today," Walker said in prepared remarks. "Our budget chooses to fix our problems now, so that our children and our grandchildren don't face the same challenges we face today."
I'm sure the children and grandchildren he talks about, who will have to face the new challenge of increased global competition with an increasingly better educated non-Wisconsin population instead of the challenges being faced today, will be very appreciative.

Public universities generally have been faring quite badly in the current financial crisis.  I have a deep pro-education bias, unsurprisingly, so I find this depressing.  But also, in my mind, it's just not sound financial sense.  I believe these cuts today will yield a corresponding decline in Wisconsin's economy tomorrow, for some appropriate notion of tomorrow.  A dollar spent on education should be worth... well, I don't know how much it should be worth, but my guess is the multiplier on the dollar is pretty high.  I'd like more information to back that up.  If you know of any studies that demonstrate the payoff for education -- the sort of thing all of us in the education field should have on hand when discussions like this come up -- please leave them in the comments.  It would be nice to have a collection handy.  

Tuesday, November 15, 2011

Yes, We Are Hiring (2012)

Harvard CS will be hiring this year.

One tenure-track position is geared toward systems, very broadly defined.

A second tenure-track position is in Applied Math, where we're aiming for a "discrete applied math" person.  The right CS theory person could fit just fine.  And if we see great CS theory people who really want to be in CS rather than AM, we should be able to find a way to make that work.  

Here's the link to the ad for both.  Here's the URL:  https://www.seas.harvard.edu/csjobs.  And the ad text follows.  Spread the word!


Tenure-Track Positions in Computer Science and Applied Mathematics

The Harvard School of Engineering and Applied Sciences (SEAS) seeks applicants for positions at the level of tenure-track assistant professor in the fields of Computer Science and Applied Math/Computer Science, with an expected start date of July 1, 2012.

Candidates are required to have a PhD or an equivalent terminal degree, or to be able to certify that they will receive the degree within one year of the expected start date.  In addition, we seek candidates who have an outstanding research record and a strong commitment to undergraduate teaching and graduate training.

Position 1:   Computer Science.  We welcome outstanding applicants in all areas of computer science. We are particularly interested in systems, broadly defined, including compilers, programming languages, distributed systems, databases, networking, and operating systems.  Applicants will apply online at http://academicpositions.harvard.edu/postings/3825.

Position 2:  Applied Math/Computer Science. We welcome outstanding applicants in all areas of applied mathematics or theoretical computer science. We are particularly interested in topics at the boundary or intersection of these fields, including optimization, applied probability, scientific computing, combinatorics and graph theory, approximation algorithms, and numerical analysis. Applicants will apply on-line at http://academicpositions.harvard.edu/postings/3824.

In terms of applications, areas of interest include computational science, engineering, or the social sciences. We encourage applications from candidates whose research examines computational issues raised by very large data sets or massively parallel processing.

The Computer Science and Applied Mathematics programs at Harvard University benefit from outstanding undergraduate and graduate students, an excellent location, significant industrial collaboration, and substantial support from the Harvard School of Engineering and Applied Sciences.  Information about Harvard's current faculty, research, and educational programs is available at http://www.seas.harvard.edu.

Required documents include a CV, a statement of research and teaching interests, up to three representative papers, and names and contact information for at least three references.

Applications will be reviewed as they are received. The review of applications will begin on December 15, 2011, and applicants are strongly encouraged to submit applications by that date; however, applications will continue to be accepted at least until January 15, 2012.

Harvard is an Equal Opportunity/ Affirmative Action Employer.  Applications from women and minority candidates are strongly encouraged.

Monday, November 14, 2011

Public Salary Information

While visiting Wisconsin last week (enjoying very pleasant company and conversation), various issues came up.

For one, I was reminded (or recalled) that as a public university, University of Wisconsin-Madison salaries are available online.  I can understand why salaries of elected public officials, and the people they hire, should be public information.  Transparency in politics is a valuable thing.

But I don't see that professor's salaries should be public.  Perhaps this is merely a personal bias;  I wouldn't want MY salary to be public information.**  I also don't use Facebook, so perhaps I'm just a 20th century privacy-desiring relic.  Perhaps more reasonably, I don't see university faculty as political employees, and therefore think they -- as well as the university -- should enjoy the same privacy for salary information that other employers and employees enjoy.

Perhaps, however, I'm just wrong, and transparency of salary information is good for all.  I'm willing to entertain that thought.  Certainly I think the Taulbee survey that aggregates salary information is useful and good information, for both universities and faculty, as I think there's a shortage of accurate comparative salary information for faculty positions (as compared to other jobs), and the Taulbee survey provides an important information baseline.  Is it so far to go from there to individual's salaries? 

How do those of you at schools where your salary information is public information feel about this?  And the rest of you?

** Although perhaps in some sense it is.  I don't believe my NSF grant budgets are publicly accessible information, but at some point, I was informed by my university that a Freedom of Information Act request had been made for one of my funded proposals.  (I don't know why, though I have some suppositions.)  The university filed paperwork to hopefully make sure that personal information, including my salary, would be redacted. 

Thursday, November 10, 2011

CAEC: First Cambridge Area Economics and Computation Day

Giorgos suggested I remind people about CAEC, which will be next week (November 18).
Still time to sign up and register.

Here's the link.

Wednesday, November 09, 2011

Programming for Non-Programming Exercises

One of the exercises I assigned last week proved interesting: 

Consider n points on a circle, labeled clockwise from 0 to n-1.  Initially a wolf begins at 0 and there is a sheep at each of the remaining n-1 points.  The wolf takes a random walk on the circle;  at each step, it moves with probability 1/2 to one neighbor and with probability 1/2 to the other neighbor.  (0 and n-1 are neighbors.)  The first time the wolf visits any point it eats the sheep that is there.  (The wolf can return to points with no sheep.)  Which sheep is most likely to be the last eaten?

If you haven't seen it before, you might try it;  don't put the answer in the comments, though, since I'll use the problem again.

While grading the assignment, I found a number of students had simulated the process, figured out the answer from the simulations, and then used that knowledge to prove the desired result.  The problem didn't ask for them to do it, but they did it themselves.

That was great (and I told them so).  That's how solving research problems often works for me.  I have to understand what's going on, and in many cases, that understanding comes about by simulating a process to figure out how things behave.  Then I go back and try to prove what I think I'm seeing in the simulations.

My worry, though, is that the students that did it this way were primarily the "non-theorists" in the class, who did it because they knew they didn't know the answer, and thought it was easier to code to figure it out.  And that the "theorists" in the class correspondingly thought they knew the answer (rightly or wrongly) and went ahead with the calculations without doing a simulation.  That's not necessarily a bad thing, certainly not for this problem (which is easy enough), but I'd also like for the theorists to also get into a mindset of doing simulations in this sort of setting, both as a tool to gain insight before trying to prove things and as a check on their proofs.

I think they're probably getting the lesson from other, harder exercises I give.  Still, it was nice that a number of people in the class went that direction (and thought to write it down in their assignment).  

Monday, November 07, 2011

A Tale of Talks

A bunch of talks today.

Carla Gomes gave a talk at CRCS (Harvard's Center for Research on Computation and Society) to talk about her work on computational sustainability -- interdisciplinary research with "the overall goal of developing computational models, methods, and tools to help manage the balance between environmental, economic, and societal needs for sustainable development."  How to use optimization, machine learning, and math and computation more generally to help with problems in "the real world", like designing paths for animal migration or designing control systems for energy-efficient buildings.  Fun stuff.

Then I had to take Harvard's M2 shuttle over to the Medical School Area for the Broad Institute's annual retreat.  Some students who I have been working with on a project spanning systems biology, computer science, and statistics were giving a 15-minute presentation of their results.  (More on the work at some later date.)  The scale there is a bit larger than I'm used to;  I think over 1000 people were listening to the talk, which might well make it the most seen presentation of my work (even if we sum over multiple presentations of the same talk).  Happily, the students really nailed it, both in the presentations and the follow-up Q and A.

Then the shuttle back for Mark Zuckerberg's Q and A session at Harvard.  I don't think I've seen him speak before, and he's actually much more well spoken than one might expect if you saw The Social Network.  He was entertaining and captivating, and I'm sure inspired many of our students.  It was a full room -- you needed to get a ticket to get in.  I understand recruiting sessions with students are taking place sometime after.  If there are good writeups I'll link to one here later.

I also have my own talks to work on.  I'll be giving two talks at U. of Wisconsin this week.  One "old" talk on cuckoo hashing, and one "new" talk on verification using streaming interactive proofs.  Come on by if you're in the area.  (Of course, I suspect if you're in the area, you're probably a student or faculty member of U. of Wisconsin.)

Friday, November 04, 2011

Funny E-mail of the Day

I've having some issues getting straight answers over e-mail from an administrator in some Harvard office I'm dealing with.  This morning, I found the following e-mail in my inbox: 

Dear Mmichael,
To be clear,

Sent from my iPad

Well, now, this is entirely the problem, isn't it?  

Wednesday, November 02, 2011

This Week, We Were Doing Security

If you look on Yelp's engineering blog (http://engineeringblog.yelp.com/2011/10/output-filtering-failure.html), you'll see Yelp's VP of Engineering, Michael Stoppelman, crediting our team (myself, John Byers, and Giorgos Zervas) for finding a privacy ``leak'' in their system that occurred on the mobile version of the Yelp site, m.yelp.com. Their post describes the issue from their point of view. We'd like to elaborate a bit further by presenting how things appeared from our end.

Before beginning, though, we should say that Yelp's team responded in what seems to us to be an exemplary fashion. After we contacted them, Michael Stoppelman and members of the engineering staff listened to our presentation and description of the vulnerability seriously, and, as they describe in their blog post, took immediate action to correct the problem. While it would be fun to have a security horror story to tell (right around Halloween) of a big company not taking the leakage of user information, or us as researchers, seriously, that absolutely was not the case here. Indeed, when we expressed that we should make the issue public after the problem was fixed, both to transparently inform their users and to possibly help prevent a similar problem on other web sites, they agreed to write a blog post about it, and let us read the copy in advance to make changes or offer suggestions -- and except for making sure Harvard, Yale, and Boston University were all credited, we didn't have any to add.

As people may know from our previous work, we have been studying sites such as Yelp, as they provide an interesting case study as a social network that provides economic information in the form of reviews. As part of our research and data collection, Giorgos was looking at their various interfaces, including the Yelp mobile web site. To be clear, he was not ``hacking'' the site in any way, just interacting with it via a standard browser and normal HTTP requests. He found that when he checked a restaurant for reviews, and subsequently clicked on the button asking for more reviews, entire reviewer records were leaked in JSON format, in the manner described in Yelp's blog post. While this data was present in HTTP replies, and was visible to an HTTP logger such as Firebug for Firefox, or via the built-in logger for Chrome, ordinary users accessing the site from a device such as an iPhone would not observe sensitive information, as client-side Javascript displayed only the non-sensitive information (such as the review text, date, and the user's handle).  This example shows the importance of having multiple redundant layers of security when handling personally identifiable information;  in the Yelp post, they describe the redundancies they have added to prevent such leakage in the future.

While there was no financial information involved, it seemed to us to be a severe hole, in that personally identifiable information was being sent in the clear in response to a normal and seemingly not infrequent user request. We spent some time verifying what we saw, checking that we were not mistaken and that the vulnerability could potentially leak information at scale. When we were fully convinced the problem was both real and significant, we contacted Yelp.

We did have concerns as we went; we have heard stories of some businesses blaming the messenger when approached with significant security issues. We were pleased that Yelp responded by thanking us rather than blaming us. In our minds, this was a very positive interaction between university researchers and an Internet business.

Giving credit where credit is due, Giorgos deserves the lauds for finding the problem and thereby protecting a lot of user data.

Thursday, October 27, 2011

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.

Wednesday, October 26, 2011

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. 

Tuesday, October 25, 2011

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.