my slice of pizza

NYCE 2009

2009-11-10T23:30:00.000-08:00

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

2009-11-10T16:03:00.000-08:00

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

2009-11-10T14:09:00.001-08:00

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

2009-11-08T20:56:00.000-08:00

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

Let us call this a tweet

2009-10-31T16:51:00.000-07:00

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

2009-10-31T11:20:00.000-07:00

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

2009-10-23T16:17:00.001-07:00

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

2009-10-23T11:51:00.000-07:00

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

2009-10-19T08:41:00.001-07:00

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

2009-10-18T11:06:00.000-07:00

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

2009-10-18T09:53:00.001-07:00

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

2009-10-14T02:34:00.000-07:00

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

2009-10-11T14:23:00.001-07:00

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

2009-10-04T16:44:00.000-07:00

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

2009-10-01T18:24:00.001-07:00

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.

NYCE 2: CS and Econ

2009-09-28T05:07:00.000-07:00

The Second Annual New York Computer Science and Economics Day (NYCE 2009) will be on November 9th at the NY Academy of Sciences, and organized by Robert Kleinberg and Eva Tardos. They are soliciting speakers for the rump session, deadline is Oct 12. Tentative agenda: Michael Kearns (9 AM), Shahar Dobzinski (10 AM), Jennifer Rexford (11:30 AM), Rump Session (2:30 PM) and Larry Blume (4 PM).

Cross Product Research

2009-09-27T10:30:00.001-07:00

I remember Hal's talk about "combinatorial innovation", that is, once you have certain basic ingredients for innovation, people find ways to combine them and generate an explosion of ideas and products in a very short time. That is the good part. I want to talk about an annoyance that is similar in spirit that I often confront.

I refer to Cross Product Research, that is, research that is the result of mixing ingredients. The formula is (recent hot topic) X (known problem formulations) X (favorite math tools and methods) X (some data, experiments, and good writing) \rightarrow (Paper Submission). I may have left out certain adjectives and some dimensions may be superfluous, but this formula begets longer titles, more papers and destroys trees.

Algorithm Aware

2009-09-26T08:44:00.000-07:00

If some researcher asks you, what is your area of research, and you say Algorithms, most times they look at you without comprehension. So, in a discussion, the crowd wondered, what is Algorithms Research? I mean, every researcher -- in CS and beyond -- thinks they design Algorithms, so poetically:

An Algorithm is an Algorithm,
Databasers do Algorithms, Networkers do Algorithms,
Visioners do Algorithms, So do Machine Learners I suppose.
But a SODA Algorithm is an Algorithm and was always an Algorithm.

So the crowd meandered with hypotheses of what is Algorithms Research and Sudipto Guha supplied, "You know you do Algorithms Research when you are aware." (paraphrased)

Travel to the Bay Area

2009-09-20T09:01:00.000-07:00

Typically when I travel to the Bay Area, I feel like a horse with blinders, my sights focused on meetings and what needs to be accomplished. Last week, I looked around more than usual and had some interesting conversations:

Moshe Babaioff: Structure of subdominant strategies and their usefulness.
Aranyak Mehta: That is so paperware!
Ashish Goel: What will be an open architecture for auction platforms? (like OpenFlow is for IP routing).
Lars Backstrom: Say people vote only when their votes matter. Dynamics in small committees.
Sivakumar: What is the rate of growth of information consumption?
Ravi Kumar: PTAS for Jacard median. Interesting stuff. Ravi has been giving plenary talks, we need to see the slides, we need to see the slides....
Jasson Schrock: new YouTube skins.
Kunal Talwar: Is budget-limited auction design a foundational research problem of interest?

And many others. In some cases, I am still continuing the conversations in my head. :)

Friday Evening Play

2009-09-19T10:00:00.000-07:00

It was a long week, with situations that force a definition upon you and you have to remember to bust out. For friday evening, I went to Brooklyn which is forgiving of tired researchers and veering artists. Far from the prying Manhattan, at the dilapidated but charming Harvey Theater on the left, I watched Actress Juliette Binoche and Choreographer Akram Khan from very close, as they tried out each others' trades some.

Juliette is not a graceful dancer, but she has a great presence reminiscent of her film roles; Akram excels when he reaches back to his boyhood and acts out 2 roles, but the plot is from the left field. All this storytelling takes away from the joy of the dance, but like seasoned researchers who can do with 6 what others do in 10 filled camera-ready pages, the artists kept it short and did not grate. Dinner at Stonehome, crispy Chicken and warm Chocolate Cake, got me to the weekend.

Visit to NYU Stern

2009-09-18T20:49:00.000-07:00

I visited NYU Stern to give a talk. Putting disparate people together pays off. I met with faculty from OR, Data Mining, Stats, Econ, and Social and behavior sciences working in a single division. So, during the day, I discussed many different topics and saw how much the faculty had learned from each other being colleagues who make hiring, teaching, mentoring and funding decisions together, with social lunches too.

