Friday, November 30, 2007


After a long intense week of excel-ing, I went for a walk to the east side. Such a walk on a friday night in NY means you get high secondhand, hear 10's of different languages, pass people in pairs or groups, fighting or just making up or out, and it is difficult not to connect with a certain music that is the city. NY is seeing the emergence of female DJs who are commanding the dancefloor (with their vinyl spin) and the psyche of clubgoers (with their style). Away from Manhattan, the boroughs are decking their bicycles with powerful sound systems (5k watt of woofers, amps and all else), and the Trinidadian and Guyanese bob their heads and cruise the streets. More photos here.

Bob Tarjan is 60

Friday May 9, 2008: Workshop in honor of Tarjan's 60th birthday at Princeton, NJ, organized by Adam Buchsbaum, Valerie King and Danny Sleator. In many ways, these events remind us of maturing of Computer Science itself, CS being not that much older than its pioneers like Bob Tarjan.

Researchers are going to remember and remind others of his many contributions, so I will say the following \epsilon, somewhat from the left field.

I remember his slim volume on Data Structures, a gem, that in many ways continues to be my inspiration, in particular, in succinct, clear technical writing. In basketball parlance, it is swish, nothing but the net, when it comes to getting to the beauty of the main ideas and doing just enough mathematics to prove the main elements. There are details of course, they can be worked out, let us not floor and ceiling all x's or keep the constants around, just hide them in the all-engulfing O and be elegant.

Sunday, November 25, 2007

When abuse prevails

This is definitely not CS, but I need to end the day of blogging with something silly. Here are three videos:
  • machines abuse machines (the cyborgs shoot shotguns and abuse trucks, skip to 3:45 in the video),
  • animals abuse animals (discovery channel does an animated series that is awful, I got this reference from a fellow CS researcher when I discussed the m/c abuse m/c theme), and
  • men abuse men (Bollywood in ridiculous action, I got this reference from a fellow traveler at the Mumbai airport in response to the m/c abuse m/c theme).


New trend in Coffee

I think this is a CS-related post, or may be, it is just research-related. Coffee craze has worked though the phase of novel beans, their terroir, then fresh-roasted ones, and now it is the Clover machine. Uses vacuum tech, brews single cup individually and has just started a market all of its own with $3.50 - $6 - $9 for a cup. In NY, go to Cafe Grumpy.

How cities move

Mumbai is a NY-esque city (or vice-versa), and seems to be obsessing about how to upgrade its fleet of 45k or so cabs. From the staid black-and-yellow cabs of the 70s, they want to leap to cool cabs with GPS, A/C and electronic meters that spew out receipt printouts, for the 00's and beyond. They look to Singapore as a model for upgraded taxi service. I hope local madness mixes in and they get efficient cabs, but with an attitude. NY has just upgraded to cabs with GPS, map and TV, and there are bunch of ongoing projects to rework the cab design; however, no changes to the attitude are currently planned.

Emerging Research Worlds

Economists talk about the emerging worlds of China, India, Brazil and others with rapidly strengthening economies. China is running hot with manufacturing, India is coding itself into IT, and Brazil (yes, God must be Brazilian) just discovered oil in its Tupi fields to add to its bounty that is already paying off. Some of the already-emerged economies are steaming (euro hits new highs weekly). Let us for a moment forget potential recession in US and what can only be called the submerged world of African Economy, and go with the rosy picture.

What I wonder is how will this affect the research world.

These emerging economies will invest in Research. The question is, what form will this investment take? My guess is, these countries will do what they typically do: set up a few "centers", get a few "top researchers", pile money on them, and hope this trickles down to form a research community. I have no idea if this approach has ever worked for any country. I mean, the "top researchers" are really the top ones, and they do their best, generate bunch of postdocs, students, support high quality visitors, and form joint programs with other international research centers. Will all that ultimately generate a research program as vibrant as the one in US?

Theory-CS Blog Aggregator

It may not be as cool as The Terminator, but here is an Aggregator of theory-related blogs (will be useful for people too lazy to aggregate RSS feeds for themselves). In a single scroll, you can tell, we are interested in a whole bunch of different things. Some features are:
  • automatically import comments, see/hide them or add comments,
  • automatic resolution of DBLP/homepages of participants,
  • filtering by category (in addition to others, may be we should have a special "aggregator" label?)
  • automatic link to citeseer for papers mentioned (planned).
If you need new features, contact

What we export

