Saturday, January 27, 2007

Design Principles

Designing a system is an art. To design a usable system, one has to look at the applications, abstract away from them and look for the simplest pieces to build and the interactions between these pieces, so that once that plumbing is in place, others can build on top of it. Typically the plumbing one builds does not resemble the applications one had in mind. So, the motivation that yanked one to that place in the world is not the one that helps one put on their jeans, wear hefty shoes, lift the toolbox belt, and build the pieces. Lot of applications are compelling, but the systems one needs to build for them needs the drive derived from a different source.

Steve Martin, a contributor to the New Yorker, has a beautiful piece on poor designers in hell, of inventors who bequeathed the shrinkwrap for CD covers, the ungainly pineapple and the slippery corkscrew. They are visited by the angel of good design, of Ziploc bags, the perfection of a fruit i.e., the banana, and the milk carton. What fun.

Speaking of fruits. Kiwi fruit started its life as a Chinese Gooseberry, and through New Zealand, landed in California as late as late 60's to early 70's, coinciding with the rise of Computer Science and nouvelle cuisine, and it has thrived since. While a lot of exotic fruits have been discovered and developed in US market, there are still fruits out there that are popular in local regions and for which we need a business plan to grow and market in US.

Thursday, January 25, 2007

Clustering sets

Given sets S_1, ..., S_n, each S_i being a set of points on the plane, cluster the sets (using usual suspects of optimization criteria) with some suitable notion of distance between two pointsets. Any fun versions of this problem?

Teaching Vignettes

I heard about this Italian course where the teacher says at the beginning, "At the end of this course, you will be able to order coffee at a Starbucks with confidence."

I hear there is a primary school program (in Japan?) where the kids are taught to use chopsticks. The exam? Assaf, the new New Yorker, tells me that the final exam is to flip over oiled coins (say dimes) placed on a table top, as many as possible. I learned to use chopsticks and shovel rice because if I didn't, I wouldn't get anything to eat (at the Cantonese family style dining table a long time ago); later, for the pure pleasure, I learned to wrap lettuce, cut nori and chop dumplings to share. Seguing into art and chopsticks, I like the work of Donna Keiko Ozawa who has created nice pieces out of dumps, including sculptures with waribashi, the disposable wooden chopstick (of course there is a video of the artist describing the work on youtube) .

Teaching happens at many different levels of course. Joe Kilian recently mentioned (in the context of the graph evasiveness conjecture) that there were many problems in theoretical CS which are easy to state, and highly nontrivial to solve or open for long; introducing them to math researchers early in their career will help attract them to our area.

Finally, I hear in India they train elephants from when they are little by tying them down to a stake. The baby elephant learns that it can not escape. Later, a rope can hold a grown elephant to the stake, I am told.

Sunday, January 21, 2007

Homage to Friends & Movies

Stefan Langerman and Luigi Laura are movie fanatics, able to gather and gobble large number of movies and moods. I tried to pull a luigi or a stefan and watched Beat the Drum, Shadows in the Sun, Jakeob ui Jeongseok, Chokher Bali, Malek wa Ketaba, all during a single flight.
  • Beat the Drum: Sweet story of a Zula boy going to Johannesburg in search of his uncle, amidst the "curse".
  • Shadows in the Sun: Harvey Keitel tries his best, so does the fine Italian backdrop, but the movie of an author with a writer's block hiding from the world is stabbed by the script, other performances and the silly music, Claire Forlani notwithstanding.
  • Chokher Bali: Tagore's story massacred. Individual scenes in serious stress.
  • Malek wa Ketaba: Egyptian tale, modern, very modern. Hind (Hend?) Sabri sparkles.
  • Jakeob-ui Jeongseok: What fun. Technically a romantic comedy, but mainly, I liked the flawless looks and facade of the two leads being rippled by a series of episodes showing them in very much boy/girl petty urges.

Saturday, January 20, 2007

Winter day for stats

It is a crisp blue winter day. The trees, denuded, show strange shapes; the buildings stand taller, more revealed, and carry old fading signs of businesses long gone; the skyline is sharper and shadows long. The air, light and mood is of Santa Fe in January long ago before the mystic studios became shops.

Check out the distorterd maps that depict world trends. For example, how is Research and Development distributed in the world in spending and in employment, and what is the distribution of patents granted? This should provide plenty of problems for computational geometers. The methods behind these maps are from the work of Mark Newman.

Thursday, January 18, 2007

Making a Play

I watched Manhattan Theater Source's Spontaneous Combustion last weekend: a series of micro plays (6--8 min) that they write, rehearse, tech and perform in 48 hours. Each play had 2 characters, and as they conversated, they hit an instant when one character's view of romance/love/passion is suddenly turned around. One character spoke shakespeare-esque and the other the contemporary speak. Within these broad confines, the plays explored many different locales, from church to subway and airplane. There is a gleeful moment when a character describes some unknown, magical place she visited a long time ago while in NY that had large blue dome filled with stars and constellations, and throngs of people walked underneath. Locals know this magical place and how it was saved.

Fitting, Sensing and Learning

We are more than what we publish in research papers. We have insights, not just results and proofs. Luckily, there are ways to bring out these aspects, say through surveys and invited talks. I have been struggling to find the connection between sparse approximation, compressed sensing and learning problems: one senses that there are similarities and that if one learns to look at them in a certain light, they would fit in a puzzle together. Ron DeVore has a beautiful, mathematical exposition of the data fitting, sensing and learning problems worth reading.

