Talks

Comedians have their acts posted on YouTube instantly, their material replayed later by many, and are therefore forced to generate new material for each performance. I am no comedian, but I thought I will use the nuclear option and post my talk slides, so I am forced to generate new ideas for talks. Here is a page with my talks, it will get updated slowly.

Puzzle Undone

I had a great time when Michael Rabin visited for the past few months. As he was leaving, he said "I did not get to hear a good puzzle", and I am ashamed. It has indeed been a dry season.

Anyway, here is a setting. n people go to dine at an Ethiopian restaurant, are seated on a circle, and order distinct entrees numbered 1,...,n in the order in which they are seated. The waiter brings them the food arranged p(1),...,p(n) on a circular plate, as they tend to do in Ethiopian restaurants. Of course p is some permutation of 1,...,n. Now, the plate has to be rotated in the plane to insure people have the entree they ordered directly in front of them. Questions:

• What is the worst permutation p, that is, no matter how it is rotated, it has the least number of entrees directly in front of the person who ordered them?
  
• Find a fast algorithm to determine the rotation that will maximize the number of people who will find their entrees directly in front of them.
  

If you are inspired by the setting above and find new problems/puzzles, I would love to know. I could not devise an engaging puzzle.

ps: Ans by David in the comments.

2 Round Monty Hall

I heard this version: It is the Monty Hall (MH) problem but in 2 rounds. A and B decide on their strategy ahead of time. Then A enters an instance of MH to choose the door with the car behind it, and if he succeeds, B enters the same instance of MH to choose the keys to the car. What is the maximum probability of success? Notes: There is no communication between A and B once the game begins. It is not success if A finds the key and B the car. This puzzle has apparently hit the blog world.

Free

For all practical purposes, electronic storage is "free''. We see its implications everywhere (see review of Chris Anderson's book). An extension of it is, let us say, electronic publication of conf or journal proceedings is "free''. Then, how will our world be different? Do we really need page limits on paper submissions, and force authors to do baselinestretch, use times font, and other torts?

ps: Of course people will argue it is not really free, or that ultimately, the measure to optimize is readers' attention, so we need confs to select and rank papers, and authors to write papers in a prefix-complete sense (readers read from the beginning and stop when they want to, and the results should make sense no matter where they stop), etc.

COCOON 09

I was at COCOON, held at an edge of US, where the Niagara river goes over. I got there in time to hear Venkat's very nice talk on inapproximability of certain ordering problems like maximum acyclic subgraph (MAC) and permutation CSP. A message was that it is hard to beat random ordering (for MAC), and Venkat gave a lot of intuition into formulating the notion of "approximation resistance" (CSP). He also described the larger context of UGC hardness and approximating CSP problems via SDP, established by Raghavendra. I wanted to give a talk on Configuration Auctions, but ended up giving a more general talk on Internet Ad Auctions. I will put slides up soon. One of the nice things about theory conferences, no matter which one, there are always nice problems/techniques one hears.

SUNY Buffalo, the local host institution, is associated with quality theory in my mind. I got to talk to Atri Rudra and heard about some of his nice new results on codes in the streaming model. I also had a great talk with Hung Ngo on analyzing probabilistic data, wish I had more time to talk about some networking problems.

Finally, I completed nearly 20 years of my life as an immigrant in NY by visiting the Falls for the first time. I am a freak for large bodies of water, and the simulated waterboarding as you stand under one of the falls and gasp as your lung expands, was cool. Also, I got reminded that we all have reasons why we are theory researchers. Me, I left my undergraduate school vowing never to read another IEEE journal again. With the exception of some amazing thing by information theorists, for most past, I have succeeded.

NY Friday AM

It was hot and humid on the street, unbearable on the subway platform. Three men in dark glasses start singing, "I've got sunshine on a cloudy day, .... My girl (this girl, that girl), ..." It was wholly inappropriate, but slowly people suffering on the platform saw the possibilities. Wallets that got stuck to the pants that were stuck to peoples' bodies, got pried open. It was beyond the commute hour, the wait was longer, the cash bag got fuller, people tried to smile knowing the cool blue train will eventually get there. That is my story this Friday.

Things I Think About

Ahuva said something that led to this post. Days, amidst their chaos, give you a few minutes, when you can reflect. Some do it when seated in an airplane, they anticipate the taxiing of the plane down the runaway, and let their mind wander. Others do it when meetings meander, or have dinner with relatives and the conversation lulls. What I have been thinking about:

• [Worth of Information] If you had access to the location of people for every second, accurate to (lat, long) coordinates, for several years and continuing, for millions of people, how much -- $'s -- is it worth?

• [MJ, MJ, BO] NYT says, "Mr. Jackson was to music what Michael Jordan was to sports and Barack Obama to politics ...". Everyone I know thinks one of the 3 --- a different one for each --- does not belong to the list with the other 2, based on some hypotheses they have in mind for the analogy. The question of course is what did NYT have in mind?
  

EC 09 Travel

Travel to confs is when you do a little bit of many things, not a lot of any one thing. I traveled to EC to be part of the gestalt of Electronic Commerce (note to organizers: must change the name!).

