Monday, December 31, 2007

Wish 1 Granted

Iftah Gamzu has done it: he has put together a webpage (suresh: sorry, it is not a wiki) with the list of invited speakers at various theory conferences. There is a list per conf and also much shorter per conf/per year. There are some gaps, and obviously it has to be backfilled. Please send comments/suggestions and more importantly, missing information to Iftah. My sincere thanks to him.

ps: I discovered Andrei's upcoming plenary talk at SODA on Computational Advertising, and am looking forward to it.

Sunday, December 30, 2007

Satisfying one thousand desires or conquering just one

This is definitely a non-CS blog. Sometimes I need peace, and today I went to the Rubin's Museum of Himalayan Art to get it. In particular, I wanted to see the photographs of Bhutan by Kenro Izu (NYT has been peddling Bhutan in travel and art, I decided to consider it for travel later and check out the art now). Clicking on the picture on the left will take you to a set of photographs, B&W and curiously, almost archaically still portraits.

The museum was also playing a movie called Samsara (trailer, the beginning). It turned out to be a visually beautiful film about a Buddhist monk's life, somewhat inspired by characters in Buddha's life. Shawn Ku played the monk and was not good at communicating the thoughts that motivate his actions, some self-destructive, some confrontational, and most abruptly life-changing; but then, Siddhartha was similar in sketchy legends in India. In contrast, Christy Chung who played his wife, a standin for real life Yasodara, is talented and played fabulously. The tagline is: Satisfying one thousand desires or conquering just one? Watch the movie for an explanation.

Well, this is NY, the movie couldn't be just played; there was an preamble of an introduction to the movie by Rubin staff and a short (film) interview of the director who talked about the 80+ different sounds of the winds in the Himalayas that he used throughout the movie for the soundtrack. Very cool.


Wednesday, December 26, 2007

Wish List Item 2

What I like about YouTube is "collective consciousness". If I liked a 30-sec segment in a film from say the 70's, chances are several hundred thousand others watched that film and liked that segment too, and further, the chances are 10's of those fans upload that precise segment onto YouTube, so viola, a search with the name of the film should give the 30-sec gem. This is incredibly efficient and mostly it works.

After some struggle, I found this segment (not 30-sec, several million dollars and months worth of filming): two trucks cross a swaying, decrepit rope bridge amidst a storm, carrying high explosive nitro. The best part is the audio of the roaring truck and the crunching wood.

For the times the process does NOT work, here is my wish list item 2, rather, a meta-wish item: someone could create a bulletin board/marketplace/whatever for people to post their requests for short movie segments, their fave moments in videos, and for others to supply them, so the demand meets the volunteers' supplies. One can generalize this further and create such a request/post meeting place for highly specific user-generated content too.

When I go shopping

Happy holiday wishes to all! Whether you like shopping or you don't, you still gotta do it and shop gifts for friends, neighbors and family. I distract myself as follows.

Year Ends

Two years ago, I agonized over if I should blog: it gives me another channel to express myself (besides papers, PCs, talks, etc), and will that ultimately be scientifically unfair? Suresh and David helped me get over those concerns. Unlike most other professions, being a researcher is really one of self-gratification, instant or otherwise, because nearly every act, everything we do in a day (think/solve problems, write/referee papers/grants) translates to supporting our view of world/science or to becoming more skilled or more crassly, to a line in our CV. Blogging is a perk, with an immediate, instant gratification, and I am thankful to have this outlet even as I split my days among research, products, plans and plain hopes. So, thank you all.

Saturday, December 22, 2007

DBLP Refines Itself

I noticed a feature in DBLP that lets one refine publications of an author by venue, by authors, or by year and presents the selected subset according to the refinement. Here is an example.

Mea culpa. As a commenter points out, DBLP-plus uses CompleteSearch by Holger Bast. I have always liked Holger's research trajectory (early stuff on integer sorting, then "scheduling at twilight", some shortest paths stuff) and the current work on search engine technology has some nice use cases.

Triptychs again, this time sword fights

Someone asked me to do a triptych again, so here it is.
  • Darth Maul, by far the best fighter on the screen, with his well-balanced stance and professional, fluid moves, gets cut in half;
  • Mifune holds his breath and ours, and strikes venomously in a blink;
  • The anime sword glints and eventually D. takes on the vampire, after 9 min.


Friday, December 21, 2007

Uncommon Cents

I dislike coins left lying on the streets and pick them up whenever I can, and mostly, they are pennies. And in the annals of well-known dreams, there is one in which you walk down a street and you start to pick up a coin from the street, then see another, and then another, and so on... It was dream come true the other day when I was at 30 Roc (Rockefeller) and came across the Penny Field, a field of 100 million pennies collected by school children, a swimming pool of copper, created by Common Cents.


