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.

Gaussian Legend

Gauss kept a blog (a journal used to be called they were), and left some puzzles behind; also, he is the subject of stories retold. I heard two sorta jokes in which he makes an appearance:

• Q: What is the best known dad-son mathematician team? A: Gauss and his father.
• Q: Who was Seidel of Gauss-Seidel method? A: Gauss's programmer.
  

Linear complexity in External Memory

In the standard RAM model, one hits the sorting bottleneck of \Omega(n\log n) sometimes, and researchers find ways around by using say word operations that avoid comparisons. In the PRAM world, people tried to get around certain sorting bottleneck by "padded sorting", where items can appear in sorted order but with empty memory locations between them.

I was recently drawn to this issue when working with Gianni Franceschini and Roberto Grossi. Consider the external memory (just the vanilla version with input of size N on disk, internal memory of size M, and block size B) model. Even problems like permuting an array that takes O(N) time in the RAM model, and therefore, should ideally just take linear number O(N/B) of block accesses, seem to take essentially \Omega(N/B \log_{M/B} N/B) block accesses in the external memory model; sorting, convex hulls, MST and other problems then face similar bottleneck.

I think this is fundamental and one would think researchers would have by now figured out different ways to circumvent this bottleneck with additional assumptions on the input or on the model. But I haven't found anything. Any pointers?

ps: Btw, for the problem we were working on, we did find an algorithm with linear number O(N/B) of accesses. The algorithm is too long to be described in this blog.

On Shared Reading

Three notes on reading and sharing:

• I hear that the trains in St. Petersburg have seats on either side facing each other with a central open aisle for people to stand, presumably in two columns, each facing a seated column, and their backs to each other. This configuration lets the people who stand share in whatever the seated ones read, but one has to learn to read upside down and right to left. Apparently, now there is a suggestion to print books in two halves: each page will have the lower half printed normally and the upper half printed in reverse, bottom to top; this way, if you are standing or seated, you can read the book conveniently!
• I read somewhere that an Egyptian newspaper has a circulation of X millions and a readership of 2X millions a day.
  
• At Penn Station, in NY, there is a brotherhood of middle-aged men (never a woman) who salvage leftover NY Times from trash cans for personal reading. Most of them can afford to buy one, but there is some draw I suppose of snatched treasure when you retrieve a nice, complete paper, a gem, hardly read, found among the others soaked in coffee, hiding chewing gum and generally abandoned by the commuters. The cleaning staff help out. When they empty the trash, if they find such a gem, they leave it out on the can.
  

Barcode

I heard Leo Guibas talk the other day. It was refreshing a hear a talk that was about a research agenda, one with deep math and algorithmics, rather than an isolated result. He spoke for example about discovering the structure of given set of geometric objects, leading to a nice definition of a "bar code" that captured betti numbers and other topological properties; lot of the talk described his work with 3D shapes and objects and included some nifty demos (one on finding symmetry within the Coliseum was terrific). Must go, read these papers.

ps: As an aside, 2D barcodes encode more information than the standard 1D barcodes in products and are slowly finding fun applications.