Vasant Dhar: Transparency and speed of exchanges auctions in ARCA, SEC's REG NMS spec for getting the best price across all the exchanges, 30 ms that each platform gives itself to fill an order before it accesses other exchanges and the resulting dynamics.
Foster Provost: Identifying people with brand affinity using friends in social networks and using the user-target feature in ad exchanges to market to such users across web properties. Level of trust among ad networks, brand advertisers, exchanges etc.
Anindya Ghose: Confs that bring marketing and CS folks together such as CIST09. Bidders in ad auctions seems to care about competitors: at what granularity should they care (aggregate or individual)?
Arun: A practical economics puzzle: the medium coffee costs more per ounce than small or large coffee at the Stern Cafeteria, why? We also talked about teaching math to Business majors, and the cute Manga Guide to Calculus. He is a clever man: during my talk on sponsored search, I spoke about bananas, and he asked, "Organic or Sponsored"?
Alex Tuzhilin: He was an expert witness on a click fraud analysis case, and his report is public. Click report audit and verification is sometimes outsourced to third party companies such as ClickForensics. ACM conf on Recommender Systems will be in NY. Exactly how much did NetFlix gain with a paltry $1M competition? :)
Lunch at Lupa, Dinner at Tabla. oolala.
Sonny. Understanding organizational and human capital in services. Scrapping resumes from LinkedIn. How to infer hierarchies from communications among people.
Yannis Bakos. Classic Econ discussions. Tradeoff between finding better matches vs cost of search, eg in the "house around the lake" model (on a circle, rather than on a line as in Hot dog vendors model). Bundling and what happens when marginal cost tends to zero. During my talk, Yannis asked how to bundle ads, something in general worth thinking about.
Sinan Aral: Information flow in organizations. He asked what is on my mind these days, and I answered: I would like to design a reservations/futures marketplace for ads.
Students: I met Nikolay, Jing, Eyal, Xiaohan, Shawn, Bebe, Ning, and others. I dont see their homepages.
Post-Talk: Over wine and cheese, Panos, a thoughtful blogger, quickly converged on the second part of a proof I left out in my talk. Btw, check out his citation tracker.
Dinner: All dinner conversations should be so scintillating! Roy Radner asked two questions: Why should Economists care about Internet Ads? What is the total value of Internet Ads to the society? I can only answer these over dinner. :) Foster Provost, clearly very deep into thinking about Internet Ads, challenged me about the standard notion that Internet has made ads measurable: in particular, if you ignore direct marketing, there are more offline measures and measurements of brands ads than online.

Coda: It is amazing how much Hal Varian populates conversations even 3000+ miles away.

Labs vs Academia Contd

2009-09-13T07:54:00.000-07:00

I enjoyed the discussion on labs vs academia at Boyd, Michael, Katz and Mihai, and comments therein. I more easily understand Mihai's take than say Boyd's, perhaps because I am closer to Mihai in research interests and geographic preference. An interesting mental exercise is to ask, have truly fundamental results come from Academia (more than Labs) and have truly great applied algorithmic results come from Corporate Labs (more than Academia)? I would reckon world does not divide nicely that way. It will also be great to get a balanced view on grants. Is it an all consuming monster of a process or is there a way to be selective and reap the benefits?

Timing

2009-09-12T11:42:00.000-07:00

A friend asked what I seek. Such a question is usually an opportunity to make something of that moment in the conversation, with a few words you can spin it to wild place, veer towards an adventure when the bar closes and the music turns to the Blues or simply subdue the moment, get the check and take taxis home. My answer is this: I have always wanted to live in the moment, not bear the burden of the past or the future, just be. That is difficult.

I was reminded of us when I read this NY Times piece on a Tajik storeroom worker who finds fame singing Bollywood songs with uncanny precision. "Mr. Allaberiyev’s family understood that he had a gift; by the age of 7 or 8, he could commit songs to memory and repeat them with eerie accuracy, after watching a movie twice. But he was born at the wrong time, or in the wrong place. By his early teens, he was picking cotton for a pittance in pay." Having all your belongings in a satchel, asking the reporters for replacement teeth and carrying around the red backstage pass with the words "artist" like people who leave ski passes on their jackets long after their brush with the snow, reminded me of what I seek.

WWW2010

2009-09-09T01:49:00.000-07:00

WWW2010 "is a premier conference on web research" and has an interesting mix of theory, systems, software and practice (yes, the last three are different!). Ashish Goel, Ramakrishnan Srikant and I are helping with the Internet Monetization area, but you will see other theory folks on the various committees. Deadline is Oct 26.

Here is a blog entry by Danah Boyd from Microsoft Research that discusses Corporate Research vs Academia, with a particular point of view. The comments are interesting as well, and surprisingly one-sided.

Back to Art

2009-09-05T15:45:00.002-07:00

One of the conversations at the CS and Econ meeting at Cornell reminded me that I need to post this. Video of a fantastic Artist Kevork Mourad, a visual atist who paints to music. His Gilgamesh rendition is on Youtube and is a treat to watch in person.