Ranking

We rank students, papers, schools, ourselves and others. We rank the rich, riches and books. But over the web, ranking is a large scale monster, and more recently, it is derived from many different users (dogs?), whether collaborative, adversarial, or simply gameful. There are many ways to try to get "quality" ranking: by fiat, by appealing to good citizens, by policing them or letting them police each other, whatever. One approach is to provide incentives and develop a market around the users' utilities (juicy bones?). Setting up the incentive structure and mechanism is a complex problem. A recent paper does a nice job of formulating the questions and providing some solutions:

• Algorithms and incentives for robust ranking. . R. Bhattacharjee and A. Goel. SODA 2007. Earlier position paper, Incentive based ranking mechanisms in NetEcon 2006.

Single Malt

I remember this conversation I had a long time ago, trying to formulate why humans gave up the cosy life of hunting, gathering and roving to settle down, face the vagrancies of the weather and pests, to grow a lot of plants, throw out everything except the seeds for consumption? The answer is clearly that they needed to brew.

Single malt whiskey has many fans, and the conversation is usually taken over by the scotch variety in its malt madness. But others have their stake too, chiefly Japanese. Enjoy. Here is a map.

Three movies and some funerals

Working on the 15th street and living on the 4th does not mean it is an easy walk home after work. On the way, there are distractions. For example, the Quad Cinema that makes me want to spend the entire day watching movies. I recently saw A Dios Momo, the story of a newspaper boy from Uruguay with a committed soccer buddy, a loving grandmother, and no school, discovers via lyrics of Murgas and the magic of Carnival, to read, write and deal with the loss of his soccer buddy. Fellini-esque. It didn't deserve panning by the Village Voice that latched on to the presence of Big Cola.

