Yet Another DBLP feature

I used a feature in DBLP recently: type in "venue:FOCS" or SODA or whatever, and you get useful stats on the conference including the total number of papers, number of papers per year, most prolific authors and their count of papers, etc. Try this. Simple groupbys are so entertaining!

Making a prediction

Many days I have to walk into meetings, 30 min, 45 or an hour long, and am called on to make a bonding with near-strangers and accomplish something specific and significant before the meeting ends. This means one has to be able to read others as well as read themselves, all on a shot of adrenaline or may be coffee.

Things get more tricky when people ask you to read the future. So, here is a flippant prediction, for -\eps it is worth:

Generalized Second Price (GSP) auction will be to sponsored search research what PageRank has been and continues to be to web research.

Beaching

I can spend a long time watching the ocean, even though in their constant angst, the waves don't seem to achieve anything in particular, except to lap, retreat and try again. Watching the ocean gets better in the winter and I am maniacal enough to wade, if not outright swim or drown, in the frigid waters on an impulse. Here are fluevog shoes and custo shirts with me on the beach and jazz on the shore.

On Scheduling Conferences

One travels to SODA or STOC or FOCS on a Saturday and returns Tuesday night or Wednesday AM, and in the process, loses the weekend to the conf; include the monday holiday as well in the case of SODA 08 due to MLK day, and include friday evening too if you attend the workshops that precede the confs.

Why do we do it?

Why do we volunteer and take weekend off from our families, our personal and social lives, and do what is most certainly an important part of our work, either as a univ professor or as a researcher in an industrial lab, during the *official* non-working times? It can't any longer be for cheap saturday night stayovers. Avoid conflicts with teaching because our teaching responsibilities triumph our research?

Spirited Away

I have been away from home for a week, and sometimes I am called upon to play the NYer for bemusement, or other times, the situation wrestles that out of me and people are not amused, but most times, I am simply a NY taxpayer on travel. I collect my Times during the week thanks to Starbucks; when I get a chance, such as the weekend, I read quickly through the main sections, and surgically remove and retain the Arts sections for later.

A sad story of what is happening in Kenya: Wesly Ngetich, a (Duluth) Marathon winner, was killed by an arrow!! In a struggle that seems like a throwback of centuries, Wesly wanted to be a big man in the village, but for that, he needed to own 1000 cows; he had 150 and Marathon running was his way to get the rest.

I made the most of my time away, and spent the weekend on the beach, finding art, discovering artists (jeff faust shown here), and falling love with pens, this one in particular, now you know why I have to leave it behind in a store near the beach, several thousands miles away, and return home.

AGTCs

One's evolution can be traced to the A, G, T, and C's. My evolution has led me to research on Algorithmic Game Theory (AGT), and there is a growing list of AGT Conferences. The new one in the block is SAGT, to be held in Paderborn, Apr 30 -- May 2. The list of accepted papers is now available.

Research Funding

I was at SODA and discussions meandered through updates on problems I care about, new problems, gossip, intern and job applications, and most importantly, research funding. (By going short, I avoided discussions about my hair.) Yes, Google has a healthy program called Google Research Awards. The process is light-weight. Reach out to contacts you know, visit to give talks, learn from google researchers, educate them, and iterate on developing and sharing research ideas. Algorithms, Optimization, Auctions and much more.

Affordable Art

I support efforts, public or private, for affordable housing (housing for people making say less than 35k a year) in NYC, so the city remains the place to work, play and create, for everyone, not just the rich, resident, visiting or touristing. Likewise, I think there should be affordable art too.

I know people who will be willing to buy art for 100's of dollars (not 1000's or more), and I know artists who will be happy to sell at that prices. Still, it has been difficult to get these two parties to find each other, and to develop a nice market place. Partly it is because people don't search for art the way they search for books, gifts or trinkets. Any creative ideas here will have tremendous impact.

Meanwhile, there is the Cheap Art exhibition in Athens, Jan 16 -- 26. Cheap Art is a concept where art is both exhibited and made available for public purchase. The Cheap Art gallery in the bohemian neighbourhood of Exarchia plays host to this free annual…Then there is the amazing Hotel Art in Rome. Not in the affordable category, but definitely in the art category.

MapReduce Again

MapReduce is a parallel programming environment. It is successfully used at Google, and perhaps elsewhere. This has generated some inspiration, some frustration and alas, some angst.

• First some inspiration. The XLDB meeting at Stanford got scientists with *really* large scale data analyses problems to meet with academic researchers, corporate customers and vendors. A somewhat optimistic view there was that these applications needed MapReduce. In principle, a parallel shared-nothing programming system will be useful, but it seems to me that high energy physics and astronomy need sophisticated analyses, different from the kind of analyses at Google for which the design of MapReduce is optimized.
• Next the frustration. When an Engineer asks me how to find the shortest edit distance between two strings on a single processor machine, I can immediately point them to Dynamic Programming and a classic Algorithms textbook. As a theory+algorithms researcher, I am frustrated when an engineer asks me how to solve a graph problem on MapReduce and I cannot immediately point to a upper/lower bound or a usable theory. See initial theory here.
• Finally the angst. The database research community tends to be focused more on concepts and abstract solutions, and less on systems. A recent blog article describes some of their angst in not seeing the basic elements of a relational database in MapReduce. This angst is misplaced as comments and articles point out.

