Deep Theory Bench

There is a lot of discussion about the top conferences/journals in algorithms/theory, but one of the things I point out to others is the "deep theory bench" (baseball speak, check out the dictionary). For every slugger at the plate hitting NY Times homers, there are dozens of highly talented players on the bench with great solid results, and at a suitable moment in the sun, capable of hitting the ball out of the park.

Today

At any given moment and in any given 3 block pixel of New York, something happens. A subcult of people take part, driven by interest, pulled in by proximity, or whatever. One is reminded of E. B. White's Here is New York. Today, here is an example of an NY pixel: Dog Days Brunch presented by Leashes and Lovers, where one can brunch, booze, boogie and bow wow! (Dog NOT required).

Good Primes

Background: The Karp-Rabin fingerprint fp(s) of a binary string s[1..k] = sum_{i=1}^{k} s[i] 2^{k-i} mod p, where p is a prime. Fingerprints are good for comparing strings.

Given a binary string t[1..n] and a prime p, p is said to be good for t if for all i, j and k, we have t[i,i+k]=t[j,j+k] iff fp(t[i,i+k])=fp(t[j,j+k]). Our problem is to verify if p is good for t. It is trivial to verify this in O(n^2) time, but the goal is to (a) design a faster--linear time--deterministic algorithm, or (b) sublinear time randomized algorithm which is approximately correct, a la property testing algorithms.

[Btw, Karp-Rabin analysis shows that there are so many good primes in the range polynomial in n that choosing a random prime will be good with high probability. This is the property a lot of string matching algorithms use.]

Best of The New Yorker