Acta Diurna to Times

The first published newspaper was the Acta Diurna in Rome from 59 BC; it had sections for the news from the Roman Forum, and I am sure, a Sports Section, of drama from the Coliseum. The evolution of newspapers from then to now is simple: basically they spread geographically, became mechanized, added ads, photos and eventually color, collided with other industries from Radio, TV to the Internet, and now are struggling but still very much a force (at least in my life).

One of the fascinating aspects of newspaper publishing (and of my research interest) is that of advertisements (see an early ad on the left; more info here). Very little has changed since the early days. The timeline sees first full page ads, first double columns ones, first ad agency, and so on, but basically, the negotiation between the publishers and advertisers for determining the price, advertiser's targeting and expectations, determining how effective the ads are, etc. have changed little in the past 300+ years. It was good to see a mildly-coaxing article in the current issue of Presstime (magazine of the Newspaper Association of America) about trying new business models. Unfortunately, the article is not online.

Wish List, Item 1.

It will be great to have a list of theory conferences in each year and their plenary speakers, going back to the past. Titles of their talks will be a bonus. I am happy to collect lists, and put them on the web in a nice way. Alternatively, if someone does it, or if there is already such a website, that will be great.

Update: Thanks to Iftah Gamzu, who I discovered, is maintaining a list of accepted papers at theory conferences as well as deadlines.

Wednesday, December 19, 2007

Hotel Aggregator

From Brandon McQueen (google is unaware it seems), comes the pointer to an aggregator of hotel room reservations (from Australia) for comparison shopping with upto 10% rebate for university people. I haven't used their service; if someone has any experience with them, please let me know. Btw, one should also understand the legal aspects of getting rebate on a travel that is reimbursed through one's employer, and how to discount them on reimbursement forms.

Tuesday, December 18, 2007

Indian Fiction: Short Stories

I like reading a collection of short stories: you leave one out for the wait at the baggage claim and read the rest during the flight.

I have been reading short story collections of modern-ish indian writers. The previous generation (R. K. Narayanan, Kushwant Singh) were inspired by the villages and the oddity of contemporary life in India. Unlike the modern movies in India that look to Hollywood for material (song tunes, fight sequences, story plots), modern writers seem to be part of some diaspora (either within India or across countries) and look to the previous generation for the material. So experiences of parents/uncles/aunts get retold, and the generational passage is achieved not just in wealth as in parents buying the first homes for their children, but as in stories, struggles, sense of values, duties and guilts.

Observations: Mumbai and Kolkata get a lot of time in these books and to a limited extent Delhi too; women writers are plenty, even disproportionately?


Monday, December 17, 2007

Problems on subsignals

Given two strings S and T of same length, it is trivial to compare if S=T. If S were of length n, T were of length m, n > m, we can ask whether T appears as a substring of S, that is, T=S[i,i+m-1], for some i. Then, there are potentially O(n-m) substrings of S to be compared to T, and the problem is now the non-trivial, much-studied string matching problem. In this example and elsewhere, switching from strings to substrings normally makes problems interesting.

Let me propose a similar extension for the recently-solved compressed sensing problem which is: given a signal S[1,m] that is k-sparse in some m-dimensional basis, find approximate reconstruction of S with klog (n/k) linear measurements. An extension is, given an m-dimensional basis and S[1,n] where each S[i,i+m-1] is k-sparse in that basis, find an approximate reconstruction of S faster than it takes to solving O(n-m) instances of the basic compressed sensing problem independently and collating a suitable approximation to S, or is better approximation to S than solving O(n/m) nonoverlapping instances of the basic compressed sensing problem.

To be honest, I am doing seat-of-the-pants research here. I haven't figured out what class of S's satisfy the conditions above, what is a suitable definition of approximate reconstruction of such S's, where problems of this type arise. That doesn't stop me from saying problems of these sorts can be solved using random set of linear measurements of dimension m, FFTs, suitable sublinear reconstruction algorithms, and (all standard fare so far, but now the handwave) some way of taking consensus from the O(n-m) sets of O(k polylog) basis vectors to get O(nk polylog) time approximation to S. Hope someone proves me right or wrong, they can take all the credit of course because almost certainly they have to formulate the problem more precisely (provided they too are not flying by the seat-of-the-pants).

Sunday, December 16, 2007


I can't match David's skills in geometric rendition, and even in high school math days, geometry was my weakest link.

Sometimes I need 3D models and use SketchUp programs in demos. They can be imported into some of the mapping products, and I hear architects upload the SketchUp version of their design and view it in its correct context in the physical world. Wonder if they are used in academic conference presentations.