In a story by Hurakami called "The Year of Sphagetti" (New Yorker abstract, a copy of the story; just buy the book and enjoy the stories), the narrator spends the year 1971 by himself in a small apartment cooking sphagetti of different sorts and engulfing himself, his books, clothes and records in its smell. The story ends with, "Can you imagine how astonished the Italians would be if they knew that what they were exporting in 1971 was really loneliness?

What do we export as Researchers? Mihai Patrascu articulated something in a different context that applies here: (paraphrasing) he said we export our lifestyle. In the best light, it involves being super-committed to our research, staying up nights and days in pursuit when an idea attacks, decent middle-class earning, travels world over and having local "friends/hosts", limited freedom from the vagrancies of the "boss/society/economics", and finally, an evolving notion of self and perhaps truth. Almost every profession (eg., being a journalist, an artist, whatever) exports its lifestyle, and it is worthwhile to knows one's export, in good and in bad lights.

Saturday, November 17, 2007

Le Balloon Rouge

Fall days mean walk in the city with swirling leaves, flying hair, humans in scarves and coats, and children walking with their heads down, eyes averted. Some days I feel like an adult or world thrusts that upon me, and then there are days I feel like a boy or the world yanks the boy out of me. Today, I found a red balloon bobbing on the street, I picked it up and let it go, it flew, but followed me for an avenue block, so, I figured, like Lamorisse's hero, that it wants to with me, and I walked it home. Walking down the city blocks is a danger in itself some will tell you, walking with a red balloon in hand is even more so; I was glad when I managed to get home and shut the door behind safely. The red balloon, my treasure, is still holding its breath and hovering over me. Here is the media on the 1956 movie and its accidental enactment today.

A Past

This is the season of conference deadlines (STOC/SIGMOD/SIGMETRICS and many others), holidays, and the surge and ebb of traditions. In a break from a tradition, I have put myself outside the process of conferences (and embraced the holidays), and am now willing myself towards the end of the year. I will be away in India for a week, and on reflecting, found myself thinking of my alma mater, IIT Kharagpur (the least known of the IITs in Theory CS---there is always a linear combination in which one leads---but it is a gem of course). The CS dept is celebrating its 25 years of existence this winter. I remembered the last time I visited the institute, it was 10 years ago, and googling yielded this blurb by Devdatt Dubhashi. This and other pasts often intrude in strange ways: watching a movie in a theater far away from Kharagpur, if someone yells "Tarapodo!", the legend lives on; in a party in the village, I see Umesh and remember his fantastic lecture at Kharagapur in 97.

Wednesday, November 14, 2007

Hot off email

I really shouldn't publicize getting an email with the Call For Papers for a new journal: Rejecta Mathematica. As the website says:
Rejecta Mathematica is a new, open access, online journal that publishes only papers that have been rejected from peer-reviewed journals (or conferences with comparable review standards) in the mathematical sciences.
Further, the website clarifies that the journal is interested in forms of "mapping the blind alleys of science, reinventing the wheel, applications of cold fusion, misunderstood genius" etc. Enjoy!

Btw, you can imagine what an email invitation would say: " light of your reputation in the research community, we would like to extend a specific invitation to you to contribute a paper..." :) The website above counsels authors whose submissions to this journal get rejected!

ps: Mike Wakin, Chris Rozell, Mark Davenport and Jason Laska are involved. All are signal processors.

Saturday, November 10, 2007


I went to IKEA, an European equivalent of McDonalds (yes, $0.99 cheesburgers, $9.99 lava lamps). I know retailing is a difficult business and I not knocking their hard work. But retailing food is a harder business. I am mainly talking about the Salmon, the poor specimen that was born in captivity, lived within a large mesh I am sure, and eventually made its way, via the steam route, to one's plate: the piece was soggy, served on a plate that was poorly washed, and accompanied by soggier vegetables; the patrons look at the plate without appetite, use the fork to cut it to pieces, move it around and play hockey, all the while talking, eating fries and drinking. I felt the need to rush home, paint a large, healthy, lively Salmon, and hang it somewhere in homage.

Sponsored search market index

Micah Adler visited and it helped me recall shared experiences working on problems in a different world and context (parallel algorithms, scheduling problems, and a rope burning puzzle from long ago). Of course both of us had a life within a different context now, and so, we discussed a different set of problems.

In particular, I got a chance to pose a problem I think of as a big picture question of some larger relevance (I am not an expert on markets, and this may not be such an interesting/challenging problem, but those disclaimers aside, in any case, here it is): Much like indices for tracking the market for various materials/stocks, can we design one for tracking the market of sponsored search ads? Definitions aside, the engineering part of collecting relevant data may be fun too.

