NYCE 2009

NY Area CS and Economics (NYCE) II meeting took place on Monday, Nov 6, and was organized by Robert Kleinberg and Eva Tardos.

• Jennifer Rexford led and spoke about interdomain routing in IP networks. She started with a simple model of local rules for path selection that converge to stable paths for routing between IP domains, and later generalized it to picking multiple paths via source dependent path selection. She is an admirably clear speaker on a topic with many details (original RFC here). There were many questions on machine learning (are there algorithms to learn the ``value'' of paths), technology (how to simulate these policies by say MPLS protocols), incentives (domains choosing cheap paths over secure paths, fishing for information via strategic path announcements), and verifiability (can routers send traffic on whatever path they choose despite what they advertise).
• Shahar Dobzinski spoke about truthful polytime approximate mechanisms for multiunit auctions. This was classic AMD material, delivered straight. Questions explored monotonicity (eg quasi-monotonic valuations such as cant use >10k oil barrels) and variance of allocation.
• Michael Kearns showed his theory roots and applied arms. He spoke about matching buy and sell orders, not in light pools where the book shows bid and ask prices, but in the dark pools where only liquidity counts. He proposed an exploration-exploitation approach to buy large orders in dark polls, ultimately deriving RL type algorithms. Questions included role of Crypto protocols (not a good idea to enforce trust, better to remove conflicts in the system design), Strategic orders (to sniff information), and quality of price in light pools (since dark pools set price using light pools but their demand and supply are not reflected in the price at light pools), etc.
  
• Lunch in the financial district is always an exercise in avoiding crowds.
  
• Post lunch, there was a rump session of 5-min talks. Beibei Li spoke about ranking hotels by mining web data. Sharad Goel spoke about pricing ads per impression plus a click cost. Eyal Carmi spoke about quantifying derived effects on an item of a sudden spike in popularity of a related item. Mickey Brautbar spoke about algorithms for finding nodes with high degree (why these are "interesting individuals" is presumably discussed in their ICS paper?). Aaron Jaggard spoke about impossibility results for distributed decisions, from here. Vahab Mirrokni gave a clear talk on quasi-proportional mechanisms and their equilibrium revenue properties. Ruggiero Cavallo spoke about limited amount altruism in auctions. Other talks discussed social network effects to long tail phenomenon.
  
• Larry Blume gave the final talk. He started with several simple examples where we reason about probability, but implicitly with different meanings. He then formally defined different measures of ``probability'' and "expected utilities" including non-additive ones, and worked into applying them to Economic choices agents make. I was overwhelmed by the rich notions of rationality in Economics, and would like to work out some nontrivial examples of applications of these concepts. I liked the narrative in this talk, and Larry is consummate researcher switching between Math and insights, with anecdotes as needed.
  

One of the interesting aspects of NYCE is the audience from business schools to, as it turned out, businesses. The NY Academy of Sciences venue is superb, and the staff run the meeting smoothly.

Goats and Tweets

I watched Men Who Stare at Goats. It is a Catch 22 in 2009 kinda movie, essentially all male, exploring psychics, US Army, goats and LSD. Hilarious and unpredictable. You can't go wrong for acting display putting Kevin Spacey, George Clooney and Jeff Bridges together, goats help.

ps: Twitter turns a movie rater, being a critic however takes more than tweets.

Algorithms and Media

There is a wonderful interview of Michael Rabin about his visit to Google at the university relations page. My favorite part is when he is asked for his advice to students and he says, "algorithms, algorithms, algorithms".

Moti Yung gets cited in Harpers by Barry Eisler.

The phenomenal Ingrid Daubechies is quoted on the game theory behind how to divide a real estate empire threeways: three parties bid, lowest bidder partitions the estate into 3 parts, then a coin flip decides the order among the other two to pick their choice of partition. The goal seems to be to get a envy-free solution.

Need a laugh

A new week will begin soon, we might as well laugh now.

Let us call this a tweet

I may not live in the pint of a street Minetta Lane for much longer, but Minetta Lane is now in Songlines and a minute ago, I put my head out of my window, the Halloween parade had just started, a hundred or so paraders paused where Minetta meets the 6th, and did Thriller in sync. What bliss.

Private Streaming

