Among the Greats

Making grown men go "Yes, Yes, Yes" (Si Da Tak), 360 degree twirl and shooting with his back to the basket when needed, MJ, His Airness (Hello Houston):

I typically identify and cherish talent of the sort that is shown and seen at a level with a hint that if pushed and challenged, the level can be raised. And raised. A la Bruce Lee:

Finally, the inimitable subject of this drawing performance:

(For All)s

At a Dagstuhl meeting sometime ago, two communities of researchers came together: property testing, and streaming algorithms. As all theoreticians, both groups wanted theorems that hold for all inputs (with some property). The difference was, streaming algorithms research proposed theorems for particular problems such as estimating L_1 norms, while property testing research, perhaps because of the complexity-theoretic flavor, sought theorems that hold for all problems in certain class., eg, all monotone graph properties. Sudipto Guha, Piotr Indyk and others used this observation to incite streaming research to seek more general techniques and results that hold for classes of problems (all distances with certain properties, say). There is some fledgling progress on this. Guha, Indyk and McGregor have results showing general lower bounds on classes of distances (COLT 07?) and I liked Trithapura's recent talk where he reduces a bunch of problems to one (range efficient distinct element estimation) thereby relating them to each other. More general streaming results will be cool.

The City Tugs

Couples walk the city of NY in chunks of blocks. Sometimes in close embrace as in the early stages of the romance; sometimes in the comfort of romance's midlife, separated by few paces, forward or to the sides, each somewhat lost in their own thoughts; and yet other times, in dying stages, in a tiff with one walking off from the other.

No matter what, the city massages their walks through its traffic lights.

The early romancers get to linger at the traffic lights and savor; the midlife romancers draw a nice surprise when one manages to cross the street and the other is caught behind by the light or the line of speeding cars, and they sheepishly reconnect, hold hands and walk on; the ones in tiff get a respite when the leader is caught by the light and forced to stop, the lagger catches on, and they stand next to each other in huff and get another chance to reconsider, perhaps make up, perhaps rejuvenate.

Drama everyday on street corners of the city.

Networking and Databases

To algorithmii, networking and databases are two application areas, and many of us make an effort to connect with those communities and face the challenges. Curiously, the networking and databases communities reach out to each other too, have taken fledgling steps, and face their own challenges.

There are two conferences: NetDB and MineNet.

• NetDB is held this year with Usenix at Cambridge, MA on Apr 10th, with PC chairs Brian Cooper and Nick Feamster putting together a solid program including Sam Madden's keynote talk on DB issues in sensor networks.
• MineNet will be held this year in San Diego on June 12, jointly with FCRC. Shubho Sen and Sambit Sahu put together a good program last year, and are heading the process this year too.
  

It is interesting to see the conversation between these communities, even as database researchers seek general principles and data management issues that cuts across multiple applications and the networking researchers seek methods that are effective in their context, which is highly dynamic and complex, interesting in its own right.

Call to Advisors

