Sunday, June 28, 2009

Change of Proceedings

I was browsing the FSTTCS conf site (this conf may be lost in the din of FOCS+STOC vs ICS+SLOGN wrestling, but is a solid technical conf), and noticed:


Accepted papers will be published as the proceedings of the Conference in the Leibniz International Proceedings in Informatics (LIPIcs) as a free, open, electronic archive with access to all. Authors will retain full rights over their work. The accepted papers will be licensed under the Creative Commons Attribution-Noncommercial-No Derivative Works 2.5 License: Creative Commons -NC-ND
FSTTCS, like STACS, WADS, ....., had standard LNCS proceedings. What changed?


Thursday, June 25, 2009

Michael Jackson

After a long day of work, I passed out at home on the couch while wondering what I should write for a SODA submission. At 2 AM I woke up to the music of Michael Jackson coming from outside. I went down to the streets and saw MJ was blaring from a SUV. Tourists, residents in pajamas, street vendors crawling from under their vending table on the sidewalk where they had gone to sleep, homeless, and the perennials who take over the Manhattan street at night joined in, wildly dancing. Even a snippet of his music is instantly recognizable, and everyone knows a MJ dance move or two. MJ bit and spit out words. Crowd rocked the SUV. Traffic altered itself to let the party be. As I left, a man was running to join in, carrying flowers he had surely plucked from some garden in the neighborhood. Leave it to MJ to inspire, in his life and his death, an instant homage at any moment.

ps: The summer I spent in LA in '95 would have been miserable without MJ's HIStory.

Thursday, June 18, 2009

How to pull it off

At the NY Area Theory Day, I started my talk with a story. When I was 10 years old, I played this game where the other party will repeatedly toss a coin, and I would predict the outcome each time. I developed a trick to predict correctly significantly more than 50% of the times. I told the trick to the audience and lost many of them who spent the rest of the talk wondering or disagreeing that it would work. Graham Cormode pointed out that besides the trick, the challenge is to pull it off since it required some worldly social skills.

I was reminded of this when I read about a scam in India. Roughly, via email solicitation, for a fee, someone delivers a trunk full of blackened currency to you. And then asks you for money to send you chemicals that will clean and resurrect the bills. Of course the bills turn out to be bogus. This scam seemed silly. I would have liked to see one in which you get delivered the trunk full of blackened currency free of charge, then you are asked to pay a small amount and get delivered a small quantity of chemicals that cleans and retrieves a few genuine or high quality bogus currency bill, and finally the victim gets hit for a larger batch, producing only counterfeit or bogus notes. No, I am not recommending such a scheme, just pointing out that the scheme could be made more nuanced.

Tuesday, June 16, 2009

BSP, Streams and Market Algorithms

Nothing could be common among these three topics! So, here is some uncorrelated information.
  • Google announced a graduate fellowship program sometime ago. There is one fellowship in Market Algorithms (read, eg, as Algorithmic Game Theory). Congratulations Nicolas Lambert! Full details here.
  • Lecture notes from my Data Streams course at Barbados with Andrew McGregor earlier this year is now posted at Denis's site, sincere thanks to the multitude of scribes and their incredible effort!
  • Greg Malewicz will be speaking at the joint industrial track between ACM PODC and ACM SPAA this August on a framework for massively parallel graph algorithms called Pregel. It is inspired by Valiant's Bulk Synchronous Model (BSP), and relates to MapReduce. Some info on this here, but more should be forthcoming at the conf.


Sunday, June 14, 2009


The CS students of Rutgers gave me a wonderful gift, the Award for Excellence in Graduate Teaching, for 2009. I taught the graduate algorithms course in the Fall semester that I truly enjoyed (all black board lectures, I find slides to be just sedatives). In Spring, I basically quarterbacked the advanced graduate algorithms course, focusing on algorithmic game theory. Mohammad Taghi and Aaron Jaggard taught a few lectures, Mangesh Gupte TAed, and the students scribed, surveyed and presented lot of the material. So, I got to learn too. Teaching and learning are the same sides of a coin. :)


Rajeev Motwani

An Indian TV station carried the sad news of Rajeev Motwani passing away. This is a sudden and terrible, terrible loss. My condolences to his family. There is a heartfelt editorial about him in The Hindu. In his memory, among many things small and big that each of us will do, now and in the future, ACM should launch a program focused on "mentoring", which, besides his brilliance and inspiration, is the dominant theme in various remembrances.

Travel to India

I traveled to India for a week.
  • India is in a strange relationship with electric power. In an otherwise quiet room, the electrical connections make crackling noise; you turn on the electric fan and it is noisy as a light helicopter. The 2nd grade textbook on how to use a computer says, first turn on the Uninterruptible Power Source (UPS), and second, turn on the computer!
  • I visited IIT, Mumbai. Like other college campuses in India, the IIT Mumbai campus has many old trees, bordering on being a forest. I gave a talk on Internet Ad Auctions. Since it was the summer, I expected very few, but the audience was fairly large and remained behind an extra 30 min with questions and discussions. The faculty at IIT Mumbai, Sundar Viswanathan in particular, has been a terrific conduit, mentoring and releasing a great set of theory CS researchers into the world (Subhash K., Moses C., ...).

On returning, I find NY a "quiet" city and eat Weiner Schnitzel to make up for the meatless week. Then I walked over to check out Youssou N'Dour's film at the IFC. I heard Youssou first in a fateful summer in the desert of NM in 94 and was blown away by the mbalax. I never knew or understood the lyrics. The movie reveals him to be first a social activist and later, an Islamic activist for his Sufi nation of Senegal, in the tradition of the griots.
ps: In a beautiful moment, as he walks down the sidewalk on his way to The Carnegie Hall to perform, and a NY taxi driver rolls down the window and calls out, "Youssou! I will be there for the evening performance".