ps: Mitt Romney: I Love Data.

Friday, November 09, 2007

Brooklyn Blues

What will move me several blocks away from my aptment, over the river and into Brooklyn? The Blues, beats and Jazz. Fridays and Saturdays, free and sweet at BAM, to be bottled at the moment, at the source, and sipped right then and later. Today, Chanda Rule performed and freed the many who had gathered there after the long week.

Wednesday, November 07, 2007


I should have listened to Suresh and watched the movie long time ago. Instead, I watched it two days ago. There is the story of the NY grandmothers who would sit at their window and watch their 10 yr old grandson walk down the block, and the adventurous ones, let their grandson walk down the avenue block! Well, those NY grandmothers would have found it easy to track me as I walked all of 0.5 street blocks from my aptment to the IFC theater to watch it late night, the movie by now almost a midnight cult affair. The theater had 2 men fiddling with pen and paper, 2 couples (one hetero), an oldman with bulging backpack and beard flowing down to trip him when he walked, and me. I swear someone had a Mac in the theater, the movie was mainly a sublime homage to Apple. It was encouraging to see grown men (and 1 grown woman) speak passionately about fonts. The movie (NY Times Review gets it right: "you’re guaranteed to spend the next few days scanning the world for Helvetica like a child on a cross-country car trip playing I Spy.") was visually pleasing, moving from New to Old amsterdam/world, and I returned home, vowing to experiment with fonts. Save me.

Math in NYer

Finally, two of my favorites collide. NYer has a fun writeup on FireFighters Theorem, and quotes the work of Barry Cipra. Enjoy!

Sunday, November 04, 2007

Parallel Algorithms

Some of us worked on parallel algorithms theory a long time ago, and many others on parallel systems. Parallel computing theory continues to remain in the backdrop, providing a hum to the motor ride that Theory of Computing is on; the (mesh, hypercube, connection) machines have disappeared, occupying real estate somewhere; people reinvented themselves, some went on to wireless networking, others to internet algorithms and beyond; wonder what happened to the software (BSP-based or otherwise).

The word on the street is that there is a revival, with the trend of multi-core processors. I hear that compilers for these systems are a rave. Will we see beautiful parallel algorithmics again, with list ranking, Euler Tour techniques and randomized matching?

Saturday, November 03, 2007

Guest blog by a summer NYer

Guest blog by the NYer, Amit Chakrabarti: he dalayed a little, I dallied a lot, and this post appears now, several months after his visit, and the summer, alas, already gone.

A visit to New York somehow seems like a return home to this Bangalorean, despite the fact that until summer 2007, he had never lived there. Thanks to The Braided Algorithmus, that has now changed. It was a real pleasure living in midtown Manhattan during July 2007 and interacting with the sea of talent at Google NYC.

New York somehow manages to show you something fascinating every day. On this Fourth of July, the Sight of the Day was not the fireworks on the East River (quite spectacular, thank you), but this rather prominent advertisement of some of my host's research (See the photo).

Formal Call for Napkin, Notes and Other Math Scribblings

Napkins are special: they are easily available in restaurants, cafes, and bars. While regular folks use them to make lists and progress on chores or get telephone numbers and progress human race, researchers use them to do math and progress knowledge. Somewhere between chores, race and knowledge, comes entertainment: there are napkin sketches, napkin writing, napkin art, etc.

I am very excited about math we do in scribbles, on pieces of paper we can easily find: napkins, receipts, business cards, or whatever.

So, here is a formal call for my pet project: please photograph or scan such gems, and mail ( them to me, with your story, if you are willing to share, and I will collect them and create an online exhibition of how in these driblets, we force math and methods to progress.

The Week Ends

Some weeks have setbacks, stories of friends' relationships that struggle at the threshold, and multiple murders. About setbacks, all I can say is a few weeks before a conference deadline, we, the researchers, sift through the pile of papers and sometimes a gem emerges, other times one gets a paper cut. I can speak about the murders more. On Friday, I chose to watch the movie Before the Devil Knows You are Dead, a tale of murders, more or less projected on to family members, very disturbing! Then today, in a spur, I went to watch a lowkey adaptation (Wicked Tavern Tales; Welcome to Hell's Hound... where the Beer Flows Freely and the Tales are Tall... Or Are They? Written by Greg Oliver Bodine; Directed by Amber Estes) of three tales due to Edgar Allan Poe, of cats, wine connoisseurs and men with cat-like eyes, all murdered, bricked off into cellars, plaster walls or simply stifled, but their sounds exact revenge.