What should be...

This should be my living room, this should be every living moment, ...



ps: The other day, I asked a neighbor in the building where they worked, and they said, "I manage the Strand bookstore", thereby making my day.

ESA 2008

FYI: ESA accepted papers here.

Tour De Brooklyn

Most explore Brooklyn, start and alas stop, with its Manhattan-esque parts (you know, Heights, Park Slope, the by-now-well-hewed Williamsburg, Prospect Park, Museum and the adventurous ones, the BAM). Beyond it, Brooklyn is a borough of astounding murals, and more.




Today, I went on the bike tour of Brooklyn. The borough president Marty Markovitz, in his true Brooklyn accent, started us off. The tour went through a rainbow of neighborhoods: Atlantic yards, Crown Heights, Bed-Sty, Eastern Parkway, Bushwick, and curiously the Navy yard. I went to the Navy Yard yesterday and the security did not let me in or take pictures. Today I rode in with several thousands through a different entrance and rode out waving to that same security person with a smile! Brooklyn is also the borough where the riders would urge the cops on duty to come, join, and the cops--even the ones with the shades--will smile and decline. A bakery would exude great smell and the knowledgable rider will tell stories about the goodies in the bakery we were leaving behind. Cars stopped at the light will roll down their window and blare reggae to cheer us, and people will clap for no reason and ask me as I rode by, "Bro, what is the ride for?". For da Brook'lyn.

Self-Help

