Talks

I heard a few talks the past few days:

• Adam Smith spoke about nifty ideas of differential privacy and described the angst of formulating a workable notion of privacy preserving data analysis.
• Asaf Shapira spoke about property testing, starting with his general results for monotone graph properties for dense graph, and successively nailing down general results for hereditary properties for bounded degree graphs, minor-closed properties of sparse graphs, and testing graph expansion.
  
• Vahab Mirrokni spoke about approximation algorithms for submodular function optimization -- monotone, non-monotone and negative -- and a whirl of problems where they are, or can be found, or planted if one is clever.
  

I feel sated, but I must prepare now to give my upcoming talks (31,1).

Thursday evening Haiku

Came home, and decided to see a movie.
Discovered short films, half a block and 15 min away.
At the theater though, I fell asleep. Alas.
One hath it, grabs it, lets it get away with a nod.

ps: If I had more time, I would have written a haiku.

Fistful of $'s

Some $ factoids:

• [Clenched fist] There are many people out there now worried about their financial future. An observation: The NY Yankees paid more for A-Rod than JP Morgan paid for Bear Stearns.


• [Giving fist?] There are many algorithms conferences, they can each use say 10k sponsorship per year, and they now gather it from different corporations in a painful and inefficient way. Is there an algorithmus who has hit richness who can sponsor these in one swoop? A quick calculation shows this person must be quite rich.


• [Tight fist] I read an article sometime ago that now I can't seem to find: it was about a stage theater in the east village, one of those off... Broadway shows with a tiny cast, tinier venue. The salary paid to the cast for a day's performance: $15/person!
  

Improbable experiments

Here is the transcript of a speech by Illinois Sen. Barack Obama, delivered March 18, 2008, in Philadelphia. He speaks about the improbable experiment in democracy from 221 years ago, and the continuing experiment in race relations that is much younger and more raw. Politics aside, someone had to put the aspirations and struggles of the various races in a larger context, and this transcript does it, to some extent. Now, I wish someone would stand up and start the improbablest experiments of all, to erase borders between countries, let the notion of countries fade away, and let people just be, no passports.

Private query with ranking

The following problem has been studied: Alice has a bit array A and Bob has a query index i. Bob needs to lookup A[i]. The protocol needs to ensure that Alice is unaware of i and Bob remains unaware of everying except A[i].

Now imagine A is some search engine and Bob has a query word w. The problem to make the query without A knowing w. This may be related to the above problem if A[w] is say the ranked list of answers to the query w.

Going further, what if Bob's query comprised two words w_1 and w_2, or three words, and so on. Search engines may not precompute A array for all combinations of query words, and it is not just desirable to privately retrieve the ranked lists A[w_i] for each w_i in a query and try to combine the ranking on one's own. Is there a nice formulation of the problem of retrieving the ranked list of answers for the combination of the words in the query?

[This is a stream of consciousness question. I am not an expert in private queries or searching.]

My Moods

One has several moods.

• Some days I would feel like a big black lab I once knew that wore a red collar. I would chase distractions playfully like the lab used to do, breaking pots and peoples' backs with its stiff tail along the way.
• Some moments I have a research problem in my mind, and I am somewhere between the start and the end, not knowing if I was close or just bearing down on a false alarm, my brows will be furrowed, my head will ache with concentration, and my body will be twitching with nervous energy.
  
• Some moments I would wait for the train with a steady stance, a coding project on my mind, deliberating leaked memory and hanging threads, arranging them into rough priority buckets and working through the bugs in my head until I reach my desk and open multiple terminals.
  

Many Consolidated

Consolidated:

• I Like It. NY Times indulges academics with an article on the role of beer in the decline o research.
  

  In spite of his study, Dr. Grim, who said he would on occasion enjoy more than 12 beers in a night, is not on a campaign to decrease beer drinking among scientists. Why not? His answer: “I like it.”
  

• Crypto in the backyard. Things one discovers in the backyard: 5th theory of cryptography conference (TCC), 2008, at New York University, March 19--21.

• Green. In NY, St Patrick's day becomes a month. Guiness wants the day to be a national holiday. Bass has joined in.
  

Not quite a puzzle

You browse, detect an assistant professor's homepage, and discover the exhausting list of papers, PCs, CV, yaada yaada yaada and then hit a wall, a year, a date, after which there are only sporadic updates or none at all. Guess what happened? This is not a koan. :)

Book factoids

We researchers care about printed material, and books are big among us. Here are three book micro-episodes, more like odes to our rail systems:

• Julien Basch told me that he was in a subway car and while habitually checking out what others were reading, noticed the title, no kidding: Advanced Turkey Hunting.
  
