Monday, February 26, 2007

S* and the City

A recent article on Google offices in New York is titled, Search & the City. NY Academy of Sciences has a webzine called Science & the City. The British have Stress & the City. We have Satellites & the City from 2005 and surely, others before that. Will we soon have Desperate H*s?

Saturday, February 24, 2007


Bristol in UK is a Pittsburgh-esque city, with a prosperous industrial past in mid 1800's that has left remnant signs in its mansions and grand construction projects, some due to Brunel. UK continues to be intellect-centric: a TV program required participants to generate a target number (or as close to it as possible) from a given set of numbers using standard arithmetic operations (in less than 30 sec, and the target number was something like 423 in one example from 6 integers); a couple on the flight from Bristol to EWR (direct, no less, thanks Continental) who persisted with a Sunday times crossword puzzle during the entire flight; ...

The Bristol Algorithm Days drew its share of acronyms (DAD, MAD, LAD for Durham, Manchester and London, resp.). It was good to see a significant fraction of algorithmers from UK at the meeting, and some of the talks were very good, including ones on Burrows-Wheeler transform, power scheduling algorithms, worst case data structures and quantum computing. Slides should be online soon. Raphael Clifford and Paul Sant were excellent hosts, both shepherding good talks through and urging discussions about open problems (will some one write them up please). Paul, always the adversary, tried to distract the audience during my talk by giving them a Sudoku, which, I managed to solve later and was pleased to win/earn a wooden puzzle as a prize. Lots of puzzlers there.


Sometime ago, the PhD students at Rutgers organized a talk and asked me to speak about job interviews. Most knew about the academic job market, and really wanted to know about jobs at (research) labs and companies. Jobs in labs fall into at least 3 categories:
  • one writes a research paper and then shops around to see if someone in the company will find it useful.
  • one first builds something useful and later writes the paper.
  • one just builds.
The companies differ on what building means:
  • code enough to do the plots in the paper.
  • code enough to prototype, GUI included, and shop around.
  • code the prototype and get others to use it internally (in the company, community).
  • code to release for (paying?) customer use.
Seen from the interviewer point of view, one can tell when someone has done their homework. When asked what would a candidate do at the job, one of the common responses is, "I want to be close to the data". I don't usually know what that means, and as Graham Cormode (paraphrased) quips, "When one says they want to be close to the ocean, do they want to watch the waves or surf?".

Saturday, February 17, 2007


In a few hours I am going to UK for the Bristol Algorithm Days, yes, not Algorithms Day. My plan is to give a talk on Algorithms for Sparse Approximation problems, this time working in Compressed Sensing, Non-L2 norms, as well as the recent matrix rank approximation results. This talk is slowly taking a shape where I think I should write a survey. Btw, it is good to see algorithms researchers in UK spread out to Bristol, Bedfordshire, Liverpool and beyond, to add to Kings, Leicester, Edinburgh and Warwick. I like travelling to UK and the throbbing algorithms community in UK is going to give me another opportunity in March when I go to attend the Workshop on Algorithmic Game Theory at Warwick.

There is the IntErnational Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies that goes by ESCAPE. I recently got an email from the ACM Conference on Electronic Commerce which I think occasionally goes by ACEC. A pdf for some conference acronyms from Springer is a perverse fun to peruse.

Friday, February 16, 2007

The Secret

I watched the play The Secret of Mme Bonnard's Bath, about the painter Pierre Bonnard's life, his painting and the intersection of both in overt ways (his love interests, both the long term one which left him entrapped and the short term one that promised him the flight) and covert ways (the painting of the posed woman in bath is that of a woman who in her death imitated his painting of a woman in bath which was a painting of a woman he posed in the bath for a painting; the pleasure of the bath in its swirls mixes with the love that bled at a different place and different time). The paintings kept me entralled, the acting was fine, but I kept getting distracted with the storyline of infidelity and judgements, and of the painter who appeared the same, be it in his 20's or 70's, and therefore just inserted himself into the flow. Pierre Bonnard's paintings.

