Arts during the Break

I like plays, performed in small spaces, with bare chairs for the audience, one, two, at most three rows of them, hair breadth away from the actors. One place you can enjoy this experience is at the Manhattan Source Theater where I recently watched 7 very short plays due to Joshua James called the Best Shot. My favorite was Three Times, a short piece about a Mathematician facing a breakup.

I also like contemporary dances, a half a century of fantastic American contribution to dance via Alvin Ailey or Merce Cunningham and many others. Recently I got to watch 60 yr celebrations of the Limon dance company at the Joyce Theater where they did a program (B) of their early performances from 40's. What a treat.

City Living

Living in a city has its own daily language.

• You may use a cart to shop in a store for food, but you don't push the cart past the cashier because the full bags don't go into the cart and out to the car. Instead you lug the food bags home along the grid.
  
• The NY taxi riders need a "Pull and Slide" note on the door handle of new *minivan* taxis on the street. They are used to the "Grab and Yank" to get into an oldfashioned taxi, and are unused to minivans, and minivan taxis.
  
• NY Times had a collection of citydweller haikus a few years ago, and one went something like this: Our eyes met/He stood up and offered/his seat deep orange and warm. Most citydwellers will know that this tryst happened on the B/D/F subway.
  
• Finally, as Seinfeld watchers would know and this is suitable for discussion coming out of a Thanksgiving break, you don't go to the airport to pick up visitors or see them off. You let them navigate the buses, taxis, bridges and the tolls.
  

Wiki

There is a wiki page for algorithmus Erik Demaine, real Lenna, fictional yoda, inimitable David Lynch and the Onion's parody. That is the kind of sentence you can put together when talking about wikis.

Being Indian

Most days I live in a world --- subways, streets, shops --- where people look at Indians in a broad stroke, a swarm from the billion left behind. Sometimes people drill down a little further and separate South from the North Indians or the Indians from Trinidad or in one case, the Indian Brahmin from others. The Nuanced speak of Idlis and Dosas, being distinct from the Tandoori's. Still it is going to be a while before people appreciate the nuances of Bengali vs Punjabi teas (to be found on Houston street in the lower east side where taxis to go to sigh and their drives sip, yes!). Taking the nuance to the limit, I remember a dinner time conversation at MSRI: Suresh and I spoke in staccato code, sitting among strangers, about IIT Kanpur that many in our research community have heard about and Suresh's alma mater, and the IIT at Kharagpur, my alma mater, less known, but (more and longer) storied. Believe me, most IITians can look at others and can tell which IIT trained, groomed and ultimately graduated them, and most are convinced their IIT is the best. I come from the one in the land of leisurely teas, long discourses, Satyajit Ray and you can tell us apart from others. :)

Range Medians

Vitaliy of Google gave me the following nice algorithmic "puzzle" (admittedly via a proxy, and with my own twist).

Input: An array A[1,n] and a set of k possibly intersecting intervals [i,j] \in [1,n]. Output: For each interval [i,j], output median(A[i],A[i+1],...,A[j]). How fast can this problem be solved in the comparison model?

Spoiler: I can do this in O((n+k)polylog (n)). Anyone with O((n+k) log n) or even O(n+k) if that is possible?

MapReduce

I used to work in parallel (PRAM) algorithms more than a decade ago, and have always been curious how parallelism will work out for real. Now, we have some positive developments. Google for example uses systems such as Sawzall and MapReduce to process large amount of data using 1000's of parallel, loosely synchronized machines. A bunch of us have spent time trying to abstract a computational model for Sawzall and MapReduce. We have made a start with what we call the MUD model. More remains to be done, in particular, with a bounded number of rounds and a large number of "keys". Any new model or algorithmic insight is likely to be useful since these systems are widely used in practice.

Organizing a Workshop

A type of workshops I like explore new connections between different areas of research. It is difficult to organize such workshops: it requires the ability to bring together top people in more than one area of research to collasce around some central problems and techniques. So, I am grateful when someone does organize one of these workshops. Petros Drineas, Michael Mahoney and others organized one such workshop a few months ago, bringing together people from Numerical Analysis and its applications, and algorithmii working on linear algebraic and matrix problems. I think these two (three, four, more?) communities should really talk, and it was good to see a start made. SIAM News has an article on this workshop in their October 06 issue.

Air Travel

I watched the recycled sequel to the old, old classic Airplane! this AM. In real life, pilots sometimes have to communicate things beyond the usual to the passengers and the things I have heard:

"Electrons are running around in the computer and not listening to us, so as soon as the technicians fix that, we will on our way". -- This took several hours even as my plane was parked off the runway in some airport in Germany.

"We have just got our paperwork, and we can now fly". -- This was after several minutes of waiting at the gates with closed doors without any announcement. I hate paperwork and can not imagine it will follow me on to a plane too.

Here are some funnies, mostly antics by Southwest Airlines flight attendants.

Brooklyn Pizza

I am in Mountain View (MTV) for the week, dealing with the weather (sigh), taxi drivers (sigh-er) and lack of coffee (sigh-est). The weather is grey whenever I am here; nearly every time I have been here this year, I have drawn newbie taxidrivers who ask *me* for directions and highway exits (to get to downtown MTV!); coffee, well, I am not stumbling out of my bed to grab the 50--70 cents coffee in the street corner. Instead, I get a ride to a coffee shop with strange music, a laptop heaven, and where are the little kids and old people in these places?

To remind myself there is a world out there, I thought about Brooklyn. More precisely, Brooklyn Pizza. Think Grimaldi's, Di Fara's. Mouth-watering. Domino's has introduced their Brooklyn Style Pizza. NY times article on what locals think about it has a nice photo or two.

MST

Gianni Franceschini, my coauthor in the future, was trying to fit a model to the sporadic emails from me at nonstandard times and asked if there is a timezone called MST, Muthu's Standard Time. In Italy, there is the academic quarter (in Sweden, akademisk kvart): things start a leisurely 15 min after the scheduled hour. For me, time gets measured in different units, time it takes to get to work, via consumables: the half a cup of coffee to get to work from my place these days, the one cup it used to take a few weeks ago, and the cup of coffee, breakfast of bagels and the Times it took to get to work for more than a decade before that.

NY's Sanest

It is impossible to escape the Halloween day parade in NY city with the guy in a shower stall costume, the man dressed as Princess Leia with R2D2 or the usual grotesque, burlesque, politicsque, whatever. But being a resident of the city means you focus on the day after. But the NY's Finest (they levy fine?) knows not only how to control the crowd, but also, how to wrap it up. Instantly as the tail of the parade passed my street, they moved in, removed the barricades, stacked them on the side, and followed the parade wrapping it all up like dominos. Shortly after that, the NY's Sanest came in sanitary trucks, sucking the trash all in, and this AM, the streets looked just as dirty as usual, no more. Few moments in life you are glad to pay the taxes. Small collection of pictures at NYC Photobloggers, in paritcular here.

Media and Compressed Sensing

Among the cult of compressed sensing researchers, or the subcult of algorithmii thereof, it is news that the media has picked up on compressed sensing. See the Economist article. Also, Graham points us all to the talk in video by Richard Baranuik of Rice Univ. on Compressed Sensing.