Virtual Estate

My life usually goes through changes, beyond the cadence of the semesters and summers that professors see, or the cyclic rhythms of conferences that researchers calculate out; my changes include abrupt travels, new pastime (mountain biking now), unruly working hours, evolving research topics, or obsessions with new thoughts and gadgets. So, at some core level, I appreciate a non-changing, focus point of a piece of real estate that is mine, my home. For amusement, here are two such permanent pieces of estates, these are virtual.

• You could buy a decimal digit of \pi at mysliceofpi at its face value of dollar (digit i costs i dollars, and its font size is a subtly increasing function of i). You can rent out or sell the digits too. The page will remain for a "long" time.
  
• Oldie: You could have bought a rectangular set of pixels at a dollar a pixel (1000 X 1000, you do the math) at million dollar homepage, and the seller gurantees "The pixels you buy will be displayed on the homepage permanently.", You can put a logo and link it to whatever.

Spectating Politics

I watch the political process in workplaces, countries, or whatever mainly as a spectator. So, typically, I just look for interesting moments: I found

• a great line: Bill Clinton, ever the clever speaker, said the other day, "People the world over have always been impressed with the power of our example than by the example of our power." and
• a great spoof: Onion, ever the spoofer, did the piece on the left on polls and demographics and sticks it to the statisticians.

A Gadget

Mark Sandler put it in front of me, and I needed one for myself immediately. It is a gadget, it is a pen, it is an electronic pen that writes on special paper. It records (audio and visual) what you speak as you write, and plays it back. Now that does not sound cool, but writing is ultimately a visceral experience, so walk over to an electronic store, remember the boy that you are, play with the livescribe pulse, and I would be surprised if you too wouldn't want one of these.

ps: You just draw 9 vertical lines, 2 horizontal ones, and play piano. Whimsical.

A NY Day of Detoxing

Looking ahead, I am glad Olympics lost out the best tagline I have heard, NYC Olympics2012: "Every Country Gets Homefield Advantage''. True.

NYC's tagline for the day (today) was Play. Run. Walk. Bike. Breathe. The city shut off some streets to motor traffic and I joined all who thronged. Young ones, walkers, sidewalk aerobic lessons and skate repairs, whatever, people taking over the scenic Park Ave.

Detoxing doesn't end with miles of tiring bicycle ride. It ends with me getting the new look on the left.

A Day of American Fiction

On Wednesday, Paul Auster came to talk at my work, and reminded me that though I may have cooled off on Paul Auster, I am still running hot on American Fiction, and needed a dose. So, I went to Shakespeare & Co bookstore on Broadway and binged.

Hours later, I walked out with

• David Mamet's edgy, subversive writing on the movie business ( NPR podcast interview here; David is a genius; his gem Glengary Glen Ross is a must-see movie),
  
• Nathan Englander's new fiction from last year (Nathan is the writer of a short story collection from 2000, the best I have read in last 10 years or more, and is beyond edgy, pure scalpel),
  
• and several others.

A day like this does not end there. Essense of binging is excessing. I pulled out Mamet and read it voraciously, over hot soba at Soba ya on the east side, teeth rattling and gums hurting as the angry soup made its way down my gullet. Mamet quotes "In the morning you're making Citizen Kane; after lunch you're making The Dukes of Hazzard."

3+ Movies

I caught Woody Allen's Vicky Cristina Barcelona on its release on Aug 15th. Allen has moved from Venice to London and is now in Barcelona. The movie is a fantastic job of stereotypes: 3-some proposing Catalan painter; free-spirited American discovering her talent; uptight, scholarly American who marries a Wall Street type; etc. The twist is that each has Woody-esque moments, stammering and rationalizing. Penelope Cruz breaks into the plot midway and holds the movie in an unstable, quirky equilibrium. Forget the reviews, just go, enjoy. Woody Allen reveals himself to be a hippie.


Also, somewhat late to the theaters after the film festival last year, A Girl Cut in Two. This IS a movie of stereotypes: older writer with a dark side conquers a young girl who seeks him for his "experience" and who is loved by a young, rich man who is petulant and jealous, etc. I am sure in some way that only the French can concoct and justify, this is a movie about something in the context of the history of French cinema, or Chabrol or whatever. This movie is saved by Ludivine Sagnier, who can save any movie by simply walking towards the camera, or walking away, or simply being.

