Must do

Some days you have to rip out your schedule, grab a canvas and paint something dark, or at least grey.

Shotgun Research

Paul Beame mentioned being hiring manager at a research lab as a test of executive skills on the research side. That got me distracted with an unique form of research found in labs.

You do what I call "Shotgun Research" at some labs. You go into a meeting with a person you haven't met, and in the following one hour, you have to bond with them, size them up, get their respect, quickly formulate a problem that will match the interests of both of you, and put in place the skeleton of a novel idea or direction or even a claim. Then before the clock interferes you have to lay the foundation for how the direction will be developed, and leave with a social contract. Later of course you will refine the problem, nudge the direction and rewrite the claims, and have to do the sweat work to make it a project or a paper, but the initial shotgun meeting is the key.

I modelled shotgun research after shotgun sequencing in genomics which wiki tells me is "named by analogy with the rapidly-expanding, quasi-random firing pattern of a shotgun." Quasi-random is right. Shotgun research does not lead to FOCS/STOC papers., but leads you to problems which with serious sweat may become one.

Hot dogs and SoCG

Jeff Erickson announces the call for papers for SoCG. He says, "Paper submissions are due December 1. ... submit a paper or three!"

Let me piggyback on that and announce the opening of a new store in my neighborhood: NY Hot Dogs and Coffee. That is right, Coffee and Croissants, or Hot Dogs and Papaya Juice are combos of the past. Strip away the silly partners (croissants and papaya juice) and you have the perfect, stable marriage: hot dogs and coffee.

Hand me down quote, and hand me the explanation

Some time ago, I blogged: From Kamal Jain to Christos Papadimitriou and via Moni Naor comes this modern take on the Turing test for the crowd:

If your laptop can't find it, neither can the market.

What did Kamal mean? He responds: A "rational" entity in theoretical economics is nothing but a Turing machine. So this quote basically means that at least one of the following must be false: Entities are rational; Economics system reach equilibrium efficiently; Equilibrium is not hard to compute by a Turing machine; In practice generic cases do not appear.If computer scientists have some evidence that computing Nash equilibrium is hard, then it puts the ball in economists court. So in theory economists should convey at least one of the following message:

1. Entities are not fully rational, and therefore it is ian interesting question to study their irrationality. Though modeling would be hard, because a modeled irrationality may again look like a Turing machine (bounded rationality).
2. Economics system may not reach equilibrium. If economics system converge towards theoretical equilibrium, then that again makes the market dynamics a computational model.
3. Provide novel computational insights to computer scientists! Because in principle, one can simulate a set of rational entities by a bunch of laptops.
   
4. Claim that the realistic situations are not generic. Well, in that case it is intersting to model the realistic situation. That again brings us to a computational model.

All in all, computational models are not forever ignorable to study economics systems. Or in some sense, algorithmic game theory is more realistic than algorithm-less game theory.

Abie raps

Abie --- Abraham Flaxman --- comes at us blogging here from Seattle. I am looking forward to posts on random graphs, economics, research in health metrics, and other (I hope un-)related topics.

Mike66, Remembered.

Mike66, from the way Mike looked, was like Mike30's. The opening speaker quipped how Mike got U. Warwick to build a physical bridge between the Math and CS depts.

Leslie Valiant gave the first technical talk. His basic premise is that evolution is an algorithmic process and we need a model that will converge in rate commensurate with the growth rate of DNAs and explain the complexity of current organisms. He presented a model that is contained in PAC learning. Michael Fischer, a long term collaborator of Mike, followed and spoke about the think-a-dot puzzle, its states, strings it generates, and their properties. Mike used this construct in 70's to teach finite state machines. Graham Cormode started with theMunro+Paterson result from 80's, the earliest truly streaming result, and spoke about medians, in small space, small number of passes, whatever.

Mike designed and released a puzzle weeks earlier. He described the solutions over time as they arrived, using pseudonyms, and the finale revealed that Pie Goly who solved the Pie Gon puzzle was Vaughan Pratt.