Saturday, February 10, 2007

Weekend Walks

Life is hectic, so I am happy when I can wrangle a walk during the weekend. Today my walk took me by what used to be a secondhand book store on Bleecker, long gone, now playing the Anti-Valentine Pop Shoppe for the curiously strong chocolate Altoids. Free coffee by Ninth Street Espresso.


New York City has gross annual product of more than US$450B, not counting the larger metro region around it. What it all amounts to is a line in the 1996 movie City Hall in which Al Pacino, playing Mayor Pappas, says with an impish smile and bravado, "Welcome to NY, the Sushi Capital of the World". Later, he is proved right:

Thursday, February 08, 2007


Problem: Given a string S, find the shortest string obtained by repeatedly removing any series of identical characters of length at least 2. Find the shortest transcipt?

In 2d, we generalize it as follows. We have an n X n gird in which each cell is labeled one of the 4 colors R,G,B,Y. Find the smallest object by repeatedly dropping any contiguous portion of identical colors (colors pack the empty cells if any to the bottom and left). Reminds one of the Same GNOME game (not quite interesting as a game?). Any formal analysis out there?

X and Y

There are quotes involving functions that take arguments X and Y, and swapping them works. For example,

The relationship between theoreticians and practitioners is based on trust and understanding: theoreticians (X) do not trust practitioners (Y) and practitioners do not understand theoreticians.

Actually, that quote has a couple of (X,Y) pairs!

The book review last Sunday has a review of poems by John Laughlin, a great publisher---he has published James Joyce, Tennessee Williams, Nabokov, Henry Miller, Dylan Thomas---and a ?-poet, and ends with a quote,

"For a poet (X), he was a great publisher (Y), and for a publisher, he was a great poet".

Tuesday, February 06, 2007

Databaser Life

Soon SIGMOD and PODS results will roll in,
and then the VLDB fog will follow.
Awaiting the Summer that will bring travels,
Before the Winter dumps the new cycle on one.

Monday, February 05, 2007

Web 2.0

This is not really algorithms, math, poetry or ... This may be art? Here is a video on where the web is headed, thanks to Mark Sandler, the Researcher, the Hacker, the ... (where does he find the time?)

Thursday, February 01, 2007

Being the Outsider

I moved schools while growing up, catching myself with kids who spoke freely in languages I barely knew, and that included English. I found it natural being an outsider in the playfield or in the classroom or just about anywhere. Now there is Outsider Art. It is art by people outside the system (amateurs, people in prison, people who are insane, or whatever) of schools, society or sanity. In Europe, it is less gently called d'Art Brut or Primitive Art. There is a museum for Outsider Art in Lausanne, Switzerland, a homage to the intense and the quite insane. There are dozens of galleries for Outsider Art in NY. The Puck building in NY had its show of Outsider Art recently. NY Times had a review:

"Working on brown paper bags with colored pencil, Charles Steffen (1927-1995), an artist from Illinois afflicted with schizophrenia, toiled away at home, producing two or three drawings a day. Gnarled but expressive representations of everyday life, they include self-portraits, his bedridden mother, the bank teller who cashed his Social Security checks, flowers from his yard, scenes from a state hospital where he had undergone treatment.

Drawing the same subjects over and over, he experimented from time to time by merging his figures with renderings of plants and tar or tobacco stains he saw on the sidewalk, sometimes combining male and female figures."

So it is not just art by living people who are reluctant to call themselves artists (Ludovico Laura once said, "To be an artist, you have to be dead"). It is by the true outsiders in mental and physical realms.


That old ode to new york streets by Lauren Hill.

I philosophy
Possibly speak tongues
Beat drum, Abyssinian, street Baptist
Rap this in fine linen, from the beginning
My practice extending across the atlas
I begat this
Flipping in the ghetto on a dirty mattress