• EC started on Monday with the Workshop on Ad Auctions, a feast for specialists, papers flying off on themes of externalities, expressive bidding languages, pricing and equilibria; all papers are online.
• Next (for me) was the Tuesday of tutorials. Jon and I did a tutorial on sponsored search and took a risky route, not talking about auction design. Jon splendidly laid out the world of many knobs that advertisers face (as one researcher exclaimed later, "And we work on what auctions to run?"). I spoke about how to optimize ad campaigns with a given budget. Researchers angst about whether advertisers care about clicks, profit, ROI, conversions, or whatever; do they consider interaction between keywords, broad match or stochastics, etc. My main point was these goals --- notwithstanding our passion to apply LPs or discover hardness of problems --- can all be compiled down to the knapsack problem with suitable weights and values, to some approximation. Then, simple bidding methods work. I ran out of energy some, and did not wrap up this argument like I wanted. I hoped to give an effective way for advertisers to think about their ad campaigns.
  
• EC Conf started on Wed, banquet-ed on Thurs and sputtered on Fri. I liked the two papers (1, 2) that tried to understand the price of truthfulness in learning click-thru-rates for revenue/efficiency in ad auctions. At the banquet, we learned Nicolas Lambert continued his run and won the best paper award at EC. On Friday, Michael Moritz, a journalist, venture capitalist, and surely other things too, gave a keynote talk.
• Nikolay Archak (data analysis), Tanmoy Chakraborty (cs theory) and Mallesh Pai (econ) are all interns in NY who were at EC as well, and I got to see the conf from many different perspectives through them. Nitish Korula, who was at ICALP, was missed.

When in confs, you discuss issues: on impact and problem formulation (Mukund Sundarajan), role of knapsack a la plastics in The Graduate (Rakesh Agarwal), estimating sparse queries (Bill Chang of Baidu), expressive allocations for large publishers (Tuomas Sandholm), etc. You catch up with friends as their lives evolve and some --- Arpita, shoutout to you --- let out their creativity. Finally, this is Palo Alto, you take an evening off and catch up on startup companies and VCs.

FOCS and Streams

Sounds like the name of a pub in Britain? Well, I came home after a long day and looked at the theory world in blogs, and saw the FOCS09 accepted list had been ripped apart into geometry, game theory and I am sure many others (eg learning, complexity, approximation) in peoples' minds. But there is a hanging chad and I will take it. People ask me whether streaming research is active. I am happy to point to (at least) three streaming-like papers in the list, so yes, it is active.

• Exact And Approximate Pattern Matching In The Streaming Model. Ely Porat and Benny Porat.
• The Data Stream Space Complexity of Cascaded Norms. T.S. Jayram and David Woodruff.
• Efficient sketches for Earth-Mover Distance, with applications. Alexandr Andoni, Khanh Do Ba, Piotr Indyk and David Woodruff.

Check Out

Check out these co's and products:

• News aggregator+reader for iPhone from Fluent Mobile by Micah Adler.
• Platform for multi-core programming from Cilk Arts by Charles Leiserson et al.
• Accelerating database operations using Fractal trees and more from Tokutek by Michael Bender, Martin Farach-Colton, and Bradley Kuszmaul.

Talks, Tutorials, Truthfulness

Jon Feldman and I will be giving a tutorial at EC 2009 on Sponsored Search. But we promise not to rehash auctions. In fact, tutorial will focus on an advertiser point of view, so more optimization than auctions. We are also running an ad campaign to collect stats:

EC 2009 Tutorial Feldman, Muthukrishnan: Information Exchange in Sponsored Search. www.sigecom.org/ec09/..

There are at least two forthcoming talks of great interest, but you have to choose one: Susan Athey will speak at EC09 on Wed, July 8, at Palo Alto, CA. On Thurs, July 9th, Noam Nisan will speak at ICALP09 at Rhodes, Greece.

Finally, truthfulness. Can we design a truthful mechanism for budget-constrained bidders in a series of ad auctions? If you wanted to maximize the number of clicks, in some cases one can design such a mechanism [FMNP SAGT08]. If you want to maximize profit, such mechanisms can not produce Pareto-optimality [DLN FOCS08], but in a forthcoming paper at Ad Auctions Workshop, Ravi, Hafalir and Sayedi show a very nice, simple semi-truthful mechanism that is also Pareto optimal.

Change of Proceedings

I was browsing the FSTTCS conf site (this conf may be lost in the din of FOCS+STOC vs ICS+SLOGN wrestling, but is a solid technical conf), and noticed:

Proceedings:

Accepted papers will be published as the proceedings of the Conference in the Leibniz International Proceedings in Informatics (LIPIcs) as a free, open, electronic archive with access to all. Authors will retain full rights over their work. The accepted papers will be licensed under the Creative Commons Attribution-Noncommercial-No Derivative Works 2.5 License: Creative Commons -NC-ND

FSTTCS, like STACS, WADS, ....., had standard LNCS proceedings. What changed?

Michael Jackson

After a long day of work, I passed out at home on the couch while wondering what I should write for a SODA submission. At 2 AM I woke up to the music of Michael Jackson coming from outside. I went down to the streets and saw MJ was blaring from a SUV. Tourists, residents in pajamas, street vendors crawling from under their vending table on the sidewalk where they had gone to sleep, homeless, and the perennials who take over the Manhattan street at night joined in, wildly dancing. Even a snippet of his music is instantly recognizable, and everyone knows a MJ dance move or two. MJ bit and spit out words. Crowd rocked the SUV. Traffic altered itself to let the party be. As I left, a man was running to join in, carrying flowers he had surely plucked from some garden in the neighborhood. Leave it to MJ to inspire, in his life and his death, an instant homage at any moment.

ps: The summer I spent in LA in '95 would have been miserable without MJ's HIStory.