Monday, January 15, 2007

Jetlagged in NY

You wake yourself up at midnite and go to what looks like an Italian party (vespas outside) in a club where smoke smirls and bodies shimmer as the lights twirl. I dance to the beat while the rest of the club seems to dance to the rhythm and they haven't disovered 50cent yet. I finish it off with pizza at the corner as the residents (me, in another day) yell to keep it down.

Saturday, January 13, 2007

Catching up: TECS in Pune

Harrick Vin and Mathai Joseph of Tata's research division organized Excellence in Computer Science (TECS) week at Pune Jan 3--7, 2007. There were 6 lectures each by Jim Kurose (sensor networking), Raghu Ramakrishnan (databases), Alex Smola (machine learning) and me (algorithms & theory), all related to analyzing massive data sets. Raghu. Jim and Alex gave very high quality lectures. I am sure the slides and videos of the lectures will be online soon. Me, well, in Yankee-esque language, I had trouble "locating" a couple of the lectures, but found my rhythm during the others.

Jim spoken about real-life experience with sensors for radar data gathering and other applications, a project that teaches one a lot from physics, hardware to systems. Raghu, inimitable, spoke about building database systems for web data. I liked his work on probabilistic databases, and suspect that is an area in which we will (need to) see followup. Alex gave almost encyclopedic lectures on machine learning, and I particularly liked the tips, do's and dont's sprinkled in his lectures. Lot of students in the audience. Also, the ever-sharp Jay Misra and the elegant C. R. Muthukrishnan from IIT M. I was touched that Raghu thanked all the teachers in India, who sometimes at great loss to themselves, shaped generations of Indian Computer Scientists we see around us now. He also reminded me of the topclass team Yahoo! Research has put together: Prabhakar, Andrei, Andrew, Ravikumar, Michael M, Raghu, ...

Social: We watched a fusion performance by a "jazz" band. Unlike other fusion bands, the fusion was subtle and gently handled. The flautist (Milind Date) played the flamboyant trumpteer and bleated us away. The tabla held the drum down to the jazz beat, and wandered off into eastern beats when the mood settled in. Beautiful.

Friday, January 12, 2007

Catching up: IIT Kanpur workshop on Streams

Sumit Ganguly and Manindra Agrawal conceived of running a workshop on data streams at IIT, Kanpur. Sudipto Guha and I helped put the workshop program together. It was an intense 3-days meeting sponsored by N. Murthy, the founder of Infosys. Yossi Matias provided an overview and some history behind the genesis of data synopses. Divesh Srivastava spoke about the database perspective. In addition, there were talks on data stream algorithms in Matrix Algebra, Geometry and Graphs, as well as on lower bounds, new models and connections to Compressed Sensing. The talk slides and videos (!) are on the program site. Alas, my (our) body language and hand gestures of captured there, better than youtube-quality. Excellent organization and execution!

There were many students. Their feedback: will be good to have more public technical discussions; are there interesting problems left in stream algorithms?; how to get internships. Yes, the workshop schedule should have more time for technical debates on the stage. Plenty. Almost every talk had a bunch of open problems, and whole new directions are just emerging, e.g., connections to automata, statistics, machine learning and compressed sensing. About internships, make connection with researchers on a technical level, try to converge on a technical problem or two, and followup with resumes.

Monday, January 01, 2007

Jetlagged in Pune, India.

The public spaces in US tend to have a problem: they are either too hot (in the winter) or too cold (in the summer), because it is difficult to calibrate the heating/cooling systems. In India, the problem is bad music. It is loud, anachronistically pop and for a country with great classical musical reportire, a disappointment.

I drove from Bombay to Pune over beautiful hills and traded one urban world (Bombay) for a more manageable one (Pune), I realized that India is a country of walls. People build walls around homes, universities, corporations, whatever, to keep the world out and the gardens in.

Totally jetlagged, I had chinese food for dinner (served by a Manipuri with vague oriental looks in "traditional" chinese garb, with a spicy cook from Orissa, Incredible India!) and worked on Times Kakuro. It is the harder brother, I hear, of Sudoku.

ps: We know Fermat's Last Theorem: there are no integer solutions > 2 for a^n+b^n=c^n. Its trivial brother is: there are no integer solutions > 2 for n^a+ n^b = n^c. Credit yourself only if you get a neat one-line solution.


I remember the moment at Los Alamos,NM when someone introduced the quiet man at the lunch table to me as "This is Metropolis." So many thoughts went through my head! I remember this was immediately after my thesis work on myraid problems, and I was on the lookout for new problems and directions to define my research career. Historically, coincidentally, it seems people like me ended up at Los Alamos/Santa Fe, something about the New Mexican desert. This is all beautifully described in Mike Waterman's prose-ode: Skiing the Sun. These days I work on adwords auctions and game theory, a new area for me. I got to meet Hal Varian who gave me a puzzle from his thesis. More on that later. His non-academic writing is quite interesting too!


Here is something from the Times of India: "Like Govind, an 18-year old in Bhiloda, who moved to his in-laws' house after getting engaged to Rekha. Keen to win over his in-laws, he cooked lipsmacking meals and kept the house in order; A snake-charmer, Govind would then go out with his reptiles to earn a living."

Science of It

Operations Research community brands itself and calsl itself, the Science of Better. Sigh. Science of Near-Best?