Monday, May 28, 2012


On scale: Rakesh Agarwal and I spoke recently. A goal would be 10 Million sized online class room!

On NY: It survived the assault, going from "WALK/DONT WALK" to nonverbal "red hand/white silhouette".  Folks still read on subways, and the city remains a readers town.

On puzzle: A long time ago, I had a function calculator and a lot of time. So, I worked on the puzzle of starting from a 0 in the display and generating any arbitrary integer, only using function keys (arithmetic operators, sin/inv sin, log/exp, etc, all unary operations). Any pointers to this puzzle or its variants welcome.

On lingo: I heard of SoLoMo, and it is not about real estate. Social/Local/Mobile. Advertising.

Algorithms Day at Google, NYC

Google NY folks organized an Algorithms Research day following STOC and invited a bunch of STOC attendees. Vahab orchestrated the day, and from what I could see, the team of Nitish, MohammadHossein, Silvio and Jon helped out, may be others too, behind the scenes where I couldnt see. The team did a great job!

Eva Tardos, our newest Godel winner, started the day and talked about sequential auction. Bidders know order of auctions.  v_i(A_i) for items A_i for i. n bidders, m items. Goal: social welfare. Agents strategic. Solution concept: subgame perfect eq (for each subgame history). They looked at PoA of complete as well as incomplete information case.  The talk had an interesting example (Dining Bidders) that showed some of the nuances, and had one nontrivial bidding strategy (and its variant for analysis): each player draws  a random sample of value from others values and uses that to strategize. Costas and Moses asked what value distributions challenge the analysis and how the PoA of 3 is affected by the distribution. I asked, if the order of auctions can be determined and how that affects PoA.

Eyal Manor, the Engg Director for Ad Exchange (AdX), spoke next.  Q & A was the key, this was clearly an opportunity for researchers to get answers from a key person in AdX.  Bobby asked, why push bids for each impression sold, why not let ad networks push bids in a flexible way in small bulks. Eyal's answer was,  real time strategies seem important to AdX players.  Someone asked, there is information asymmetry, can AdX equalize the information available to all parties. Eyal answered that AdX did not own all the information in the ecosystem, publishers and other players do, and their data is private or secret. Eva asked, is BlueKai a pain in AdX operations? Eyal said they were good partners. Eva pointed out that Economics says what data should be shared: platforms should share, buyers should not have to share. Again, the issue is data is owned by many parties. Moses asked, what data are not shared. Eyal gave the example of someone day bought a ticket, bank login etc.

Alfred, VP of Google Research, spoke via video. He used the occasion to let folks know that Google was providing some space for Cornell's operations in NY, which is good news for Academia. Alfred couldnt resist posing some technical  challenges: we dont understand fairness of auctions to individual users; we have complex auctioning systems and very sophisticated distributed systems, how do we quantity and control risk?

There were several other talks during the day (bobby, gagan, mohammad, andrew mcgregor, et al) which I am unable to summarize here. Vahab gave an excellent overview of research in Google NY and provided pointers to folks who were experts in different projects. Towards the end, Mukund spoke about some interesting problems with interpreting sales data, and our other new Godel Prize winner Tim spoke about simple and optimal auctions.

Prabhakar called me an old timer, and I felt like one, slightly out of touch with it all. I ran the first of such meetings in 2009 after SODA, and it is great to see the continuing tradition. It was also good to catch up with Sanjeev, Stefano, Sampath, Seffi and others, that is just the S's.


Monday, May 21, 2012

On Generations

My dad worked in a coal mine for some time. He took me to work one day when I was a boy. I passed massive stalks billowing smoke, periodic loud noise from thumping machines, whirring conveyor belts carrying coal chunks, dust, stink and debris everywhere. I probably walked out with a piece of coal in my pocket and dirty hands.

Now when I take my daughter to work, I show her grey floors, neutral color walls, copier machines, and flat screens. The only thing that sputters, spits out hot water and steam, and makes noise is the Cappucino machine. She leaves clutching markers.  I hope in 20+ years she can find poetic words to think of her visit to her dad's office. 

Sunday, May 13, 2012

On Dining Astronomers

Recently, as part of a Berkeley meeting, I had outdoors dinner with a group that comprised Astronomers. There was a  serious side to the conversation, but I am going to focus on the friv:
  • Breaking off from a conversating group, holding a drink, one of them said, "Excuse me, I have to go start a telescope."
  • Talking about the impact of research, one of them said, "I mean, it is NOT earth-shattering". It occurred to me that Astronomers should not aim for earth-shattering research.
  • Finally, one of said, "We have astronomical data". To a half spaced-out Computer Scientist, it sounded like data Beyond Big. 
The astronomers convinced me that their work is difficult, because they can ONLY observe and study the data: all mining and no experimentation, but still fun. Outdoors dinner meant mosquitos, but as someone pointed out, even mosquitos are laid back in Berkeley. 

Are you being Creative?

I had lunch with several educators and the conversation started with the observation that many of the modern Internet companies treat their employees very nicely with great, free food, time to develop their own projects, and contribution to their volunteering activities away from work. Why do they do it? Answer is, they want their employees be creative: you dont want your software engineer to come to work in the morning at 9 AM and ask, "What do you want me to code?", but you want them to be at work and ask, "What can I do to make things newer, better, slam dunker, .?". Now, the question is, why dont universities do the same to their employees, say faculty members? Dont universities want professors to be creative?

ps: The conversation later turned to, "Are we -- professors -- asking our students to be creative?" Not one educator at the table thought we make our students creative. I need  a more optimistic answer from the World. 

Ad Exchange Research Contd

Here are my two recently released papers on ad exchange research:
In the first paper, we present a simple auction called the Optional Second Price (OSP) auction that is currently used in Doubleclick Ad Exchange. In the second paper, we present an efficient protocol for running OSPs in a provably trust worthy way.


Saturday, May 12, 2012

Sculpture, Then and Now

Sculpture Then: the Terra Cota soldiers in Emperor's Tomb in China from 3rd century BC has great scale and scope. I have always assumed the soldiers were for the protection of the Emperor in after life. But the tombs reveal more of course: eg., the organization structure of their society (as discussed here). But I loved the recent take by NY Times that he needed the army for this ultimate ambition of (having conquered China and History) conquering the heavens. Now the whole tomb makes sense!
Sculpure Now: Anish Kapoor is the 21st Century maestro. I managed to see his two exhibits at Chelsea Galleries recently: saw his concrete pourings for the first time and was awed. I was also with a friend in kurta with long hair, and the audience walked around us peering curiously at him, mentally calling him Anish. Salman Rushdie was in the audience too, undisturbed in NY audience.

ps: Sneaked into Kitano Jazz and heard Toshiko Akiyoshi.

Research Strikes

The long arm of research.  A paper 3 years ago by Balachander Krishnamurthy and Craig Willis that measured the leak of online personal information to third parties is cited in an FTC investigation that eventually leads to a MySpace violation citation. See the Forbes article, and Ed's FTC announcement.