Finally, there is the somewhat old movie: Beijing Bicycle. Bicycles may have a unique role in China, but this chinese movie falls short of what I imagine is its goal to remake the Italian classic: Ladri di biciclette (1948), where a man has his bicyle stolen, threatening his means of earning a living and everything else in his world. One should be born into this world as a baby, crying, but clutching a DVD of this Italian masterpiece. Forget the Beijing version.

Call for Ideas

In the past, when I had ideas/projects, I would work hard on them and when done, package, scrutinize and fix before I release them to my peers. Instead, these days I get my thoughts out soon as they pop up, as \beta's and tweak them later based on feedback! :) Anyway, here are two of my projects.

• Gagan Aggarwal and I are doing a tutorial in upcoming FOCS on Sponsored Search Auctions. I am going to focus on the role of budgets in ad campaigns: how they are spread across repeated auctions, multiple keywords, different search engines etc. In particular, my focus is of course on theoretical results about (a) optimizations (b) strategic behavior and dynamics of the game, and (c) creative formulations and approaches. If you have any suggestions for results, directions, references (in CS or Economics or Game Theory), please email or post. Help and advice will be much appreciated. Non-standard suggestions welcome.
  
• Anindya Ghose, David Pennock, Sergei Vassilviskii and I are organizing a NY area Computer Science and Economics Day (NYCE), to be held October 3, in, yes, NY. More details will come soon, but for now, think of it in the style of NY area theory or database days, or Bay Area ones. Our goal is to bring together researchers not only in CS, Economics, and Game Theory, but also in Marketing and Business and broadly others who analyze, understand, predict and affect economic activity on the Internet. Any suggestions, interest, recommendations etc. greatly welcome. Please email.
  

Thank you!

Graduate Algorithms, Fall 08

I needed to feel grounded, I needed to feel the inspiration for algorithms at a base level. So, I decided to teach a graduate algorithms course this fall. Many of you have taught such a course, even several times. There are terrific notes and homework exercises on the web. I am sure each of us would use our own notes to supplement the material out there. Question is, should one even recommend a textbook for the students? I feel like I am bumping against some ethical question here, but the question as it arose in mind was just technical, that is, are the books useful beyond the material on the web that is easily accessible?

ps: As an aside, what textbook to recommend? CLRS is rigorous, but bulky. Kleinberg-Tardos is new on the block, emphasizes the creative design part, but may be wordy. There is the somewhat dated, terse gem by Dexter Kozen. More recent, surprisingly under my radar, book by Dasgupta, Papadimitriou and Vazirani. Etc.

Missing Dagstuhl

I have been sick some, have family/personal travels in mind, and decided not to travel to the dagstuhl workshop on sublinear algorithms to be held next week. This is version 2, version 1 was in 2005. This workshop puts together streaming (sublinear space) and property testing (sublinear time) researchers, and as a side product, puts people who think algorithms (for solving a given problem, what novel techniques are needed?) with those who think complexity (can all problems in a class be tested in ... resources?). Of course, in reality, the division is not crisp, there are straddlers, but still, the workshop is a microcosm of the larger theory world, and I enjoyed the interaction the last time, and I am sure it will be great this time as well. Good luck!

Graph Secretary

We know the standard secretary problem: given n known items, they are presented in a random order; we need to either pick an item instantly as they are presented or lose it and our goal is to get the largest. The solution as many know is to observe the first n/e items and then pick the first that exceeds the largest of the first n/e elements; this has prob 1/e of being the largest. There is an exposition of the history of this problem here. This has been extended by Kleinberg, Babaioff et al, and others to graphs, matroids and more. Recently, Nitish Korula and Martin Pal have a nice result for the extension of the problem to online bipartite matching, with an elegant argument getting 8 approximation. Worth reading.

Olympian Description

To add to the adulatory sports writing, this one:

In obliterating his already absurd world record by 1.41 seconds – lowering the mark to 4:03.84 – Phelps was perfect. He was Tiger Woods at Augusta, Michael Jordan in Madison Square Garden. For an eyelash over four minutes, he owned Beijing’s Water Cube. And if it’s a sign of anything, he’ll own it all week long and leave Beijing with Fort Knox hanging from his neck.

