Sunday, January 24, 2010

Researchers in the Neighborhood

Even in the winter of Feb, we get research visitors in the neighborhood.

SIGMETRICS PC meeting took place up in Columbia U the last two days. Alas, I had to make my case over the phone (a crucial moment of vote taking for a paper went as follows: all against? everyone physically in the room. all for? everyone on the phone, which was just me. :)). Later, I managed to grab dinner with Paul Barford who was co-chairing the PC. Paul is sorta maverick of a researcher in networks (measurement/security), with whom you can discuss irreverentially about what are the grand acheivements, failures, challenges of the area, and come away with insights and conundrums. Paul may not know I have been reading his papers since his 1997 work on generating webserver workloads.

Next week is WSDM in NY. Torsten Suel, NYU Poly and Brian D. Davison, Lehigh University, chair the PC and have put a nice program together, with Susan Athey and Soumen Chakrabarti giving the plenary talks. This should bring a bunch of researchers into town.


Saturday, January 23, 2010

Online matching or Is it ad allocation?

The online ad allocation (OAA) problem is the following: "Suppose there are n bidders with known daily budgets B_1, B_2, ..., B_n. There are m queries, that come online. When each query j arrives, bidders i = 1 ,.., n submit bids u_{ij} . The algorithm has to allocate the query to one of the bidders, without knowing the future bids. If query j is allocated to bidder i, then the algorithm collects revenue u_{ij }; however, the total revenue collected from bidder i cannot exceed B_i." Replace bidders and queries by nodes, bids by weights, and you have an online bipartite matching (OPM) problem variant. So, when is OPM an OAA, really? In other words, when is OPM a real applied problem, and when is it pseudo?

In any case, this is a meaty problem and here are three examples of what we know in theortical CS community:
  • Aranyak Mehta together with his coauthors (1,2), showed a tight 1-1/e bound for the problem in the worst case, and that when the input is a random permutation, even greedy algorithm achieves 1-1/e approximation (which is nice since algorithms for this problem in "practice" can be interpreted to be of this genre). These papers provide great clarity and sophisticated analyses, TCS-style.
  • Nikhil Devanur and his coauthors (1) show that under the random permuation model, there is an algorithm that gets 1-\eps of the optimal. This work has nice insights mixing primal-dual thinking with PAC learning, insights that are getting refined as they get applied to other problems.
  • Nitish Korula and his coauthors (1) study a variant where the constraint is on the number of allocations (not on the budget) per advertiser and show an online 1-1/e algorithm (under a free disposal assumption). Nitish's followup work shows that such primal-dual algorithms have other desirable properties including fairness, an issue I suspect will get explored more in the future.
Taken together, the triptych of these results show TCS researchers know how to dig deep and get important insights.



Like others, I have many simultaneous avatars, but others see me as something even beyond.
  • When I travelled with long hair, officials at airports thought I was a musician. Alas, I have no musical bones, cant sing, strum, hum or drum.
  • One day years ago when I dropped several hundred dollars getting my hair braided in San Diego, the braider --- who came from Africa --- was convinced I was a bollywood actor. Alas, I am a mutt, can't hold an accent, posture or a pause.
  • Yesterday, hair thining, holding dry cleaning in my hands, I rode up the elevator with a Mover who asked, "You, a film Director, Man?" Alas, I can't cue or orchestrate, and not meander.
Anyway, why am I telling you all this? I watched Avatar last night, in 3D. Suspend your thinking, enter and enjoy the bioluminescent Na’vi-land, I left the film theater wishing I could hop over trees, ride a Toruk, and be wallet-less.

Sunday, January 17, 2010

Confs: EC, FUN, WWW

Monday was the EC Conf Deadline. The day before, I had a 20+ pages of symbols and logic understandable only to the authors, so I had to sling that thing over my shoulder, go sleepless for a night, and produce the magical 10 or so, clear to everyone. Deadlines should end at sane local times so you can do something after. After the EC deadline, I went to catch The Stray Dog, part of the Kurosawa Centennial at Film Forum. Young Mifune is unrecognizable, made in 1949 this film is a gem, it is The Bicycle Thief of postwar Japan.

Deadline gets delayed: FUN moves its deadline to Jan 24. There is the constant din of conf discussions in our community, whether it is to accept innovative papers, or textbook algorithms or whatever. Also, there is a constant clamor for video talks or submissions and other tweaks. Seems to me that some of these would be appropriate for FUN, so we have a few days to "... sling things over ... shoulder...".

I was at a PC meeting the past few days. PC of WWW has a two-tier structure. Reviews review. Area Chairs (ACs) push reviewers to discuss if needed to reach consensus. Then, ACs represent the discussions to the rest of the ACs and defend and modulate the decisions. Also, there are secondary ACs to sanity check the primary ACs. Even with this process, at some point, the ACs meeting got tiring with ranks dwindling and clock running down, the PC Chairs Juliana Freire and Soumen Chakrabarti had to "sling things over ... shoulder.." and drive the PC to the conclusion. In general, I can switch context in research fairly easily, but even I was in a daze, following discussions on papers from equilibrium analysis for ads to approximation algorithms for social networks, machine learning for user behavior on the web, specification languages, user interfaces, systems, recommendations, annotations, twitter, mobile, and many many others.