Once it used to be known that if you wanted to pick up women, you went to the self-help section of Borders (or B&N), to catch the ones just getting out of a breakup. Presumably there is similar wisdom for picking up men as well (IKEA: finding furniture after moving out of ex's place?).

I had a strange attack of self-help. I dreamt that I, the novice, spoke to me, the consummate writer, and asked for writing advice. The consummate me says, "Respect the intelligence of your readers, and let go." I, the novice, in dream or in reality have no problem with the former, but have difficulty letting go. Must practice.

ps: A colleague who will not be mentioned here, but who will be recognized by the coterie around the beer cans some time ago and very far away from the eastern seaboard, said he dreamt he was an algorithm and recognized in his dream that he was deterministic!

pps: This post is an homage to the anonymous commenter who said an earlier post was Godelian.

Two papers

I played around this morning and before my first cup of coffee, set up this page and included two papers still in the publishing pipeline, one a set of problems on Ad Algorithms and other an overview of theory at Google. The page is insipid, and I will revisit it after some coffee, and a few days.

Quixote Magic

Don Quixote by Miguel de Cervantes gets reexamined repeatedly in surrealistic paintings (appearing as a theme in Dali's many paintings) and magical realistic writings (Borges's little gem is one of my faves; Paul Auster, in a brilliant piece, chases the explanation of who wrote Dan Quixote). Every once in a while, I can understand the modern life only in quixotic ways described in this 1605 novel.

Ranking vs Classification

When I began to blog, I feared that I will not have time to read and understand a lot of others' papers in any detail to have a pipeline of general results of interest to blog about with technical content, and that I would eventually end up talking about my own results disproportionately often. I continue to have this fear, and am glad when I get to blog about others' work.

There is an interesting recent result due to Ailon and Mohri. The authors reduce the problem of learning a ranking among objects to that of pairwise classification. The reduction is randomized, takes O(nlog n) calls, and the quality (formalized as regret) is no worse. The reduction is like quicksort and connotes the work of Ailon, Charikar and Newman for minimum feedback arcset for tournaments. This result improves earlier work that gave up a factor of 2 in quality and used O(n^2) pairwise classifications. The result is an example of interesting, foundational theory, and more reductions of this sort in machine learning will be of great interest.

Bicycle and Theory Visions

Blogging is not like riding a bicycle, because you do forget and lose the rhythm if you don't blog for a while, or so I realized. Let me get back on with a comment on the Visions for TCS workshop.

Meetings like this get a lot of smart researchers together: they agonize, organize their thoughts and generate a thoughtful writeup which is typically a summary of the recent past with a slight peek at the future. Such meetings are much-needed, and one is grateful that top researchers care and free up time to do this. This exercise, prescient or not, gives us a top down sense of orderly progression of research.

In the other model (the Levin model?), my preferred model, research springs up in a distributed way, bottom up, and while our visions point one way, these nuggets sprout, break the ground into lumps, spread like weed in entirely different ways, and ultimately make it to the writeup above in their middle age!

Top down or bottom up? It reminds me of an Yiddish story of Seychel and Mazel competing to see who is more important in life. If you have one, you want the other. It is like business consultants: if you have a centralized company, they ask you to distribute it to be more flexible; if you have a distributed company, they ask you to centralize it for efficiency.

Interviews

You know the joke about this guy who goes to a small town bar with a friend, and discovers that the locals have assigned a number to each of their jokes: when they want to tell a joke, they just call out a number (eg., "42") and people laugh. This joke has a couple of twisted endings (1, joke 118 in 2).

I feel that way when interviewees answer the question: Why do you want to work for a corporate lab X? Answers are (a) I want to have impact, (b) I want to work on real problems, (c) I want to have access to the data. The answers are simply sound bites. We should have a universal list of these answers and answer to other questions like "Do you prefer academia or research lab?" and just call out the numbers.

On a serious side, when I interview a candidate (for univ, resrch lab, engineering, startup or whatever), I do a lot of homework on the candidate and come prepared. I like to see the candidates do their homework too. And much as in research, I am looking for the unique aspects of the answers.

ps: In Wodehouse's story, "Best Seller", Egbert is sent on a suicide mission to interview his ex-fiance, a female romance novel (bilge!) writer, for a Christmas Special and taking a deep breath, he begins the interview: "Are you fond of dogs, Miss Pembury?" he asked. "I adore them," said Evangeline. "I should like, a little later, if I may," said Egbert, "to secure a snapshot of you being kind to a dog. Our readers appreciate these human touches." "Oh Quite," said Evangeline. "I will send out for a dog. I love dogs--and flowers." "You are happiest among flowers, no doubt?" "On the whole, yes." "You somethimes think they are the souls of little children who have died in their innocence?" "Frequently." "And now," said Egbert, licking the tip of his pencil, "perhaps, you would tell me something about your ideals. How are the ideals?"

Journal and Focus

To journal a paper or not, one asks this question many times. If you answer yes, you have to figure out a suitable journal. Some turn of events led me to check out the journal: GAMES AND ECONOMIC BEHAVIOR. (Quoted) Research Areas Include:
• Game theory • Economics • Political science • Biology • Computer science • Mathematics • Psychology

ps: Ok, this needs a punchline: Talk about being the Journal of All Trades.

Compressed sensing: L0, L2 and no L1.

I heard Joel Tropp talk recently on his result with Deanna Needell. The problem involves measuring the signal with a small number of inner products and using these measurements to pick the linear combination of a small number of basis vectors that approximates the signal the best. Group testing and greedy methods (L0 approach) or linear programming (L1) have been in vogue recently. A different method (recent ex) iteratively refines a set of vectors (L0) and each time finds best linear combination by least squares optimization (L2). The Needell and Tropp result follows this approach, but uses the structural properties of the set of measurements to get nice bounds for the problem; this method may be among the most suitable for current technologies that perform these measurements.

Cirque Act

I have a friend who wants to only work for one of two companies in the world. One of those companies is Cirque Du Soleil. Here is one of my faves, watch it on IMAX and 3D, when you get a chance. Sometimes in life, when I am confronted with Art, I feel like the spectator youth in this video, willing to hop over water for a close look, grab a magical hat and pursue whatever the Art wills.

Telecom in Halifax

Canada, to a casual, occasional, and ultra short term visitor like me, is a country finding itself between bits of Britain, France and undoubtedly US. I felt transplanted when the locals in Halifax spoke (in English and French) of Royalists, of growing up in Dartmouth and New Brunswick or of the car dealership in the Chester county. Also, something about the weird geography we learn as kids (you grow up in country X and continue to see the world map as this multicolored object centered on X, no matter what X, because that is what school books show you), I had a feeling I was on an edge of the world when I was in Halifax. And what was reassuring was that there was a large community of researchers there in communications and computing, that the Canadian government supported research there through innovation funds and would send ministry representatives to support the conference, and that the participants would all speak our cult language of problems, proofs and experiments.

Travel

I walked in to yet another hotel room, switched on the TV and the heard the same LodgeNet woman's voice I have heard in three different hotels in the past week, "Welcome to Y. Thank you for choosing X hotel. We hope you enjoy your stay with us". And she keeps repeating her message.

Anyway, I am giving a talk at the Communication Networks and Services Research conference (CNSR 2008) at Halifax, Nova Scotia. It looks like a conference of telecom researchers.

Hand me down quote

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.

GTA 4 comes home

Life is complicated. I've killed people, smuggled people, sold people. Perhaps here, things will be different.

So, Nico says as he sails into the Liberty City, a virtual world dead ringer for NYC in GTA 4. The local newspaper has a brilliant review of the game, in A Strange City Called Home. The reviewer tries to find his favorite and familar spots and fails. :)

