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.

Fall day in NY

Someone reminded me I haven't talked about NY (or beer) for a while. Today, a fall day in NY, the light was perfect. On the left is what one buys for beers in NY: well's banana bread beer (uk), traquair house ale (scotland), samichlaus classic (austria), and moa (nz). All exceptionally rare, but in the village, you walk a block and pick them up at Hercules Fancy Grocery.

October Festivus

October is here, modulo Tigers and Twins who stretch it to Tuesday. Soon, there will be some sweet playoff baseball and the breweries in NY will politely challenge Munich for the Fest. Two comments on Sept blogs:

• Mihai's post and the discussions on and off the blog world reminded me, there is a little bit of Howard Roark in all of us and a little bit of Antonio Salieri, question is where we leave the dial at any given time.
  
• Noam urges academia to take a broader view of research and academic output. The best way to urge is by an example, and Noam is leading as a great example with incredible breadth and depth in CS and beyond.
  

Web Random Bits

We often need random bits. People toss a coin or use noise from transistors or whatever to obtain random bits in reality. Here are two tasks.

• Devise a method to get random bits from the web. The procedure should not use network phenomenon such as round trip delay time to random hosts etc, but rather should be at application level. Likewise, the procedure should not be to go to a website which tosses coins for you. Rather, it should use some existing web phenomenon or content. Btw, quantifying/discussing potential biases will be nice.
  
• Devise a method for two people to coordinate and get public random bits from the web. The method can't assume that two people going to a website simultaneously will see identical content or be able to synchronize perfectly.

Of course, it should be fast and fun.