Sunday, January 10, 2010

Two recommendations

Vestry Wines in Northern Tribeca. Space designed by Jae Chang. Specializing in smaller producers from Italy, France, and California. Fantastic staff, say hello to them from me if you go there.
Macaroons on the left from Madeleine Patisserie in Chelsea. Gets compared to "Payard’s, Bouchon Bakery’s, and La Maison du Chocolat’s, ... Ladurée in Paris and Confiserie Sprüngli in Switzerland" in chow.

Triptych of Teachers

People who teach are special.
  • A long time ago, I was a boy, not yet a teen, and lived in what was essentially slums. A young, idealistic single man of a school teacher who lived a few doors down gave us kids a few sheets of paper with facts about the world (called "General Knowledge" or "trivia"), and ran a competition later to figure out who knew most. I learned that elsewhere, away from where I lived, there were large mountains, different kinds of money, and people believed in different things. I won the competition and got a pen as the prize which I am sure I promptly lost in some boyish game or the other. Looking back, I am thankful to that teacher, and realized that I learned then to travel (very) light in life, not carry much of the present into the future, not much of one place to another.
  • Later, when I was an Engineering student, I liked building circuits, solving puzzles, and like a typical youth, lived every day with the desperation of a person who has a single bullet left and longed to fire it. But CS was mainly tedious and I was disillusioned. 3 years into the program, PPC, a young professor, barely out of his PhD, taught a course on Algorithms, showed me the wonderful structure and brought the fun of problem solving back in to my life. Much late now, I may have learned more tricks, but I learned everything I needed to know then, from PPC. PPC it turns out is a pipeline, turning many other disillusioned engineers to theory research in the past 2 decades (you know who you are!).
  • As a graduate student, I was somewhat beaten down by the rigor of STOC/FOCS/SODA research. I liked holding the crisp, 10 pages, LaTeXed paper in my hand and could even drive myself to produce it, but somehow the experience was like having rushed to get few steps into the intersection to beat the traffic light, you wanted to rest some, but have to walk the rest of the distance to cross the street before the flashing light turned solid.For several semesters, once a week, I would go to Joel Spencer, coffee in my hand, and he would excitedly describe to me proofs -- his or others', it didn't matter, whatever caught his imagination that week -- and for a couple of hours, nothing else mattered, except probabilities and nifty asymptotics. Looking back, I realize those moments felt like the rush when you get to the net and volley, if you know what I mean, having baselined all week. Teaching is finding ways to make students feel that way.

Graduate Fellowships

Increasingly, companies are offering variety of support for graduate students, in particular, in Market Algorithms and other areas. Here are some examples:


Thursday, January 07, 2010

Ads/Auctions Courses

Ultimately we are all learners. Once in a while, I look up courses on topics of my interest to keep myself educated. I liked
  • course by David Parkes at Harvard on Assignment, Matching and Dynamics. The list of papers/book chapters that formed the course, as well as notes and presentations are available online.
The selection of topics is closer to my interest than


Sunday, January 03, 2010

Ad Exchange Followup

You let out something into the world, you have to follow up, that is what I believe. Here is some followup on Ad Exchanges.
  • In the list of best articles about online advertising in 2009 is an old article that reviews a few of the ad exchanges. It manages to communicate the idea that real time bidding is important.
  • This article insightfully discusses the need for advertisers and publishers to get more sophisticated (to "deaverage"), when bidding via ad exchanges for display ads. "How many relevant mathematicians are on your team, that can handle machine-learning and statistical inference type problems, utilizing data from advanced data mining?"
  • Adexchanger looks at search trends and finds the bump corresponding to the release of Doubleclick Ad Exchange.
  • Research-wise, bunch of results out there which should come out over the next few months.
ps: Here is a set of slides in David Parkes's class on my Ad Exchange paper. Some more discussions about Ad Exchanges: platform aspects, real time bidding, challenges in ad reach, transparency, etc.

Friday, January 01, 2010

Happy New Year

Well, what do you want the new year to be?

Sometimes I get asked how I do what (how much) I do. This question people should really ask Michael Mitzenmacher or Terry Tao or ... I tend to focus on what I don't do. One of my regrets is that while I read others' blogs, I haven't been able to contribute to the discussions there as much as I like. Commenting needs different personality from writing a blog, so I need to find this new personality, this week, year or decade.

And a note to self: I often face the divide between theory and practice, first hand (when I do my work), second hand (when I referee or hear a talk) or third hand (when someone describes others' work). Mostly I see people respond with pseudo-theory, or pseudo-practice. Must recognize and resist this temptation!

ps: What is new year without fun? Give the setting of 3rd century China and a cast of thousand to John Woo and watch arrows fly. It was the time when Generals fought on the battlefield. Real warriors will ignore the crossbow -- the wii of bows -- at the end.