• Ana Radovanovic told me she was busy reading a book, and looked up as she was about to leave, and the man sitting across from her was reading the same book. We could not confirm if they were reading the same page.
  
• I went on a trolley ride in San Francisco and amidst the rattle, the slanted light and moving shadows, sat a still, stylish woman, and if ever there would be a woman in your imagination to be reading Murakami, she would be the one, and she was reading Murakami.
  

Clustering Sets

I hear talks, referee papers, and space out trying to abstract larger problems during my days --- in many papers, good, bad and some pretty awful, there seems to be an attempt to solve the following: Given S_1, ..., S_k, each a set of say d dimensional points, find a suitable clustering of the sets. Yes, I realize the world does not need yet another clustering variant and yet another ''distance function''. Still, if someone has some nifty results/pointers, let me know.

Social Networking Ads

Sometime ago, I was deliriously sick in Kyoto, and R. Ravi saved me by reading maps, negotiating taxis, organizing the meal, and getting me back to my hotel, syrups and pills in hand. Last night, after some Jazz, Coffee and talking work with him --- futuristic formulations of economic games in internet advertising --- too hyper to immediately fall asleep, I remembered his recommendation of a NYer story. I am behind on catching up with NYers, but I hopped ahead to this story --- Raj, Bohemian --- in the current issue, and in some ways, felt rescued again. The story is in the ilk of Murakami or Bret Easton Ellis, but doesn't quite get quite as zany or suave. It is ultimately about advertising in social networks, the old fashioned kind, and makes this post definitely CS, if you fall asleep thinking about the underlying mechanisms.

Practice, Practice

I got to Carnegie Hall the easy way, the rain aside. A short cab ride and free tickets. Not to the main hall that was hosting Joan Osborne, but next door, to the smaller gem of Weill Recital Hall that hosted the Distinctive Debuts series. Martin Grubinger, the multipercussionist, was the performer with Per Rundberg on Piano. Martin thumped ones' eardrums to a frantic frequency and simmered them down with the magical marimbaphone (with multiple mallets in each of his hands) until there was near-silence and even the scratching of my pen on paper felt like an intrusion (videos, clips 3, 5). Brilliant, as the British youth would say. For the encore, he brought on some boyish playfulness --- no one can really be close to drums for any period of time without being playful --- and his father joined in, and one eventually understood how the little boy Martin could have started on this path for his life at the age of 5. I wrote off this week as a loss, took it off my books, because I had to miss my private tour of the Guggenheim museum on Thursday, but this friday evening performance saved the week.

Algorithms and Grand Engineering Challenges

I have some interaction, past and present, with the National Academy of Engineering (NAE), and it is always inspiring. An ongoing exercise at NAE is to gather thoughts about grand engineering challenges. You can take part in these polls, and participate in the discussions. The list is as follows:

Make solar energy economical Provide energy from fusion Provide access to clean water Reverse-engineer the brain Advance personalized learning Develop carbon sequestration methods Restore and improve urban Infrastructure

Engineer the tools of scientific discovery Advance health informatics Prevent nuclear terror Engineer better medicines Manage the nitrogen cycle Secure cyberspace Enhance virtual reality

I can immediately see a couple of these challenges where algorithms research will have an impact: secure cyberspace, health informatics, .. On second thought and beyond, I am sure algorithms research is needed to address each of these challenges, more directly in some cases than the others. May be that is really my problem: I like to see (applied) algorithms research as the central piece, with its own form and factor, but often, we are in the belly of a large beast. The beast gets the attention, it is easy to set it up, take it down, or play with it. The belly follows along. I struggle with this nearly every day.

In 6, no less, no more

Here is another homage to NYer. People's biographies, each in 6 words. Six words can tell a story. Lizzie Widdicombe can too, in sixers! “Well, I thought it was funny.”

Even Out

Some days the world puts a jinx on you. Things, small or big, don't go your way, and you can say it ain't so, but you can't pull yourself out. So, you take a break and read a note: Shouts and Murmurs discusses how things even out:

Try this simple test: flip a coin, over and over again, calling out “Heads!” or “Tails!” after each flip. Half the time people will ask you to please stop.

FYI: PODS08

PODS is a SODA-esque conference, seen from an Algorithmus's point of view. The accepted papers are listed here; there are papers on stream algorithms, clustering, cache-oblivious data structures and much more.

Call for Eccentricities

I heard about this mathematician who had a reputation for speaking fast, and was about to give his talk at the colloquium. The host requests him to define everything in English as well as in Russian, hoping to slow him down by a factor of 2. The mathematician says, "No problem. I was not going to define anything anyway."

We academics are eccentric (so are other professionals, but that is a different blog post). Eccentric in how we write papers, give talks, or just be. If you know good episodes of academic eccentricities, seen live or heard secondhand, let me know.