Anyway, on the left is a SketchUp of l_p ball (for some p), and the source is here, thanks to Petros Boufounos of Rice U.

Sunday, December 09, 2007

Jobs and Mis-estimates

Elsewhere in the blog world of tcs, there is an ongoing discussion on job interviews. I remember a game we used to play in college where the goal is to propose a single word to summarize a given person, and the criteria of success was if two or more people who know that person agree it to be suitably descriptive or evocative word for that person. NY Times ran a similar game with "Country", in this case, "US", on July 4th, a few years ago.

Job interviews are like that. In any given organization, many people get to interact with the candidate; their views and scores, yearly propensities and daily quirks, candidate's moments, are all pooled together and a verdict emerges. A top research university judges for potential scientific glory or fat grants, a teaching university may judge for teaching/mentoring or the ability to write the definitive book, and a company, for the ability to conceive of systems, build and deliver, and fit in. Even at PhD level, hiring takes different forms because there are different positions: postdocs, tenure-track, glorified programmers, system builders, etc.

Academics tend to overestimate the ability of their graduates and mistake coding for system building (it is a skill that is not learned easily), and the Companies tend to underestimate the need to get employees who are trained to think methodically, and mistake novelty and anything their PhDs do for fundamental research.

Gentle snow

First snow of this season, sparrows leave footprints.


Saturday, December 08, 2007


Traveling between IAH (Houston) and JFK (New York) is like flying between two sprawling malls. The travel yielded two musical moments. In Houston, a cab driver spoke of the new Senegalese restaurant, described mouthwatering foods, and played Youssou N'Dour. In NY, the cab driver spoke about his native Haiti, drummed the steering wheel with his long fingers, played Kompa from his CD collection and cruised. Sweet! Music aside, with minutes to get onboard a flight in Houston, I rushed to pick up some reading material and:

Store attendant: Can I help you?
Me: Where do you keep Atlantic Monthly or Harper's?
Helpful SA: Uh.. We have Texas Monthly...

I let the national magazine of Texas be, grabbed a Harper's and learned (nice "readings" feature this month): McDonald's has a site in UK where people can ask questions and they would provide answers. This is a public-relations move, it seems! Ex question: Will you ever release a McClaren or Mclown burger?


Problems in Sparse Approximation, On the Side

Given v in R^n, an orthonormal basis of vectors u_1,...,u_n, and an integer B << n, a sparse approximation problem is to find a linear combination v' of at most B of the basis vectors to minimize ||v-v'||_2. In this case, we can solve the problem optimally by picking the B largest | < v . u_i > |. A problem of my interest is the variation where we have some side information about v, or alternatively, additional constraints on v besides sparseness. For example, we may know that v is zero in at most t dimensions, or we may know the t dimensions in which it is zero, or we may know the norm of v projected on those dimensions where it exceeds certain threshold, etc. What is the complexity of such problems?

Compressed Sensing, Enriched

For an area to be successful in Applied Algorithms, several things have to come together: the math and theory should be novel and get the community's respect, the applications should solve a genuine problem or satisfy an important need, and researchers have to be creative to put it all together, engineer and deliver. Many researchers in (applied) algorithms have learned in the past couple of decades to do more than one of the above, if not all, and consequently, some of the applied algorithms areas have been successful (computational biology and streaming are two examples on my mind, but I am sure there are others).

Compressed Sensing is emerging as such a successful area. It has a pedigree of significant Math and theory of CS: this aspect has been talked about, blogged about, covered in media and we know great researchers bearing the torches. It has an incredible amount of applications. Rich Baraniuk and his terrific team have not only done the math and theory, but have also built things: cameras (award), MRI imagers, hyperspectral/radar imaging, DNA microarrays, and myraid others. This requires insight to figure out applications, creative adaptation of methods, tremendous engineering talent to execute them and a lot of thought and sweat. Others have joined in, and it is exciting to see signal processing, EE, biomedical and other researchers now growing the area even further by building hardware, software and useable ware.

ps: Rich gave an inspiring plenary talk at the von Neumann Symposium on Sparse Representations earlier this year.

Wednesday, December 05, 2007

Zebra Graphs

Science News has an article on how understanding the structure of dynamic interactions between social entities explains their behavior. The nodes are Zebras and the edges link Zebras that are near each other during some time. You study the structure of these time varying graphs to figure out
is there a change in the Zebras' interactions just before a bachelor overthrows a stallion in a coup? When Zebras flee a lion, how do they decide which Zebra will lead the stampede?..
The article is well written (Facebook hasn't yet opened up a site for zebras.), contains two useful references, and it showcases a genuine example of algorithmic thinking and problem-solving by Berger-Wolf that impacts Biology.