MapReduce is a working system that hands-on programmers find effective. More ideas from parallel computing, algorithms, relational databases or whatever that can make it more powerful, useful and more amenable to being analyzed and understood, will be good.

Some Distractions

I am unshaven, plowing through some writing, before leaving for SODA (San Francisco, no matter how many times one has been, one expects something to happen, maybe a new contact, a strange fruit or an unknown poem). Distractions:

• I was on the phone with Graham Cormode, when a FedEx delivery person buzzed the door and I wondered what they might deliver. GC quipped, "Your iPhone bill?"
• This AM, I woke up with sore throat and fever that sleep and pills couldn't cure and when I started typing, I couldn't find the "+" key on my keyboard. I admit, it is a reasonably new, somewhat strange keyboard and I was without coffee, but alas, what does it say about a pretend-mathematician (someone I know called us, theoretical computer scientists, thus)?
  
• Over dinner yesterday, I debated what was a good FOCS/STOC/theory paper, and as far as I can tell from the discussion, it has to be "important", but just said with a deeper, more drawn out voice, and a hand gesture of something substantial. No smileys.
  

Auto Journo

On a recent flight, I met Robert Collin, who introduced himself to me as an auto journalist. In my car-less, non-driver world, that means little. As I meandered through talking about top gear and car talk, Robert told me he has a blog hanging off his newspaper's homepage in Sweden, the land of Saab and Volvo (I am more familiar with Volver). As he spoke about his blog, I became more engaged and slowly more and more impressed. In his blog, he talks about cars, tires, traffic rules and their enforcement, alternative fuels, the impact of few hundred million new drivers from India and China, and many, many other topics, all of which suddenly made his blog so relevant and immediate, to everyone! Robert has a great journalistic personality and charm, a knack for choosing topics, framing his arguments, and a camera for supporting cast. So, not surprisingly, his blog is a big hit, and the swedish public seems to be tuning in, and learning a new attitude. What fun. My flight was a treat.

ps: Robert has a post in which I figure; he either calls me a genius or a geni, I don't know which, rubbing me the wrong way either way! :)

Late Birthday Wishes

Happy 70th birthday, Don Knuth! This is a post, arriving late and contrite, behind the slew of beautiful blog-homages (follow the thread from scott). Each of us can write volumes about his impact, and we would still be short.

One of his research threads I like (and explored a little in school and more now in my work) is on Mariages Stables. Consider n men with strict preference order for n women and vice versa, and the standard "deferred acceptance" algorithm that has men running to women down their preference list, getting tentatively accepted, getting rejected when higher preferred men come along, and eventually finding their stable mate, a bonding that cannot be broken for a better pairing with others simultaneously. This gives men-optimal stable matching M. An analogous algorithm that makes the women run produces women-optimal stable matching W. Knuth showed that M is the worst stable matching for women and W is the worst stable matching for the men. Formally, there is a lattice among matchings defined by the preference relations, and an algebra on the space of matchings gives nice properties of stable matchings.

Since the early days of work by Gale, Shapley, Knuth, Conway and others, the study of stable matchings --- algorithms, strategies, properties, and applications --- continues to thrive. See the book; there is even an upcoming workshop.

Burrows-Wheeler Transform (BWT): Provenance

Given string S[1..n], its Burrows-Wheeler transform T[1..n] is defined as follows. Consider the set of cyclic suffixes of S, ie., S[i, i+1, ..., n, 1, 2,...,i-1] for all i. Sort these strings lexicographically and output the last character in the ith string in this sorted order as T[i], for each i. Both S and T are of same size, but T has great properties:

1. T can be compressed very nicely by standard compressors, say run-length compressor,
   
2. S can be recovered from T (and the index j where S[1..n] ended up in the sort order) in nearly linear time.
   

(1) is hard to believe but there is simple intuition because if you consider two substrings that are far apart in S, you will notice that identical characters are brought together in T. Kosaraju, Manzini and others have formally analyzed the compression properties. (2) is hard to believe and works like magic, a gem in string matching algorithm literature. Thanks to researchers like Paolo Ferragina, Giovanni Manzini and others, BWT has become a very powerful tool, something for algorithm textbooks.

Btw, BWT has an intriguing provenance. Wheeler was an eccentric creator who intuited many algorithms, results and ideas. Burrows, who narrates this story (see page 199 here) in a TCS journal issue is much too modest and undersells his own considerable contribution in developing the original ideas into concrete, efficient algorithms and applications. Together they have produced a creative piece of work.