What can (should) advisors do when their students travel to give talks, in particular, interview talks? Check slides, practice the talk, time and tune it. Make sure there is at least one or two nice proofs and proof ideas (these days I hear talks that state the main theorem but don't tell me even an idea of how to prove them, what is novel). Make sure it fits the audience which is often broader than a theory-group in one's dept. Make the student do the homework. When a student performs poorly during an interview visit, it says something about their advisor.

A quote from a different time/place --- Kahlil Gibran in the other Crime and Punishment --- apologies for the preach.

And when one of you falls down he falls for those behind him,
a caution against the stumbling stone.
Ay, and he falls for those ahead of him, who though faster and surer of foot,
yet removed not the stumbling stone.

Catching up

I spent a rare weekend with friends, some from a long time ago. Curiously, these conversations made light detour to discuss our growing ages and the universal allure of the youth. Some day, we will age over it!

Aged and timed: I watched a play Burn This. It was a story of loss and love set in mid 80's in NY and was wrapped in gay life, dealing with the loss of friends, and the coming to terms of a playwright who essentially ends up writing the story of the play we watch --- of his dancer-lover discovering the MAN in another in her life and transforming it into her dance. The screenplay got sharper and the acting more natural as the play progressed (aged?).

In a dramatic moment as Jon Feldman and I brainstormed mechanism design at a white board last week staring at a plot trending the wrong way, he said, "Time, unfortunately, goes forward."

ps: Alan Lightman has a lightweight, distracting read of a book called Einstein's Dreams in which he sketches a few stories of what if time moved at different speeds at different places on earth, at different heights, or went backwards, or whatever.

March Madness

A few days ago, I could bare my arms in a T-shirt, even late nite, for example, on March 14th circa 10 PM, shortly after the shootings on Bleecker Street (NY Post called it Slay Rampage in the Village and followed up with the darkness, and NYT followed up on its front page (bottom right) article with a reflective In Heart of Village, 4 Lives Intersect in a Chain of Violence ).

Today, however, there is coarse snow on the ground and NY is going through a typical day after the snow. After a foot or so of snow, there is slush on the street corners and heaped snow mini-mountains on the sidewalks. Wearing boots or otherwise, people criss-cross, finding safe spots to step on and in a penguin-like stance, they make and follow pathways and hop over the puddles. Cabs speed along cleaned avenues, but lurk, slide sidways and move in a crouch down village streets. It is a theatrical day, with snowblowers in the city streets invoking the distant sound of lawnmovers on a Saturday elsewhere. Men scrap the ice off and make a few bucks, and hot pizza slices keep people warm.

Sums, Squares and Somethings

Partition {1,2,..,16} into 2 sets such that the sum of the numbers in one set equals that in the other, and likewise for sum of squares and sum of cubes.

Past few days in NYC

Sponsored search algorithms

These days I work in algorithms for sponsored search auctions, and there is a slow pipeline of publications emerging. Jon Feldman, a NYer (notwithstanding his vestigial affection for Red Sox), has been giving talks on these algorithmic issues recently at Yale and MIT. Cliff Stein gave a talk at Bertinoro. I am looking forward to giving a talk at MAPSP 2007 organized by Kirk Pruhs in Istanbul. New area, results, talks, pictures and looks!

NYAS

NY Academy of Sciences has an article interviewing Corinna Cortes (SVM fame, BellHead, CoI fame at AT&T and now heads Google Research in NY). She gave a talk on algorithmic challenges at Google at IBM/Columbia/NYU theory day last spring and will give related talks elsewhere like SDM 2007 and WEA 2007. The talk has nice technical pointers on problems to think about, within the context of an internet search engine/sofware company.

Research and Cafes

Those who drink decafs can only churn out lemmas, not theorems. To be a true churning machine of theorems, you have to consume coffees.

Nearly every research result I have had in Italy has come from being in the proximity of Cafe Salza in Pisa, an institution from late 1800's. I seem to take a table there for an afternoon and order every pastry on display. From my first visit there, Paolo Ferragina and I published multimethod dispatching algorithms in STOC 99; later, the 2d string indexing in PODS 01; from a visit two years ago, we got the succinct tree encoding result in FOCS 05; and finally, during my visit there last summer, Gianni Franceschini and I solved the suffix selection problem to be presented in STOC 07. I hear that the famous Salza has changed hands and the new owners are french. Sigh.

DyDAn, DyDAn Research Blog

DIMACS has been and will be a good resource for theoretical computer scientists. Independently, a DIMAS-esque, new operation has begun at Rutgers, called DyDAn (Center for Dynamic Data Analysis). Fred Roberts will be the Director, and there will be collaboration between theoretical CS/Stats/Optimization and others. There is a blog in its natal state to discuss mathematical/algorithmic research issues related to DyDAn research.

Hiring.

A joint work of Broder, Kirsch, Kumar, Mitzenmacher, Upfal and Vassilvitskii analyzes the process of hiring candidates above the mean or the median (rather than the min) of employees, in some quality metric. It has been a pet puzzle of mine for some time, it is nice to see some analysis.

Looking back, ahead and willing things

Perhaps I wanted to will Spring in, so I decided to spend a few hours going over things from the very past and (re)filing them. It is sad, fun and everything inbetween to see the past, and wish one could straighten the torts and twists, somehow make amends or just redo, undo. Instead, one just looks ahead and works in the past. The city of Pisa apparently has a rule that no building may lean more than the tower.

While cleaning up, the maniacal collector of print clips that I am, I came across:

• Okayo, a member of Kisii tribe in Kenya and a NY Marathon winner, says she began running at age 13, intrigued by her father, Ibrahim, who chased girafffes through the forests near their village, Masaba. Thank you NYT.
  
• Food served to children in schools is a topic that goes across cultures. "khichdi has failed to appeal to the children" says the official in India. "Serving Khichdi evey day puts children off. When even we can not eat the food for long, how can the children be expected to eat it daily?", asked a teacher. So, "From next year, hot, steaming idlis, dosas and uttapams will be served to primary school children." Recipes here. :)
  

Life of Pi describes an improbable South Indian meal that Pi dreams of, stranded on a lifeboat with a Royal Bengal Tiger; of course, idlis figure in the meal.

ACM EC 2007

ACM Conf on Electronic Commerce (part of FCRC) has published the list of accepted papers. Just eyeballing it, serious presence of theory folks there..