Faced with this catastrophic revelation, I turned to a life of crime. I hijacked cars and crashed them into traffic poles; I raced a motorcycle through Central Park and dismounted just before the bike plunged into the lake (my way of letting the boathouse know I won’t be holding my wedding reception there). I jumped off the observation deck of the Empire State Building, just because I could, though I took no pleasure from the sickening scream my character let out, nor the sound of his jacket flapping in the wind, 86 stories to the ground.

I am off to the stores to buy GTA 4.

Travel Moments

There are two kinds of moments I like as a Researcher.

You travel to visit a colleague, discuss a myraid of problems, maybe have dinner and go to your hotel. Then, you get to refine one of the problems a little bit, sleep, may be dream the problem a bit, and you wake up, sit on a chair, reflect on the problem and slowly some definitions emerge, an idea peeks through, may be a calculation pops out. If you are lucky, by the time you are showered, had the horrible breakfast in most of the hotels and see your colleague, the process would have led to some clarity. What I am talking about is an engagement with a morass of problems and thoughts, followed by a disengagement and solitude that eventually leads to clarity and then the re-engagement.

Check out Some Portraits

You are a traveler and an alien in most parts of the world. You wait for security screen, wait for bags, or wait for the flight. Others who wait may listen to music, do Excel, or read books. We (theory) researchers have a unique advantage. We can simply let ourselves physically wait, but mentally step aside into the world of problems and puzzles. I space out like that and when I come out of it, find myself yanking on my beard or massaging the back of my neck and realize the stranger woman sitting across from me in the airport lounge is staring at me. What I am talking about is the ability to snatch moments of solitude while the world sloshes around you and you are part of it, only physically.

Food and Photographs

In Tel Aviv, the incredibly charming TV chef and publisher Gil Hovav (UK media cites him as "Israel’s answer to Jamie Oliver") introduced me to the exquisite food at Herbert Samuel by Chef Jonathan Roshfeld. A lot of time searching the web and I could not find an article/video/photo that captures the zany genius of Gil or the sublime food of Jonathan. I am not talking about writing that just describes their work, I am talking about an article that becomes an art in itself as it captures the mood and the moment with them.

ps: If you spend time web searching, you will find something. My discovery: a couple who photograph chefs. This article has a couple of sparkling lines:

• "In the new book, we explore movement," explains Shavit. "The fish will also be moving. It will be wet and dirty."
• "I was a paparazzo child," he recalls. "My subjects were the Hasidic grand rabbis."
  

ICGT, Tel Aviv

At Tel Aviv, on the 26th floor of Levinstein tower, we gathered to discuss Computational Game Theory during ICGT 3 (there was BAGT 5 sometime ago, and SAGT 1 last week).

• Uri Feige spoke about different axiomatic systems for trust-based recommendations and showed axiom sets that uniquely yielded random-walk or mincut or majority-of-majority voting based solutions. Puts some theory muscle behind these intuitive approaches. Cool stuff!
• Aviv Zohar spoke about game-theory of interdomain routing. This is not my area of research, but it was good to see the abstract ways to reason wrt messy protocols like BGP.
  
• Itai Ashlagi spoke about how to choose between competing auctions (say advertise on site G and Y or only G or only Y). I really liked this work. It takes a lot of formulation to even address this question in principle, and Itai gave a nice, detailed talk.
  
• Moni Naor gave a fantastic talk on rational secret sharing, and in general, game-theory + cryptography (didn't get to the part about using games to extract randomness). Very exciting.
  

This is Israel, so the total intellectual strength in any meeting is high; on top of that, the organizers managed to pull together a terrific audience, and for a day, I was happy to soak in the gestalt.