ps: I have been a voyeur. I liked BWT since the first time I saw it in 1994, have used it, maybe even extended it, but I still approach it as an outsider, curious, willing it hold it like a crystal between my fingers, rotate it, examine it, but eventually put it back on the table.

Art Demaine

Erik and Marty were in NY (alas, I didn't get to see them) dropping off their creations for a show at MoMA. Check out the pieces here.

Ranking Research(ers)

I hear about ranking all the time, ranking of universities, web search results, job candidates, peers for annual review, whatever. I have never seen a ranking that sates people.

Here is a ranking of researchers (it is keyed off DBLP and therefore has database+theory bias), part of a useful site for conference search. I don't know the underlying algorithms or premises. You can find interesting inversions in these lists and be tickled.

Instead, we can do some research. Is there an axiomatic approach to ranking? That is, can we state certain properties that ranking must satisfy (beyond total/partial ordering), and see if such rankings exist? One can say: there should be a significant difference between top 3 and below 10 in quality? different rankings obtained from projecting on different attributes should look similar? ranking should be relatively stable over time? Some principled study that goes beyond the machine learning formulation will be cool. It seems to me that the axioms acceptable for ranking universities is different from axioms acceptable for ranking say the researchers or job candidates or web search results.

Update: People asked me about the source of the ranking above. See here for a writeup by Kuhn and Wattenhofer. PageRank is involved.

Update 2: Was wondering if this list is similar to one you can obtain by a simple sort order, such as, a function of the number of publications, degree of publication graph, etc.

Endre wins AMS Steele Prize

Endre Szemeredi of Rutgers University wins the AMS Steele Prize for Seminal Contribution to Research for his paper "On sets of integers containing no k elements in arithmetic progression", Acta Arithmetica XXVII (1975), pages 199-245, that many of us know, use and admire. The result is a gem, and continues to be influential in a lot of math and theoretical CS around us.


ps: Here is a quote from Terence Tao from an article in UCLA News about his work on arithmetic progressions in primes and its relationship to Endre's work above:

To prove this, Tao and Green spent two years analyzing all four proofs of a theorem named for Hungarian mathematician Endre Szemerédi. Very few mathematicians understand all four proofs, and Szemerédi's theorem does not apply to prime numbers.

"We took Szemerédi's theorem and goosed it so that it handles primes," Tao said. "To do that, we borrowed from each of the four proofs to build an extended version of Szemerédi's theorem. Every time Ben and I got stuck, there was always an idea from one of the four proofs that we could somehow shoehorn into our argument."

Blogart

Someone (obviously clever, with a gift for words) called me Blogart. It is evocative in so many aspects that I am stunned, and will spend the rest of my life living upto it.

Meanwhile, here is some art, a Rothko-esque painting I did, and its reflection in a captivating mirror; no, it is not the face of a smiling robot.

Refereeing Papers

Papers, once written, never die. Think about it.

Sports Stars Almighty

I collect things. When I was little, it was notebooks and pens. Now that I am grown up, it is esoterics. For instance, I like collecting stories/jokes/vignettes that show how much sports fans adore their stars, and sometimes God becomes a part. Here are some examples. (Anybody got anything on Babe Ruth?)

Ex 1. Wayne Gretzky, The Great One.
A hockey fan dies and goes to heaven. He sees two teams practicing in the hockey rink, one team wearing red jerseys with BG and one wearing white with GG. So he asks Saint Peter what is going on. "That is our weekly hockey game between the Good Guys and the Bad Guys", Saint Peter says. Then, before the game begins, a God-like form descends on to the rink wearing a jersey with WG on the back amidst thunder and lightning. The fan is confused and looks at Saint Peter, who says, "Oh, that's God. He thinks he's Wayne Gretzky."

Ex 2. Sachin Tendulkar, Plays a game with a bat and a ball aka Cricket.
A banner: "Commit all your crimes when Sachin is batting," it read. "They will go unnoticed because even the Lord is watching."

Ex 3. His Airness, Michael Jordan.
Jordan never really belonged to Chicago. He is, undisputably, property of the world, of the tribesman in Kenya and the monk in Tibet and the cabbie in Paris, who hears the word Chicago and winks. "Ah, Michael Jordan."

Ex 4. Tiger Woods.
Jesus and St. Peter are playing golf, and Jesus is having a terrible day, but insists on playing the ball out of the woods, out of the sand trap, over and over, always saying the same thing “Tiger Woods plays them where they lay, I play them where they lay” Finally he knocks a ball into the water trap. St. Peter tries to talk him out of it, but he repeats “Tiger Woods plays them where they lay, I play them where they lay” He walks out on the water, looking for the ball. A guy walks up to St. Peter points and says “Hey look at that guy! Walking on water... Who does he think he is... Jesus Christ?” St. Peter sighs and says “No... He Thinks he’s Tiger Woods.”