Yet Another Hat Puzzle (Maybe)

There are n players who are allowed to communicate, and then the game starts and they are not allowed to communicate thereafter. At the start, each player is given red hat with prob p and blue hat with prob 1-p. Each player is allowed to see all others' hats but not their own. Each player is then (separately from everyone else) allowed to guess the color of their hat or choose to pass. Success: at least one player should guess and all who guess should be correct. How high can one make the prob of success?

ps: With p=1/2, this is the well-known puzzle discussed by Sara Robinson. In that case, the prob is like 1-1/n. Peter Winkler and Elwyn Berlekamp among others discuss the problem in this article, and establish the connection to Hamming codes. So, may be there is a clean solution for the general p in terms of weighted codes? For small n, one should write down the hat combinations and work out the probability.

Ad Auctions Competition

Michael Wellman of U. Michigan and his group runs a trading agents competition annually. This year, with support of the EC community and feedback from sponsored search companies, they have designed an ad auctions competition for building trading agents to test dynamics of ad auctions. They have put a lot of thought into designing a controlled environment so the competition would provide meaningful comparisons, encourage interesting strategies, and hopefully, yield clear lessons. I would love to see participants actually set up agents to run experiments that feeds into their strategy design, because experimentation (trial-error-tweak) is (should be) an inherent part of taking part in ad auctions.

Algorithms for Designing Exams

The discussion about designing grading schemes (1/4th the points for "I Don't Know", choice of answering X out of Y questions, etc) got me thinking: is there published work on algorithms for designing online exams (such as in ETS) where each question is dynamically determined online depending on the performance thus far, under a suitable model and optimization criteria? Are there interesting game-theoretic issues in how students can manipulate the outcome by deliberately not answering a question correctly?

Japan in Pics

I was in Japan, the northern parts, where one can see Russia. Snowboarding near Sapporo, treading on icy beaches of the Sea of Okhotsk, and trekking through the Mizunara forest in Kawayu. In quick pics, here are three panels. In Japan, it is hard not to photograph food, packaging, nature or oneself; bookstores, vending machines and life are tantalizing.

Rabin in NY in Spring

Things long under work finally reach their finale: Michael Rabin will be visiting Google Research, NY in Spring 09.

On Patenting

We in academia should be busting patents rather than defending them. Basically, the patenting process is stretched (with parties patenting things from silly to broad, gross, and to all things published and unpublished), with the courts and lawyers ultimately resolving the issues. No matter the issue, there are "expert" academics who will defend each of the opposing sides with equal vigor, authority and self-belief. Since we care about creativity and patents are a form of creative achievement, it should be our agenda to bust patents, and bring it the same level of angst we do for our papers (find flaws, missing elements, prior work, and with some small training, check even the legalese of claims, etc). This is doable with patents in algorithms.

ps: Imagine a graduate course on patented algorithms with HW to bust them, imagine a "algorithm zoo" of patents, and imagine a SODA submission on optimization problems in patent busting. :)

On Grading Algorithms

I finished grading the finals (graduate algorithms) before I left on vacation. Grading algorithms finals has its

• challenges: grading is not just checking "equality". A student might propose a solution different from the one you have in mind but equally valid. So you have to understand their idea, think about if it will work, check proof of correctness and make sure there are no bugs, etc. All time consuming tasks.
  
• surprises: a silent student in the classroom may show a spark in the finals. A regular class room participant may fumble solutions to easy problems.
  