The New Yorker has been running a Cartoon Caption Contest. They publish a cartoon without a caption, solicit apt captions from readers, show a list of three finalists and eventually settle on the winner. I wanted to set up a blog so the ones who did not make the list can publish their entries in what may become a public, secondary contest. But the rules say, "All entries become the property of The New Yorker and will not be acknowledged or returned." So, alas, no secondary lives for these entries. [The rules don't seem to forbid simultaneous submission of an entry to two different venues; wonder how property laws work.] However, there is a different shadow contest going on for the worst captions for these cartoons.

Arkas

Christina Fragouli introduced me to Arkas, the Greek Cartoonist, and recently, Petros and Perry added to the fire by giving me a couple of his books in English. My favorite is the story of dad and son sparrows, abandoned by the mother who ran (flew?) away with her lover swallow. The dad and son sparrows spend their dysfunctional time amidst the cityscape, the loser dad trying to play the perfect father and the clever son ridiculing him incessantly. It is as funny as the old classic, Married with Children.

Notebooks

I usually walk around with what may look like a printed book, but in fact, is a notebook with acid-free white paper, plain. I write down ideas, to-do lists and telephone numbers in standard format, i.e., scraggy polylines, and occasionally put down sketches, math, and graffiti in straying fonts and boxy formats. The binding is fine, the cover is in bright colors, and the feel has to live upto the look. The commonly seen Barnes and Nobles' Hemingway- inspired moleskin sketchbook is too small for the math and will not do in any of the other metric. I have been happy with the easily available Ordning & Reda's red, black, brown or green. I sometime stray into Italian and do orange and purple Fabriano's. Recently I discovered the Legatoria Artistica thanks to Luigi Laura (the one and only, from Roma, enjoy 4 years of soccer reign dude!), and will begin with a new one in a couple of months. I can hardly wait. Handmade and leather-bound, my notes may one day live upto the notebook.

Word Play

There are true NY movies, whether they are billed as such or not. Plenty of them. The Godfather is one for instance. After several near-misses, I managed to watch the move Word Play last night. It is a documentary about personalities who solve crossword puzzles. The movie has characters from all across the country, but at heart, it is a NY movie. And NY Times reigns (after the bashing they have taken recently, I am happy to pay money to see a movie where they star, or take out a subsription or two). The movie is a honest window into the geekdom of puzzlers and celebrities who are hooked (my fave Mike Mussina of Yankees), ie, the ones who will get the tome that is Sunday Times, rummage through it hurriedly, retrieve the section that carries the puzzle, discard the rest of the tome, fold past the colorful dancers and paintings that are featured and settle on the black and white boxes and their symmetry with a pencil in hand. Sinful satisfaction.

Linear L_2 Regression: Past and Present

The linear least squares fit problem is the following. Given an n X d, n >d, matrix A of real values and a d dimensional vector b, minimize ||b-Ax||_2. It has a past most of us know. It can be solved in O(nd^2) time. Petros Drineas, Michael Mahoney and I had a SODA paper that showed that if you sampled poly(1/\eps,d) rows from A and b and solved the induced problem, one gets 1+\eps approximation to the problem. Unfortunately, the sampling was somewhat complicated and could not be done in o(nd^2) time. We knew that instead of sampling, if one "sketches" A, that is, takes poly(1/\ep,d) random linear combinations of rows of A and b, the same claim would follow, but it still did not improve the running time. Tamás Sarlós makes a very nice observation in his paper in upcoming FOCS that by plugging in Fast Johnson-Lindenstrauss Transform of Ailon and Chazelle from STOC06 and squeezing the bounds, this sketching method in fact can be run in O(nd log n) time. Kol Hakavod, Tamás!

Poetry in some motion

Othello, Act III, Scene 3:

Who steals my purse steals trash; 'tis something, nothing;
'Twas mine, 'tis his, and has been slave to thousands:
But he that filches from me my good name
Robs me of that which not enriches him
And makes me poor indeed.

NY subway has a "Poetry in Motion" series where they post pieces of poems
by school children, Shakespeare or whatever. The subway itself is more like
a Poetry Slam, a hip hop version of the sedate words posted in the car. You stand
in the subway, tune out its thundering run, screeching brakes, and the sideways lurch,
stare at nothing, reflect on the day, and catch a piece of the poem from the corner of
your eye, without actually looking like you are reading it.

Soda 2007 [Number of POPs]

There are circa 380 submissions to SODA, yummy! Hal Gabow will, I am sure, look at stats in the future, but for now, it is time to get to work.

Artists and Cities

I read/heard somewhere: there are hundreds of millionaires and thousands of artists in Paris, thousands of millionaires and hundreds of artists in London, and thousands of artists, thousands of millionaires and thousands of millionaire-artists in New York. May be I read this in the L magazine, a pocket sized publication with an idiosyncratic listing of what is going on in NY every fortnight (old word? = two weeks). Any other pointer will be welcome.

Soda pop

Today is the deadline for SODA 2007 submissions. Oddly, I am looking forward to going to the PC website and looking at an overwhelmingly large list of submissions. I may be irked by some of them, by I know there will be several submissions I will like very much, and I will end up learning a lot of new problems, techniques, and insights, some puzzles and some savory distractions (recall Hitchhock-esque Overhang from SODA06).

Brooklyn World Cup

[In Brooklyn, people react to an intruding Wall Street Journal left outside a brownstone for the morning delivery and look at each other quizzically; despite the gentrification of the King's County, in some parts, that delivery still evokes a shake of the head. ]

I went to watch the soccer game between Germany and Italy. I intuited that they would go overtime and walked into the bar as the regular time wound down. The beer in the bar was as warm as the British bitters and the air conditioning could not keep up with the thronging Brooklynites as the crowd followed the overtime. The spectators were equal parts German and Italian fans, but the German fans won out in cuteness: there were two boys with frizzy hair with black-red-yellow colors on their faces, drinking water from Brooklyn Lager cups. The prominent reaction was one of laughter as players from both sides went down clutching their faces, arms and legs in agony, only to stand up after the referee's call and sprint off. Still, there were whistles, claps, songs and infusion of energy as each fan base willed its team. I thought the Italians were crisper with their passes and sharper with their chances, and if the game had gone to penalty shootouts, I would have given the edge to Italy, notwithstanding its history in penalty shoot outs. Still, this is soccer, and anything can and will happen. It did. Miraculously, Italy broke through, once and then twice in two minutes. Unlike in Germany and probably elsewhere, the crowd did not linger. The bar crowd broke off, having shared moments of some togetherness, same cause or not, and went off to do chores, drink coffee, change for the evening celebrations, whatever. Other bars too emptied, and parts of Brooklyn breathed the muggy air outside, like many places around the world, some languid, some boisterous.

Time Travel and Currency

Borges has a story where as an old professor, he meets his youthful self on a bench (in Boston?). The older version tries to convince the younger one about the passage of time and the anachronicity of their meeting by showing a dollar bill and pointing to the date (year of print) on it that would prove to be in the future for the young Borges. A minor mistake since US currency unlike the coins did not have date on them in the past (now they have the series year). Other currencies -- Euro, British pounds -- also do not have a year/date on them it seems from my preliminary test.

Machine Learning

I was at the Intl Conf on Machine Learning (ICML) last week, in the workshop on Knowledge Discovery from Data Streams. I gave a tutorial on new developments in data stream algorithms. I am not a machine learning expert, but I spent some time formulating machine learning problems in the data stream model. For example, how to approximate a decision tree that is much too large for the storage available with some approximation guarantees, or how to find the support vector with some provable generalization error guarantee when the positive and negative examples arrive on a stream, etc. Still, it was a difficult conversation at the conference. A lot of researchers seem to think any incremental algorithm is a streaming algorithm. Sigh.

Restaurant Refs

I am happy to point out restaurants to people, but usually do not recommend them. Because one's experience with a restaurant is a function of many things, their mood, the service, the food they order and the food they get, their resonance with the chef, repeated tests, failures and sublime moments. Still, here are a couple of recommendations. Yasuda is the master sushi chef and never disappoints. Recently I was in Italy and went back to the restaurant of two of my friends. Lavinia and her family own and run the LaStalla, a gem halfway up the mountain in Santa Margherita. Paola and her family own and run the authentic focaccia-al-formaggio place Restorante Da O Vittorio at Recco. If you are in Liguria, I recommend both these restaurants. If you not in Liguria, you must go.