Sunday, February 27, 2011

Ad Exchanges Revisited

My research on Ad Exchanges has continued, but I have been quiet on blogging about the business. Here are some updates.
  • It has been more than a year since the launch of the DoubleClick Ad Exchange. It seems to be doing well. See the presentation here for stats. Of relevance to research: "in January of last year the real time buys on DoubleClick’s AdExchange represented just 8 percent of the total. By January of this year, that figure was 64 percent." So, many research problems with real time bidding are now important, from optimizing call out, to understanding the game theory, arbitrage and others.

  • Individual publishers are building private ad exchanges around their own inventory. CBS Interactive,, NBC Universal (universal audience platform), (channel 5) and Turner Broadcasting Systems. "For publishers, setting up exchanges has several advantages: they cut out the middlemen and they allow the publishers greater control over consumer data." Check out NY Times article. This means there is a lot of research to be done on inventory optimization, understanding the dynamics of advertisers automatically choosing across publishers and so on.
Hooray for AdX research!


Shout Out to Anja Feldmann

My friend, collaborator and a cohort from old AT&T days, Anja Feldmann, a networking researcher for long, has been awarded the Gottfried Wilhelm Leibniz Prize 2011. Awesome, congratulations!

About the prize:
The Gottfried Wilhelm Leibniz Prize is the highest honour awarded in German research. The Leibniz Programme, established in 1985, aims to improve the working conditions of outstanding scientists and academics, expand their research opportunities, relieve them of administrative tasks, and help them employ particularly qualified young researchers. A maximum of € 2.5 million is provided per award. Prizewinners are first chosen from a slate of nominations put forward by third parties; the final selection is made by the Joint Committee on the basis of a recommendation from the Leibniz Nominations Committee.

Friday, February 25, 2011

Ode to Men -- of Certain Age ---Shopping

I can give (for my friends who seek it) advice on shopping in NY for anything from clothes to chocolates, but I dont enjoy shopping or chocolates. It is just information I have because I like all sorts of information.

I went shopping for shoes and clothes today. I am more bling-bling than Eddie Bauer, so the "usual" places I go to have the property that without much thinking I can find unusual things. And sadly, I noticed today that inches are not what they used to be, they seem to be getting shorter, and I dont fit into the sizes I used to. :)

Wednesday, February 23, 2011

Theory Day in The Netherlands

The Dutch Association for Theoretical Computer Science (NVTI) supports the study of theoretical computer science and its applications. One of the activities of NVTI is the organization of the yearly Theory Day with a combination of speakers from The Netherlands and outside. Here is the link to the 2011 version, to be held on March 4, and a link to the past list of speakers. I will speak on Data Stream Theory and hope to include some new results, slowly getting back to this area after a hiatus. The last time I was in Amsterdam, I was an unformed youth with rollerblades on my back and a restless mind. This time, the rollerblades will not travel with me.


Saturday, February 19, 2011

Renewal, NY Style

I have been down some, mojo in a freeze. A couple of recent incidents are helping with the thawing.
  • I rode my bicycle through the streets, holding two dozen black and white balloons on my left hand. The day was windy and I made a bulbous figure crouched on my bicycle, swerving to avoid parked cars, darting pedestrians and trying to not interrupt the flow of taxis that slowed as they approached me, and sped off with relief when they got past. Children waved and wanted to reach out to the floating ying yang, but my moment was made when two tourists stopped me to take pictures, with the cobble-stoned, graffiti-filled Tribeca for the background.
  • Yesterday it was warm, but the Parks dept is yet to catch up. The Imagination Playground was closed. I saw a few children and parents inside, including what looked like a 7 month pregnant woman. When asked, they said, "just hop over the fence". That is how one has a pleasant PM in Burling Slip, NYC. NYers dont wait out the winter, as much as spring ahead.

Edible Geometry

My review of the book, Geometry of Pasta. With beautiful black and white prints. Let me list the pasta types I talk about in the review (so you dont have to rely on my spoken Italian): Penne, Rigatoni, Orecchiette, Reginetti, Strozzaprati, Stellini, .... Who knew that geometry could be edible.

Friday, February 18, 2011

Simons Science Series: Sanjeev Arora

Sanjeev Arora needs no introduction for us CSists. To the larger audience of scientists and mathematicians at the Simons Science Series, David Eisenbud introduced him by pointing out his great trajectory in academia.

Sanjeev started the talk with an informal view of P vs NP and phrased it as "Can Brilliance --- someone gives us the solution, we check it and exclaim why didn't I think of it --- be automated?". The mathematicians briefly struggled with ease of checking decision vs optimization versions of a problem. Some in the audience needed to know what was n (input size in bits), whether P/NP was machine-dependent (under strong Church-Turing hypothsis, NO), or did randomization help (Not believed to help P vs NP). Given NP Completeness, how do we approach the world? Sanjeev pointed out the heuristic code-it-up approach vs average case vs approximation theory. Then he used the max-cut approximation as an example of approximation theory: GW approximation, inapproximability without or with UGC (no time to explain UGC in the talk). The local audience close to where I was sitting expressed some wonder at these numbers and the tightness. Sanjeev used this moment to make a meta point: the failure of SDP on some instance can be turned into inapproximability result. Then he discussed the PCP theorem, motivating NP = PCP(log n , O(1)), discussed gap amplification with an "impressionistic proof" and described Dinur's checking algorithm for maxcut. Rest of the talk meandered through KKL, Euclidean TSP, etc.

The audience had many question: does PCP theorem apply to natural language math proofs (ie can we replace referees in journals); in practice what does it mean if P=NP? (Crypto will collapse, SAT in o(n^2) might change worlds); do people work on P vs NP (Sanjeev didnt fall for the temptation to give examples of attempts and said when you work on a problem, you constantly keep both algorithm and complexity in mind, and eg wonder if I solve this piece, will it have a bad implication),;any connection to machine learning and data mining (some of the key problems there are hard to approximate); etc.

Well, Sanjeev is a prince of a researcher and he did a great job of presenting central thoughts related to P vs NP question. I was very pleasantly surprised by how audience related to the PCP theorem: many in the audience, seeing it for the first time, really saw the power of the theorem and its enormous implications. For the evening, maybe without intending, Sanjeev represented the SIGACT Committee for Advancement of Theoretical CS ("Increase awareness of theoretical computer science's activity and successes in general CS, and the public at large.")


Thursday, February 17, 2011

A Report (Financial Crisis) and an Observation (Apple)

Here is a report: the Financial Crisis Enquiry Commission has its report out on the Great Recession from 08. It is a fascinating account, one would imagine there is a lot here about network effects to model and study as (armchair) Economists.

Here is an observation: Apple is a company that nurtures and thrives on its image as an innovative company. Yet, it is surprisingly absent from the world of academia, and does not seem to support research either directly by employing a research group or vicariously via grants, or indirectly by having their employess --- Applers, is that what they are called --- attending conferences. This observation seems to say something about either Apple or Academia.


Saturday, February 05, 2011

NY loses Yasuda

It is 2+ months old news, but I could not bear to talk about it earlier. My sushi chef Yasuda leaves NY. NY Times does a piece, aptly, elegy-style. If someone has the address for his new (8 seat) sushi bar in Tokyo, please let me know. A flight to Tokyo is small price to pay for the master. Some pictures of his incomparable sushi here. And his parting gift: Sushi Nori Yasuda.