Saturday, June 30, 2007

Australian for Beer

In Australia, a pint is 14.37 ounces (not 16) and one can order a Pony, Schooner, Pot or Middy, and not get a horse, ship, or whatever, and you need travel tips for beer glass sizes. Down under, in wilderness or in your office, you have to know how to open non-US beer bottles say with bread, gas nozzle, Elvis doll, keyboard, or other things: here are a 1000 ways.

Thursday, June 28, 2007

Coffee Talk

In a casual conversation at STOC, someone presented the following observation: Theory professors make great department heads. Talk amongst yourselves!

Finishing off a long day

I have long days at work, say 6 AM to 10 PM. One has to finish it off somehow, some may do that with beer and pizza, others with tea and shower, or whatever. Yesterday, I decided to treat myself with the latest in the die hard series, live free or die hard. After several strikeouts, it was good to see a real action movie where modern technology gets a cameo and Bruce Willis, the aging warrior, shows irreverence and to twist the Basketball parlance, puts his body to it. In a fantastic debut, a F35 Joint Strike Fighter designed for STOVL, is sent out by the Marine Corps to take out Bruce Willis driving a truck: the F35 streaks, hovers, and shows its all-axes mauverability, spits missles, destroys the overpasses, shreds the truck (external mounted gun in the F35?), but leaves Bruce Willis in a shape that he can walk to his final shootout. Awesome. On the flip side, the bad guy was terrible, simply not baaad enough, some plot in the background I did not want to understand, and the usual racial, misogynistic and other offensive things.

Sunday, June 24, 2007


Check out the one-day conference on scalability for some truly exciting developments in large scale systems from file systems, data stores to specialized systems such as video streamers and DNS infrastructure. It is an interesting challenge to see what new algorithmic techniques are needed for solving problems in this new world.

Rebranding, albeit briefly

Father Demo square, a triangular wedge (pizza slice) of land in the village, long haven to coffee-drinkers, pizza-eaters, newspaper-readers and plain resters, has reopened after a long renovation. Yesterday, walking around the square after nearly a year, with the frothing new fountain, children running around and the people who were using it as if it had always been there, I was reminded of a moment in a film: an US military airplane flying under some codename (say foxtrot) ends up taking aboard the President of USA who had to abandon his own airplane after some dramatic action sequence, and the pilot of the foxtrot gets on his communication channel and says, "The foxtrot is now Air Force One, I repeat, the foxtrot is now Air Force One". I felt like saying, "NY is now the Eternal City, I repeat, NY is now the Eternal City". Briefly, I hope Rome with its majestic fountains will acquiesce.

Birthday wish

I know someone who spent their ith birthday reading the ith page of every book on their shelf (atleast for a particular i). I can see this breadth-first search leading somewhere over time!

Given time, lot of things become possible. Sometime ago I read a story (by Haruki Murakami) of a woman who works as a waitress in a restaurant and ends up being at work on her 20th birthday. She meets the owner by chance and he proposes to grant her one wish. Much later, she is speaking to the narrator and asks him what his single wish would have been when he was 20. He can't think of any. I have been trying to understand this for some time and this morning, at a corner in washington square park, felt like I connected with an answer. I can think of many (usual or unusual) wishes for my life at this moment, but I can't think of what I would have wished for (besides the obvious answers people suggest) at a certain moment in the past like on my 20th birthday knowing I would have thought hard about the question even at that time and would have tried to come up with an unusual wish!

Hashing with linear probing

In grad school, I spent time studying analyses of various hashing schemes: uniform, double, linear probing, whatever. Alan Siegel (from the school of Knuth) at Courant Institute of Mathematical Sciences where I went to school has several fundamental results on simulating idealized hashing that assume n-wise independence among n variables on real models with limited independence and space tradeoffs. He has a simple overview on his homepage with links to papers.