My student Andre Madeira successfully defended his Phd thesis last week. Andre is culturally universal moving across countries and languages, and CS-wise broad, working on thesis at Rutgers Univ, working as an architect for secure data storage with CommVault Systems Inc, and starting now at Google Inc. in NY. Among other things in his thesis is recent work with me that initiates the study of privacy-preserving algorithms in the streaming model.

• You need a basic building block for streaming, namely, a random access to a long vector of suitable random variables, without storing all of them: we use certain pseudo-random functions to get these. The standard use of pseudorandom generators from streaming algorithms does not suffice.
  
• You also need algorithmic building blocks --- like sampling and sketching --- to base your algorithms. We show how samples with small bias suffice for functional privacy in some cases.
  

These give first known private streaming algorithms for many problems (eg., for usual suspects like L_p norm estimation), and builds on some of the earlier work of Indyk and Woodruff for privacy preserving algorithms with polylog communication (btw, this IW work deserves more attention, some nice mix of data structures and privacy preserving stuff in it).

Ad Exchange Research

There has been a lot of CS/Econ research attention on sponsored search, not as much on display ads. For a large part, display ads on the Internet have been bought and sold over telephone by sales teams; to a lesser extent, they have been outsourced to intermediate networks and agencies. These processes represented few research problems, if any, to study. In the past few years, however, ad exchanges have emerged as an alternative where display ads can be bought and sold via real time auctions, and these automated exchanges are a great source of challenging problems.

Here is my writeup that describes a model of ad exchanges and proposes research problems in auction theory, optimization algorithms, and other areas that arise; this is the text for my forthcoming talk at WINE 2009. It represents insights from working with the terrific team that launched Google's Ad Exchange recently. Here are official blogs 1 and 2, Noam's post, and other posts, on the launch. For general ad exchanges discussions see: ads 101: ad exchanges, real time bidding, etc.

Friday Sundries

The week is winding down, and here are a few thoughts:

• [the weather] When people talk about the Fall, they talk about the colors, and beautiful rides to see them. But for me Fall is always about the wonderfully gusty winds. Every NY street corner becomes a setting for a French film with men and women grappling with their flying hair, or skirts that stick to them, and swirls of fallen leaves rising off the ground.
  
• [coops] NY has coops. The real estate ones are the most known. But under the radar are the food coops. NY Times has a poetry of a piece on the Brooklyn food coop, a must read. To quote: “I’m seeking the olive packaging boy that was laughing at my jokes and wearing plaid pants,” said a Craigslist “Missed Connections” item last winter. “I was wearing the leopard print glasses and my responsibilities included: Mozzarella whole milk, part skim and plain goat cheese.”
• [plays] As weather cools, people head indoors and there are always plays to watch. I watched Vigil, a two-person dark comedy about a talkative nephew harassing his bedridden old aunt to death. It had some great lines: “I’m concerned about your health these past few days,” Kemp says. “It seems to be improving.” or "Why are you putting on makeup? Why don't you let the mortician do that?"

CI Fellows

Here is the official list of CI Fellows supported by NSF. A few Algorithms/Theory mentors here including Suresh, Eva, Boaz, Satish.

Parallel Models Again

Recent discussions reminded me of three papers, new or old, on parallel models:

• MapReduce has inspired many in the past few years. The upcoming SODA paper by Karloff, Suri and Vassilvitskii has a new computational model for it. For example, the model allows n^{2/3} machines each with n^{2/3} memory for a problem of size n, and works in a series of polytime map and reduce steps. There are a couple of interesting results in this model for s-t connectivity and MST.
• PRAM has been "fixed" many times. A variation of PRAM that allows log n processors is in Dorrigiv, Lopez-Ortiz and Salinger. There are some general partitioning results for dynamic programming and other techniques.
• There is the agenda of using Graphics Processing Units (GPUs) as parallel machines. Suresh wrote a great note abstracting a model in 2003. Since then, more communities are following this agenda. A few weeks ago I heared about GPUs being used for medical data analysis.
  

Upcoming conf deadlines

October is the precursor to the conf deadlines. WWW: Nov 2; STOC: Nov 5; SIGMOD: Nov 5; SIGMETRICS: Nov 9; SoCG: Dec 2; PODS: Dec 11; . Happy LaTexing! Crispy papers hot off the laser printer is intoxicating.

polylogblog log

Data streams get a voice. Andrew McGregor enters the blog world with the polylogblog. Fantastic! Now, a few others areas can use their own logs.