And to my Brazilian fans out there, hope 8th month of 08 proves special:

An Olympic gold medal is the only significant title the five-time world champions have never won in soccer. The Brazilians won the silver medal twice, in 1984 in Los Angeles and in 1988 in Seoul, and the bronze in 1996 in Atlanta.

ps: News is, Bolt became the first person since Carl Lewis in 1984 to win both the 100 and 200 in the same Olympics, and the first ever to do it while breaking both world records. “You have people who are exceptions,” said Stephen Francis,... “You have Einstein. You have Isaac Newton. You have Beethoven. You have Usain Bolt. It’s not explainable how and what they do.”

pps: On Phelps. Russian swimmer Alexander Sukhorukov went on to describe Phelps as "just a normal person, from a different planet, a planet from a different galaxy."

Virtual whatever

Sometimes I feel I live in a virtual world of commutes and meetings. The real world of math and CS intrudes sometimes. The other day, I passed a pedestrian standing on a street corner, dressed in a shirt and tie, yelling into his phone, "No, I said eigenvalue, I said EIGENVALUE!". And yet another day, I was in the elevator and someone said, "So firefox parses until it finds a space to figure out how much storage to allocate and it was bombing because the string had no space!" Chuckles.

Anyway, Senator John McCain hosts a virtual town hall meeting, using, yeap, YouTube annotations.

In Photos

A long time ago I worked with Ted and Ritto, played with wireless systems, and met some cool people; one of them recently lamented not being able to see my shoes in my pictures. But let me distract him with my glasses, trains, trees and Venice. And to make amends, there are also pictures of paintings.

Traveling in UK

Traveling in UK is in some ways like traveling to CA. The locals are so persistent (or enthusiastic, in case of CA) with their accent that it is difficult to come back without acquiring a poor imitation: the enthusiastic people on the west coast perhaps do the High Rise Terminal, and the English a very liberal modification of R.P. Also, in some parts, UK not only has narrow streets, but also short houses that make you feel if you stretched on your feet, you can pat them on their heads.

On the bright side, people seem to have weaned themselves off fish-and-chips and bad Indian food (Indian food in UK plays the role of Chinese takeout in US for most part, and is awful, not even in the category of kebab's in Germany or pizza's in NY that are quick, toothsome street foods), and I saw genuine variety, and some coffee. Also, Banksy, the talented graffiti artist, seems to be thriving (see his work in Israel). Finally, as my taxi drove me to the airport, the Sun came out and beautiful, green rolling countryside was revealed. Nice!




On a personal side, I have a long running relationship with a piece of real estate: the Kenilworth Castle, visiting it several times under various guises for the past 13 years, all memories.

Communications of ACM: 08/08

Normally, when I see a copy of the CACM magazine in my mailbox with its color-infused cover and screaming headlines that scare, tease, or scar, I put it away with other junk mail. This time I looked over the 08/08 issue since it was supposed to be a major renovation as Stu explains in his farewell message and as Suresh blogged earlier. Yishay points to its glory days with: A theory of the learnable , by L. G. Valiant, 27(11), Nov 84. The new CACM may not be all that, still here are two articles worth reading:

• Yoav Shoham writes a tersely idiosyncratic description (Pg 74) of the interaction between game theory and computer science. He also proposes at least two large directions to theorize. This article is gem, a great example of writing for general *technical* audience: broad and bold!
• CTO Storage Roundtable (Pg 45) is a discussion by a few CS systems thinkers on storage (in particular, flash drives). It is a window into how one needs to rig up/tear down, measure, tradeoff, compromise and generally grasp complex issues and trends in ones mind for good systems research, something theoretical computer scientists rarely understand about the "messy" real life world. Since many of you will probably not read this article, let me quote this war story by Mary Baker I really liked: "Talk about noise. We have three TBs of storage at home. What used to be my linen closet is now the machine room. While storage appliances are supposed to be happy sitting in a standard home environment, with three of them, I get overheating failures. Our house isn't air-conditioned, but the line closet is. It doesn't matter how quiet the storage is because the air conditioner is really loud."
  

Finally, for dessert, Peter delights with a triptych of puzzles on Page 104. Next time I get CACM, I may immediately just flip to that last page!