In STOC 07, there is a very nice result on hashing with linear probing that has been much harder to analyze than the other variants. This result due to Pagh, Pagh and Ruzic shows that 5-wise independence suffices to obtain constant expected time per operation. The analysis (atleast as it appeared in Rasmus's talk) is elegant.

Sunday, June 17, 2007

One's name

One accumulates stories of different sorts over time, some in which we feature and others in which we appear  by proxy. Having a name such as mine means I feature only in near-proxies, with liberal edits applied:
  • Mewtwo, a 6ft 7 in, powerful pokemon character, able to communicate with humans.
  • Moutai, a liquor from China, that I worry may be just associated with middle-aged men.
  • Mutsu apples, or Crispin, moderately sweet.
  • Mutu is a Finnish slang for something you cannot prove but intuitively makes sense (somewhat dubious fit for a theoretician!).
  • Mutu is also a form of shamanism from africa where mutu men are often employed by soccer clubs. What a bad mutu if you lose! Nothing to do with the Romanian soccer star Adrian Mutu, or the inimitable painter Wangechi Mutu.
When I was a boy, I was called The Mutt (sometimes  anglicized to Matthew), that fits me  tight as a glove, much like names one gets in high school fit us, at one time or the other.

Saturday, June 16, 2007

Atlantic Avenue ArtWalk 07

Atlantic Avenue in Brooklyn has become the Boulevard of Boutique shops. Once each year, the shops showcase artists, and we get to walk around and watch some art. Jana Ilkova's photographs to the left, or paintings of Jerome Lagarrigue.


I wish I could do a suresh-sariel-jeff version of STOC and other confs at FCRC, but I tend to have and present fragmented views of the worlds.
  • Avi Wigderson gave an ambitious plenary talk at FCRC, providing an overview of hardness result for MAX 3-SAT and tracing many different lines of research in theory. Much needed talk to showcase the excitement and achievement of theory, but at various parts, even definitions quickly unravel into long conversations, and I think most of the non-theory audience will have to vow to go read the papers or a book; Avi brought all the enthusiasm necessary to make anyone vow to do just that.
  • I gave a talk on suffix selection. Simple problem discussed in this blog earlier. I tried to avoid the mess of suffix trees, periodicity properties and integer manipulation data structures in a talk.
  • Google was a sponsor, and had a booth at the conference. The normally perky Google people who staff the booth and the somber conf crowd interacted via the puzzles.
  • I saw/talked with a lot of Rutgers faculty I normally don't see in the conferences I go to, thanks to the sprawling FCRC: Ricardo, Uli, Barbara. And others that I do typically see: Eric. And the strangely shifted context of students from Rutgers last seen at theory colloquium moving between various confs at FCRC.

Back in NYC

I had to delay the therapeutic moment of return to NY from a string of travels until the weekend, and go through a long day at work on Friday after the red-eye flight. But today, Saturday, was a June day of summer in the city when the Sun breaks through and penetrates the skin, motorcycles slither out, rooftop gardens sprout out and catch one's attention, light is perfect and NYers are out in their usual clothes, each unique in shirt, shorts or shoes. Rain eventually arrived, but one grabs $3 umbrellas that materialize some time after one spots clouds but before the first drop hits the sidewalk, and simply goes on. I discovered a perfectly cooked Spaghetti at Petrarca (NY Mag Review). And online, the wonderful couch of Pierre Charpin, and offline during the walk, lighting by Ingo Maurer.

Sunday, June 10, 2007

An open problem

Pierre Fragniaud described a fun problem. Given G, its augmentation is to add a single (long range) edge to each vertex in G resulting in H. Now consider greedy routing on H where the shortest distances are given by G. The goal is to minimize the time for greedy routing. The authors in SPAA07 paper show an augmentation for arbitrary G such that the greedy routing time is roughly n^{1/3}. The best lower bound seems to be n^{1/\sqrt{\log n}.

Welcome, MM!

I maintain a mental list of people I would like to see blog, and one comes off the list this summer, with his biased coin. Welcome, MM!

Summer Time

In universities, the summer is one of travels, research, cleaning offices, making starts and friends, whatever. In research labs, things get hectic with interns and new hires. Nir Ailon joins Google Research in NY as a new hire. Bunch of interns already settling in (Tasos, Florin, Krzysztof, Smriti, Aparna, Tejas and others), some yet to come (Eddie, David), it is time for me to go to work, immediately after FCRC. Soon I will be looking ahead to the quiet Fall.

Fiction in Bite Size

I read these days much like I paint or do research: in bite sizes, with a clear frame around the time it takes to start, do, and be done. That means short stories for fiction that take a morning moment to read, 1ft X 1ft paintings in coarse brush stokes that each take an evening to do, and well, research, research that gels over travels and showers, written in hungry taps when time can be snatched.

On a recent flight, I had a choice to read: a pile of paper, or a collection of short stories. I chose the later, this being a birthday gift, several days before my birthday. It was a collection of short stories curated by Haruki Murakami called Birthday Stories (a good review with contents; my fave is Lynda Sexson's "Turning"), and it comes with a preface by Murakami describing his birthday moment that got him started on the collection, and a piece written by him tacked on to the dozen or so gems, most of them curiously Murakami-esque, others less so, each comes with a short note from Murakami and his voice carries through the stories and tie them together. Has a lot of bark. Great book to bite into it.

Italian Travel

I went to SIROCCO at Castiglioncello, Italy. The travel gave me the blues:

I asked for Beef and got Chicken, sat squeezed next to big peoples;
My flight left and arrived late without my bags, let me miss many trains;
The machines wouldn't sell me tickets for even the near-empty cars;
My dog left me and I couldn't find a cafe... (just kidding).

It did not matter, I was in Italy, a land of great friends and great food, how can one remain blue for long?

SIROCCO, I came to know, has a history tracing back to PODC and DISC, and had a strong distributed computing presence. I did some homework to tilt my talk towards communication complexity, but could have done more to show the relationship between streaming and distributed computing. I made amends by talking in the open problems session, discussing two of my pet "new directions" for distributed streaming research: the MUD model for mapreduce, and distributed, continuous model for sensor networks; one stuck with the crowd and the other didn't.

It was nice to see Fabrizio Luccio, Alberto Marchetti Spaccamela and others at the conf, asking questions, formulating open problems, mentoring students. Also, it was fun kibbitzing with Guy, Shay, David, Shmuel, Tamir and others, people who can instantly translate across cultures, nations and experiences over dinner conversations.

Finally, I got a scooter ride in Rome, and time with the inimitable extended family of Luigi Laura who sent me off with home made limoncello, as usual.

Sunday, June 03, 2007

Fruits Inc. Contd

How could I have left out pluots, O Anonymous! Plout = Plum+Apricot, a hybrid not to be confused with the plumcot.It is a trademark of Zaiger Genetics, Modesto, California. So is the nearly-unknown Aprium which is closer to Apricot (just as Pluots are closer to Plums?).

While not a mix, fruit talk should eventually meander through the funky mangosteens with different takes.


No, this is not a posting about filters, but about flowers. It is the season, and they are exploding. I am reminded of the two volume book by plantoholics Roger Phillips and Martyn Rix. The british and american reviews are interesting! Here are some pictures from Vol I and Vol II.

Saturday, June 02, 2007

Software art

Whitney museum organized CoDeDOC, an exhibition that goes beyond the visuals of digital art and makes viewers look at the code behind the work, so Java/C/Perl or whatever is the paint, the code forms the brusk strokes and one goes beyond the canvas to peer at the tools. For theory CS and math, what would be equivalent to peering behind the final output: looking at the proof (with its individual styles) or the napkin scribble with coffee stains?

Haikus from NYers, NY Times, Circa 1997

Here's the East Village
Green mohawk, a pierced navel
And that's just the dogs.
(Matthew Wills, Brooklyn)
Nighttime is noisetime
cars cry like babies in pain
Somone pick them up
(Jerry Burke, Manhattan)

"I want the B train"
A boy cries on the A train
Only in New York.
(Cary LeCheen, Manhattan)

I live in New York
I can make it anywhere
I can't make it here.
(Ameer Gittens, The Bronx)

Why TCS?

The summer school in Finland (SADA) was fun. Lot of great lectures (Piotr, Nir, Lars, Paolo and alas, I missed Aris's lectures since he started after I left). I had to squeeze my lectures into M-W so I am not away too much. Lots of students (70+), most in 2nd year of PhD, preped and ready for research problems. The students came from all over Europe, in some cases, Israel, Canada and Asia, and from different backgrounds. I asked them why they were doing their PhD in theory, and in almost all the cases, the answer was that they wanted something concrete, clear, correct and (close to?) the truth. That is, what attracts them is the math of CS.