books, stories, poems, algorithms, math and computer science.
some art and anecdotes too.
Sunday, April 27, 2008
Gaussian Legend
Gauss kept a blog (a journal used to be called they were), and left some puzzles behind; also, he is the subject of stories retold. I heard two sorta jokes in which he makes an appearance:
Q: What is the best known dad-son mathematician team? A: Gauss and his father.
Q: Who was Seidel of Gauss-Seidel method? A: Gauss's programmer.
In the standard RAM model, one hits the sorting bottleneck of \Omega(n\log n) sometimes, and researchers find ways around by using say word operations that avoid comparisons. In the PRAM world, people tried to get around certain sorting bottleneck by "padded sorting", where items can appear in sorted order but with empty memory locations between them.
I was recently drawn to this issue when working with Gianni Franceschini and Roberto Grossi. Consider the external memory (just the vanilla version with input of size N on disk, internal memory of size M, and block size B) model. Even problems like permuting an array that takes O(N) time in the RAM model, and therefore, should ideally just take linear number O(N/B) of block accesses, seem to take essentially \Omega(N/B \log_{M/B} N/B) block accesses in the external memory model; sorting, convex hulls, MST and other problems then face similar bottleneck.
I think this is fundamental and one would think researchers would have by now figured out different ways to circumvent this bottleneck with additional assumptions on the input or on the model. But I haven't found anything. Any pointers?
ps: Btw, for the problem we were working on, we did find an algorithm with linear number O(N/B) of accesses. The algorithm is too long to be described in this blog.
I hear that the trains in St. Petersburg have seats on either side facing each other with a central open aisle for people to stand, presumably in two columns, each facing a seated column, and their backs to each other. This configuration lets the people who stand share in whatever the seated ones read, but one has to learn to read upside down and right to left. Apparently, now there is a suggestion to print books in two halves: each page will have the lower half printed normally and the upper half printed in reverse, bottom to top; this way, if you are standing or seated, you can read the book conveniently!
I read somewhere that an Egyptian newspaper has a circulation of X millions and a readership of 2X millions a day.
At Penn Station, in NY, there is a brotherhood of middle-aged men (never a woman) who salvage leftover NY Times from trash cans for personal reading. Most of them can afford to buy one, but there is some draw I suppose of snatched treasure when you retrieve a nice, complete paper, a gem, hardly read, found among the others soaked in coffee, hiding chewing gum and generally abandoned by the commuters. The cleaning staff help out. When they empty the trash, if they find such a gem, they leave it out on the can.
I heard Leo Guibas talk the other day. It was refreshing a hear a talk that was about a research agenda, one with deep math and algorithmics, rather than an isolated result. He spoke for example about discovering the structure of given set of geometric objects, leading to a nice definition of a "bar code" that captured betti numbers and other topological properties; lot of the talk described his work with 3D shapes and objects and included some nifty demos (one on finding symmetry within the Coliseum was terrific). Must go, read these papers.
ps: As an aside, 2D barcodes encode more information than the standard 1D barcodes in products and are slowly finding fun applications.
In the past, when I worked to expand my English vocabulary, I learned to parse a word down to its roots, seek words with similar roots, and generally analyze my way through them. Alas, the short words defeat this process totally: either you know them or they sink you.
Thanks to Craig, I came across "frit" (not fret or flit), best understood by this passage:
There are more than fifteen hundred panels of glass in the InterActiveCorp building, and almost every one is unique; they curve to fit the shape of the façade, gently concave one moment, convex the next. The white color is provided by ceramic dots, known as frits, bonded to the glass. Fritting is a common way of reducing glare in glass buildings, but Gehry has exploited its potential for drama. Each panel is densely fritted at the top and bottom but nearly clear at eye level. Viewed from the outside, the building exhibits dark, hazy horizontal stripes, as if the glass had been spray-painted.
Michal Feldman, Noam Nisam and Moshe Tennenholtz are organizing the Third Israeli Seminar on Computational Game Theory. I will present 2 technical results: markov user models and their impact on ad auctions & stable matching based auctions. I am looking forward to hearing the 4 other talks, and as usual, to the travel to Israel. As my friend said, "if you are looking forward to a trip to Israel, you are either a theoretical computer scientist or a NYer", and I am doubly vested.
I can't believe I am quoting from the WIRED magazine, but this line about the devotion Steve Jobs inspires in his (um, Apple) employees got my attention:
he can make the task of designing a power supply feel like a mission from God
The article has some punchy lines and phrases (radical opacity!).
Apple to Apple. Some of you may know Apple (TM) sued the Big Apple (NY) over its GreeNYC campaign. The GreeNYC logo for those who can appreciate the nuance is \infty. :)
Those who fly United Airlines can listen to the chat between air traffic controller and the pilots (Once heard. Pilot:"Up 1000 ft, Roger." ATC:"No, Down 1000 ft". Pilot:"Down 1000 ft, Roger.") , or just the ACKs between the airplanes on the flight corridor (it is incessant. You need to know the callsigns and the speak: "Speedbird", "Reach", "Heavy"). There is the reality show aspect to it, as WSJ discusses (the famed journal first starts with sneaking a bathroom break on flights and later redeems itself by mentioning the bird's eye view from a camera mounted in the tail fin of the A380's). I wonder how much of reality we (or our audience) can take if our research world went live. Not as funny as the ATCs?
Several years ago, I went to a bookwriters-only party, I was not a bookwriter then, so I had to go as one's "date". I continue to peek into the world of bookwriters from outside. One of my fave bookstores is Book-Off from Japan; below, is a different kind of book-off:
NY Times has an article today about Mr. Parker who has written over 200000 "books", with some help from the computer. The author may have algorithms for creating and populating book templates with facts, may be factoids, and some predictions. So, there seem to be interesting technical challenges. Genres from crosswords, poetry, animated games, statistics to romance novels.
Papers accepted to ACM Symp on Electronic Commerce (EC), 2008. Time to read, read, ...
For distraction, check out the NYer cartoon in the current issue by Paul Karasick (great interview): audio books (A shelf of audio books calls out to a customer “me!” “no, me!” “c’mon, me!”.)
ps: My friends find me elliptical, in story telling, in drawing on references, and in my sense of humor: the connections have to take the long route to get to each other, or to circle off. What fun.
The b-boys, dancers from The Bronx from 70's who warred on the street and started the dance revolution, may have grown up and moved on, but the youth world over is still under the influence, and taking it to great new heights. I walked around the lower east side tenements last night and I gave in to watch a midnight movie: planet b'boy.
It is a documentary about the background to b-boys around the world, their preparation for the ultimate annual battle in Germany where nations get represented through the street attitude of these youth and the finale, where b-boys bring their muscle, puff and drink some, and face off for paltry 5k euros, split, I don't know, 50 ways, but give it everything they got. Koreans are incredible and take it to each other along the 38th parallel, the Japanese are elegant and great fun, the French are talented and angst-ridden, and the Americans, each of them brings a gem of a game. The movie for most part lets the action just be, with careful camera placement, and rightly, avoids too much slow motion capture. Nice review here.
You must watch the movie, sitting at the last row at the Sunshine cinema, with what looked like 4 teenagers in rebellion who had sneaked in to the midnight movie, a large man who mouthed off the dialog even before it appeared on the screen and whether you could see it or not, there were tattooes, piercings, and many b-boys in training. The audience came out of the theater at 2.30 AM and a small group of them just danced on the sidewalk, b-boy style, as they waited for a taxi.
Last nite, I walked with my head down, mind floating and thoughts submerged, with the sureness of a villager who navigates with the memory of his legs and not by the explicit street and store signs, into this sushi restaurant I know. I negotiated with the woman doing the seating, finagled a seat at the bar, and plopped down on the chair, and looked up: there was no sushi chef, and indeed, no sushi. The place had transformed itself from a rarity of a japanese restaurant with a female sushi chef into a korean restaurant. They had left the layout the same and subtly updated the fixtures and colors. The sushi counter was there with a different counter top, and behind it lay emptiness. I stared for a while before walking out and heading home, this time paying attention to store signs, a manhattan lesson for the day.
Bala sent the following to me by email. Someone may have already sent it to you, you may have sent it to others, or these events may happen in the future: unstable friends forever!
Ralph and Edna's Love Story
Just because someone doesn't love you the way you want them to, doesn't mean they don't love you with all they have. Ralph and Edna were both patients in a mental hospital. One day while they were walking past the hospital swimming pool, Ralph suddenly jumped into the deep end. He sank to the bottom of the pool and stayed there. Edna promptly jumped in to save him. She swam to the bottom and pulled him out.
When the Head Nurse Director became aware of Edna's heroic act she immediately ordered her to be discharged from the hospital, as she now considered her to be mentally stable. When she went to tell Edna the news she said, 'Edna, I have good news and bad news. The good news is you're being discharged, since you were able to rationally respond to a crisis by jumping in and saving the life of the person you love. I have concluded that your act displays sound mindedness. The bad news is Ralph hung himself in the bathroom with his bathrobe belt right after you saved him. I am so sorry, but he's dead.' Edna replied, 'He didn't hang himself, I put him there to dry. How soon can I go home?'
Happy Mental Health day!
You can do your bit by remembering to send an email to an unstable friend.
Some of the research labs are part of companies that patent very aggressively. Well, they are internal economies, and incentives aside, they set up an environment at their workplace which can be quite convincing that patents are important for their employer. Researchers have worked out several stories in their head that it is indeed true (the licensing fee from a few slam-dunk patents will provide revenue for supporting a lot of researchers; if my company doesn't patent it, the competitor would and then charge a licensing fee; company A meets company B with a portfolio full of patents, both avoid shootout by not opening the portfolio for scrutiny, and simply shake hands; etc.) I am a sceptic: generally, it seems USPTO relies on the courts to work out the worth of the patents in cases where there is a real need, and most patents filed by corporate lab researchers ferment in the portfolio bags.
The question that interests me is patenting in universities, where in general, resources are scarce. Some universities are aggressive about protecting their faculty research via patents; this is presumably because they have fat budgets from prior licensing successes. Others less so, and they let individual faculty find the resources to file patents and rely on the fact that the faculty will do it only for compelling cases (eg there is a startup company in the works). This provides some sort a natural barrier and foments selective patenting. Does this work out well in practice, or are their inefficiencies?
I like giving talks: they are an opportunity to share insights that go beyond the formalese of a paper with its proofs and figures, and show pictures, the paths you took, and the ones you wish had worked out and yet might, in others' hands. On the whole though, the act of giving talks is a slippery opportunity. It is like a banana peel left on the sidewalk, and depending on how you approach it, you step over the peel or land on the sidewalk.
I gave a talk on April 1st, and difficult as it was to follow the momentous announcement that day, I made it more difficult by choosing to give a brand new talk about recent results on sponsored search auctions, some just having left the oven. I made it even more difficult by choosing to show that the ((a) we can be creative about modeling and posing problems, and indeed we should do so because radically new methods may actually get tested and have an impact, and (b) we can bring our CS type thinking to an area worked over by Economists, and generate surprises.
I did not quite succeed in doing the above with any clarity, and as Mihai (who I have always found to be a careful thinker when analyzing situations) said, I ended up marginalizing algorithms. True. Somehow all the algorithmic hard work ended up being ultimately summarized as dynamic programming and stable matching, ~50 year old algorithmic concepts. That banana peel was slippery!
ps: Piotr was pleased that I showed new pictures. Ever clever, he also coined the word "googleheim" in developing a concept over dinner of how search companies can help art museums.