Home has its own distractions too. I relived the mirth of Welcome back Mr. McDonald on DVD. A screwball comedy about live radio drama performance that goes through uncontrollable changes of characters, names, professions, locale, and everything else but manages to adher to the basic tenets and truths (can't do machine gun fire in NY, that is Chicago!), and ultimately tells the story of the playwright. The detour that yanks the old man from the security in basement to do Foley sound effects is awesome (Corn in US but Pistachio on the microphone for the effect of the rain, a bursting dam from a toilet flush and the slap-your-head-and-jiggle-your-body for whatever). Alas, I don't see any reviews with a personality, damn the flat e-critic and the insipid wikipedia.

Also, at home, one can do a double shot without guilt. I watched Tampopo. It is a noodle-western. A tall man with cowboy hat comes to town and eventually teaches Tampopo how to clean up her act and make real noodles, complete with a real time exam in which the five committee members stuff themselves with hot streaming noodles in loud slurps and gulp down the soup (that animates the noodle!). Fabulous movie that makes one fly over to Kyoto for this and this. The movie gets a great review from Washington Post.

Finally, the funerals. I wish our research papers will get reviewed publicly like movies, plays and other works of (other) artists. Will our egos stand the panning from the ever-sharp NYer?

Tip of the Tongue Tapping at Three.

Night time sabar; Japanese tap; Old time tabla.
Triptych of taps, beats, and forms.

Signage

Driving into the city via the Holland Tunnel, one would see the welcoming business of eye glasses called The Tunnel Vision. And Dr. Fang who is a dentist. Signage in NY is a pleasant distraction, that deserves its own space in our psyche, separate from the art, threat and the treat of Graffiti.

Among all the signage in the city (example, see more at 14to42, is it even the city above the 14th?), I think the signage on scaffolding has a special place, ever ephemeral. On scaffolding (by the company aptly called Perimeter), I saw (no typos):
What is ugly to one is pretty two two.

Living, learning.

One gets into these (trust me, friendly) conversations when I was asked what I had done in my XX years (safe to stick to the two digit placeholder, I have passed the X phase and haven't hit the XXX phase yet). As in what I have accomplished, what I have to show for it.

I said, I have just lived and there is no total record of it all. My fearless moments, guilty pleasures eating fried chicken behind closed doors, thoughts that make me the walking lost, music I have found and destroyed, or all I have read, or whatever. Even about the worst of us, nothing less can be said.

Web search, research and chatter

Thanks to some work by the researchers, there is a page of google labs publications. Noticed some chatter on research in web search (companies):

• tracking. This has a "hockey-stick" plot: some quantity trends up like the hockey stick to the left or in unfortunate cases, trends down like its mirror image.
• experience. Discussion of internship+work experience.
  
• discussion. Lot of talk.
  

Days

Last night the city felt wrapped in a turquoise blanket, thick and textured (many I know just focus on the color of clothes one wears; textures matters just as much, as Sampath Kannan insists). Today, on Earth Day, the day is bright and promises to burn through one's psyche.

Friday was a day of "days":

• There was the NY Theory Day, held at Columbia. For long time, Zvi Galil organized this, and did a defining job. I remember his talk from 1992 that consisted of stripping off layers of T-shirts in his hunt for the lion in a desert (a parable that fits combinatorial search snugly, in particular, his result on parallel string matching).
• There was the Bay area algorithmic game theory day. Wish I had been there, fantastic collection of speakers/talks.
  

Couples

At 4 AM, I went for a walk and in the chilly, early morning, passed by two scruffy men, beer bellies (unshaven and pudgy), standing on a landing between two stores, each holding a brown bag with a bottle inside, sharing the following. One: "My wife is 36-28..". Other: "My wife is 32-29-.."

In the subway, past 1 AM, world is leisurely. I saw a homeless couple, he with this bulging shopping cart, and she with her baby carriage complete with the hood, large (but shaky) wheels, filled with newspapers and neatly piled plastic bags. The couple sat close to each other, even as the others in the subway at this time typically spread out, stretch out, avoid the smells and pass out.

Yearly party

The tax nite at 32nd and 8th, site of the main post office, is party-time. Tonight, even though the building was draped and undergoing the transformation into the new Penn Station, the party was loud as usual, with drums, hot food stands, cops, barricades, and the usual share of people outside giving out flyers for whatever cult they believed. The mass, NY's ordinary, was there, playing the script from previous years, walking into the noisy lines, bartering for stamps, jostling to get things stamped, walking away with relief. Btw, the Rangers fans were around as well, celebrating the 7-0 over Thrashers.

Running away

Kenya's Robert Cheruiyot won the Boston marathon and when asked why he did not look back to see if others were catching up to him after breaking away from the crowd, he said [USA Today], "When the lion is chasing the antelope, the antelope doesn't look back".

You can tell I stayed in a hotel last nite [USA Today].

Emptying one's pockets.

It is strange weather, bright and sunny yesterday, gusty, windy and rainy today. I left work to run through the cold rain and ran down the stairs into the subway, and when I caught my breath, standing on the platform, 1.45 AM Monday morning, I noticed that the station was being power-washed. The platforms were clean, smelled fine and for a moment, I was reminded of the platforms of suburban rails, if you discount the large man talking to himself, a chinese man swinging plastic bags from his hands, a woman sitting with her groceries, and a few other odd players looking for picking up one thing or the other. When I left at my stop, I saw and heard the bleating trumphet, amidst the dregs of NY society that prawls the subway nights, so I emptied my pockets into his trumphet case that lay open, nearly empty, near a puddle, and walked past.

Open problems

I am a fan of the culture of open problems, posing them, solving them, passing them around in parties to prod people into action. Two collections of open problems are interesting:

• Andrew McGregor has compiled a bunch of open problems on data stream algorithms, with background and bib notes. Excellent!
• Jiri Matousek has a fantastic tome of open problems on low distortion embeddings, recently revised to also show solved problems since the origins of this document in 2002.

What are we, if not churning machines that turn open problems into papers? :)

Taking a break

I was holed up in CA last weekend thinking about ajax and javascript, decided to take a break, and yes, work on writing up a paper. Thanks to the ever-smart Sariel, hearty Har-Peled, I had a writeup to work on (optimal bounds for a problem that appeared on this blog sometime ago). How did the boy who would burst out of his house when his break begins and rummage through the neighborhood on his wheels (back then, on a bicycle, one that made nearly as much noise as a Harley; you have to visualize this in black and white, except for the fiery red mud) , turn into a researcher who when his break begins, finds a quiet hotel in Mountain View and hacks at a laptop? Alas.

Search Auctions

Bunch of companies had sponsored search auctions built, launched, and producing revenue before researchers in academia really helped understand what these systems do and their equilibrium properties. There are two good papers:

• Internet Advertising and the Generalized Second Price Auction: Selling Billions of Dollars Worth of Keywords B. Edelman, M. Ostrovsky and M. Schwarz
• Truthful Auctions for Pricing Search Keywords. Gagan Aggarwal, Ashish Goel and Rajeev Motwani, ACM Conference on Electronic Commerce (EC06), June 2006.

Enjoy!

Taxing time

After a brief shutdown (wearing the Engg hat for sometime), I am trying to catch up on my blogging ideas. I know people say "today is the first day of the rest of your life". But it always feels like it the second, may be third day of the rest of my life and I am already behind.

Yesterday, in an attempt at celebration, I went to watch Craig Ferguson do standup comedy at comix club. He is clever (remembered the "Venti Sherry on the Christmas morning" of his from a while ago): when I watch him, I constantly feel he is going to lose it all anytime and the show will just explode into a place nobbody can handle. Wildly fantastic. Btw, the guy who opened for him (apologies, I forget your name, you were terrific!) said, "Internet, they sprung it on us. I mean, go back and watch Star Trek, looking into the future, with its gadgets. We foresaw cellphones. But, Internet? Nobody foresaw that! Star Trek characters don't say, "The Romulans, they just instant messaged us." or "Let me google the Romulans."." Funny.

Burger King, Your Way.

I think Burger King had an ad a while ago about the 1023 ways to order a Whopper(has 10 ingredients, you can have it your way, you do the math); the ref I could find was here, on Page 5. Burger King delights in burger variants, including this 1025th way: left-handed whopper. Andy Warhol has a unique way with a burger on the left.
BK's picture ads have been less than spectacular. Other pic ads here (check out audi).

Sigh.

I was visiting Cliff Stein at Columbia Univ yesterday and got to speak about Lance's decision to stop blogging. A lot has been said already, all true and point to high important it was, and it takes a while to appreciate the moment. For me, it was important because I use Lance's blog to showcase how effective the theory community has been in communicating with each other, and in fact, use that as an example to inspire other communities (for ex, databases and networking) to do it too.