Don Knuth charmingly started with simple Y functions and when he was done, they had become as detailed, intimidating and rich as multi-starred problems in his book. For appetizer, he showed how to get 66 from digits 1,...,9 using binary operations +,-,*,/. (He wrote a program to evaluate all such expressions.) Cenk Sahinalp revealed a secret: you can beat Mike by cheating, and demonstrated how to improve the classic Masek-Paterson edit distance computation, by changing the problem and using approximations. Uri Zwick, in a short, explosive pst, described the Overhang result, an ode to proof by pictures! Kurt Melhorn made an optimization problem out of assigning review papers to PC members.

There were other great talks of course. What remains on my mind is that researchers came from Tokyo, Boston and even non-baseball towns. They came to describe their interaction with Mike which in most cases had an aspect of puzzle solving. So, differences in age, generation and research area faded away; only the love for problems, puzzles and proofs remained floating. I think everyone was happy with that.




Thanks to Artur Czumaj, Leslie Goldberg and Uri Zwick for pulling this together. The artwork is sculpture by Le Page. In a social context, I enjoyed discussing the state of the world with the ever-reasoning Josep Diaz, and sharpening each others' arguments.

Marriages

Maximum weighted bipartite matching is a well-known optimization problem. Inspired (loosely) by its emergence in sponsored search, researchers have studied their exploration + exploitation versions where nodes or edges may arrive in some order and some weights are observed before committing to the matching (eg., as in graph secretary problems).

I would like to see similar formulations for the well-known stable marriages problem. This formulation should consider the gradual revealing of preferences. What FOCS/STOC/SODA style formulation will lead to pretty math and powerful technical results, motivations entirely aside?

Three photos

Tomatoes I buy, no two alike	Imitating Suresh from a while ago	Plates, graffiti inspired

ps: FYI

Being an Executive in Research

Events around us confront the question, how does an executive choose and appoint people to help them in their task? Fairly and by merit, or by gut and based on friendship, or by balancing quotas and quirks. There may even be disagreement on which style is better.

This led me to wonder if we (in research) face such quandaries. There are executives in academia and its administration (presidents, provosts vs the proletariat professors) and I am sure they do, like executives in other fields, but I am talking about executives in our research community.

One of the few occasions researchers get to be executives (we execute many tasks, but mostly as civil servants, or truth seekers, or as peer-driven organisms) is as the PC chair of a conference. Do we fare well?

A SODA Review

I got the following reviews for a paper I submitted to SODA 09 (accepted papers).

• Reviewer 1: ... It's good old-fashioned algorithmics....So I don't think this paper introduces any really new insights, but it was a pleasure to read. I think that many people in the SODA audience will enjoy the talk.
• Reviewer 2: This is an excellent work on .... I strongly propose to accept it. ...
• Reviewer 3: ... The approach has some innovation, and shows a lot of skill in sidestepping costly aspects. ...
• Reviewer 4: ... Thus it (the problem) is important. The algorithm is elegant ... and interesting. Therefore the paper should be accepted.

Getting 4 full reviews, none negative, wow. I sincerely thank the reviewers. Those who live by anonymity, have to gather their accolades and thanks in anonymity!

Afterthought: No, the paper was not accepted. Beware, the above feedback is not complete since the PC discussions are not public.

Algorithms in Action

"The so-called algorithmic trading mechanisms, which buy and sell stocks based on news headlines and earnings data, were responsible for roughly a quarter of NYSE trades in the last week of August." -- from WSJ article, B3, Sept 10, 2008. Now, I don't think these are algorithms and analyses we grapple with (say, sparsest cut, fractional cascading or factoring), and I am sure there is thresholded logic, information retrieval, machine learning, adaptive control, even some hearty heuristics embedded in these mechanisms. But if there were to be a certified, bonded, insured algorithms-engineer ever, this would be their responsiblity. Wow.