• and, in this case, self-inflicted quirks: borrowing from someone (who? I don't now recall), I award 1/4th of the points on a question if a student simply writes "I Do Not Know".This rewards the students for knowing they do not know the solution, as well as cutting down on fluff a grader has to read through. How do students react to this? Some are professional, fill in "I Do Not Know" just before the time runs out, some are principled and never use this route, and yet others forget to use this route and regret it later.
  

On Emails

There are two styles to doing emails. Style A is a deliberate process, measured words, read over and polished. I remember a 45-min effort to draft a few lines of an email once. Style B is the response I got for that email. Done in a short burst, like the modern telegraph, saving words (and vowels) when one could. In A, mails accumulate in your inbox and torment you until you find time to respond. In B, it seems like you are statistically multiplexing your life by splicing it into twits between emails. Sigh, I long for A and sometimes do B.

Coffee++

Continuing the theme of coffee++, we now have the Roasting Plant on Greenwich Ave, open 24 hours. It is a plant. There are tubes that convey raw beans to the roaster, from the roaster to the grinder and ultimately to your coffee, all via suction. Cool.

Online Ads Challenge

This may not be a research challenge, but it is a technical one. The Google Online Marketing Challenge 2009 has begun. Each entered team --- of a professor and students --- spends a budget of $'s on sponsored search ads for local businesses, and submits a report of their campaign. There is an academic panel that ultimately judges the winners. This could be a fun educational experience.

20th CPM

In Algorithms Research, specialized conferences (SPAA, SoCG, APPROX/RANDOM, COLT, PODC, and others) find a way to survive and thrive -- some more robustly than others -- because, even if they don't hold the attention of the entire CS community, there are hard problems, interesting structures, breakthrough techniques, and new applications in each of these areas. CPM (combinatorial pattern matching) is an example. Many algorithmii have sharpened their technical teeth on pattern matching problems; there are some truly hard problems (subquadratic regular expression matching), interesting structures (beautiful periodicity properties that you have to ultimately tap), breakthrough techniques (sparse convolutions, burrows-wheeler transforms, suffix sorting), and new applications (genomics to XML processing and web documents clustering). CPM, perhaps less centrally than many other specialized conferences, has survived and thrived: the 2009 edition (deadline is Jan 12) is its 20th!

Haikus While Sick

I am now sick and delirious, so thought I will type in two (sorta) haiku's.

Middle-aged woman on the subway
Reading CLRS
Page turned to B-Trees.
I saw the picture of a tree
upside down
Root at the bottom, leaves at the top.

Data Structures Inc.

I just finished teaching the graduate algorithms course (finals and grading still to go). I had an ambivalence towards data structures and did not really teach any interesting material: students know balanced search trees & heaps, I did teach hashing, but is that data structures? I did not teach skip lists, suffix trees, LCA, van Emde Boas, self-adjusting DS, persistence, fusion trees , ... Question is, are such data structures core to a graduate algorithms course? Any advice will be welcome for the future.

On a related note, someone asked me recently if I know of a good book on advanced data structures. I can point to a wonderful set of lecture notes from Erik Demaine's class. Together with Mihai's BAM future notes, we may get a good picture of the area of data structures.

Travel India

During the travel, I heard someone on the PA system in an airport go, "Will Mr. Patel and his family come to the desk please?". Shortly after, they called for Mr. Singh and his family. Sigh, do you know how many Patels and Singhs are in an airport at any time?

So many Indians around me at airports, restaurants, streets, and I am constantly surprised I don't see someone I already know. That won't happen to me when I travel in California.

The only reason I know Godthab, Goosebay or Gander, Canada, is the map the commerical aircrafts show onboard.

Movies: Y tu mamá también. Has more nudity than one can watch in the Economy class. The film is really about truth: the film hangs delicately to truth, faces it, exaggerates it, hides and reveals it. Pineapple Express. Have a car and severe doses of "pineapple express", and let life and some innocence play out. The film is really about friendships, won't happen anywhere other than in US.

The Land of Math

That would be India where I spent Thanksgiving. A South American asks for the price of an ice cream cone in broken English: how much? The local vendor answers: 87 Rupees. What? 87. Um, what?, this time with some hand sign. The vendor says, 100 minus one three. Universal language of Math triumphs, and someone gets to enjoy the ice cream.

India is also a land of awful ringtones. They don't let any old film song die. And it is the land of walls. Houses walled in, dirty streets and the world walled out. Owners zealously wall in their world of mansions and domestic help, every inch of their property, and just outside, the town streets are incongruously small, too small for their cars even. It is also the land where visitors and locals alike are driven to shake their heads and start with their prescription: "What India needs is ..."

ps: From what I hear, the people of Mumbai are back to their lives and its usual frenetic beat. So, kudos to them.