Below is an anachronistic quote from Hoover:
"The great liability of the engineer compared to men of other professions is that his works are out in the open where all can see them. His acts, step by step, are in hard substance. He cannot bury his mistakes in the grave like the doctors. He cannot argue them into thin air or blame the judge like the lawyers. He cannot, like the architects, cover his failures with trees and vines. He cannot, like the politicians, screen his shortcomings by blaming his opponents and hope that the people will forget. The engineer simply cannot deny that he did it. If his works do not work, he is darned. That is the phantasmagoria that haunts his nights and dogs his days. He comes from the job at the end of the day resolved to calculate it again. He wakes in the night in a cold sweat and puts something on paper that looks silly in the morning. All day he shivers at the thought of the bugs which will inevitably appear to jolt his smooth consummation."

Homing

All maps are (useful) distortions. In particular, the ones we carry in our heads. I carry a map of NY that has the village as its center with the island floating out to infinity N-S. My office is on a floor that has been mapped to Manhattan and falls on the purported village.

We carry these distortions with us and map the new lands to our homes (London is like Gramercy Park South, etc). I went bicycling the boroughs last weekend, part of the century tour, and made it may be 70 miles; all along, I swear, people saw parts of their home, in this case Westchester (Yonkers to Chappaqua), reflected in Brooklyn and Queens as we rode.

Exporting Jazz

A friend who works for Wynton Marsalis (the great) of Jazz on Lincoln Center (jalc) described projects at jalc supported by govt grants that send Jazz performers abroad to expose other countries to Jazz, or in my words, Jazz diplomacy (I am tempted to use the word diplomatics which is so wrong in meaning, and so right in cadence).

Alfred Spector, ever the Socratic thinker, asked, just how does one export Jazz? Indeed. Jazz is not a well-dressed quartet in a shiny room. It is smoky rooms, dirty drinking glasses, dilapidated chairs, voices raspy from drinks, raspier instruments, and men with a few alimony checks under their belts, indeed, men who need belts. How does one transplant this from the basement of Smalls in the village to the barren Kazakhstan?

WINE 08 The Accepteds

Accepted papers for the WINE 2008 conference is here. Enjoy the reading.

NYCE 08

Details of the first NY Computer Science and Economics Day (NYCE Day) are out. Please forward this information to colleagues and students in CS, Economics, OR, Marketing and Business schools who might be interested.

Binging Contd.

When one confesses to binging, one typically holds back something out of extra guilt. Like when you tell people that you binge ate, you leave out the fried chicken or tatsuta age. I held back something when I said I binged on American fiction: an early nineties short story collection called Jesus Son, by Denis Johnson. Some of you may have seen the movie, still you should forget that and just read the collection. I read a few pieces before (Dundun, Car crash while hitchhiking), but felt guilty because it is inexplicable having read those, I didn't seek and grab the collection to read the others. Now I have, and what fun. The title is from Lou Reed's "Heroin". The author borrows that in his writing, dreams and hallucinations (or was it reality?); he is the "dark poet of drugs, drink, and alienation", and describes some vicious, blinding instances.

ps: Rick Bass says about the book: "I read these stories with great thrill --- they cleaned out the tired old ways of the mind like a 50000-volt kick to the head; they cleared my sinuses. ... These stories terrify, warn and instruct."

A Q.

Q: Does a researcher exhibit different styles in writing single-authored vs multi-authored papers?

Assuming one can collect all the publications and publication data, holding down the different variables and doing any principled analysis on extremely sparse signals one faces will be a challenge, so we may just have to go with anecdotal support! :)

Momentum Rider

Given that world is not flat, one has to negotiate the gradients, up or down. A casual bicycle ride to the George Washington Bridge led to a stop at a bakery and discovery of Russian snacks at Washington heights, and that in turn, impromptu, led me to ride all the way to Nyack, NY, a distance of about 30 miles, on a mountain bike with slime.

I am a momentum rider. I dislike steady climbs or descends, and find them boring. I like sharp ups and downs, riding hard going downhill until pedalling has no effect on the bike at its max speed, or inching up the slope when again hard pedalling yields very little progress. I live on momentum too it would seem, eating 1000's of calories during the week and burning them in a day on the weekend.

The lesson from the chautauqua's in The Zen and the Art of Motorcycle Maintenance may have been that one should pace oneself while hiking, or be tidy in organizing one's mind and their motorcycle repair shop. Instead, I learned to go with the momentum.