Sports Laughs

On the left is the oldie, Monty Python: greeks and germans talk it out on the soccer field. On the right is the newbie, ONN (Onion News Network), the "greatest export from Wisconsin": NASCAR secrets revealed (at the end of the video, there are links to more ONN gems).

Middle East in Movies

Middle East is in my mind, now curiously, via many movies.

• Persepolis from Iran animates the struggle of a girl during the transition of Iran even as she is caught with her feet and heart in the west, more precisely, France. Here is more on the animation.
  
• In The Band's Visit, an Egyptian police band gets lost in Israel and behind the comedy, there is a sense of longing and waiting, for whatever, on all sides. Here is a review.
  
• Then, in Sukkar Banat (Caramel, in English), five lebanese women enact a captivating chick flick, find their niche and entrap each other, in and around a hair salon. Here is a video review.

A Question

I have been sick, which means you reduce the throttle, but don't shut down; you hover between rest and work, and try to get out of it at least half ahead, or only half behind, if that makes any sense. In that state, I noticed the comment that appeared in response to the post on Valiant at lance/GASARCH Blog:

Valiant proved the equivalence between Boolean Matrix Multiplication and Context Free Parsing - which was considered a major result - at least in the late 70's. Ref: Valiant, Leslie G. 1975. General context-free recognition in less than cubic time. Journal of Computer and System Sciences, 10:308--315. 11:35 AM, February 18, 2008.

This comment reminded me of a question many have had in their mind for some time: can regular expressions be recognized in sub-quadratic time? In particular, and this may be from the left field, is there a way to show that regular expression recognition encodes matrix multiplication (on some reduced input)? We know that certain simple cases encode integer multiplication, but we need more insights.

3 Pictures

A String Problem

In string matching, there is a nice open problem from Gadi Landau that seems to need a chunk of combinatorics:

Input: A test string T of length n, may be preprocessed.
Query: A pattern string P of length m. Output is all locations i such that T[i,...,i+m-1] \equiv to P[1,...,m], where two strings s and t are \equiv if there is a permutation of s that equals t.

What is the closest to O(n) preprocessing and |P| query processing one can get? Notice that |P| may be smaller than m, since P can be presented as a vector of characters and their frequencies.

Wall of Fame: Sailing

Amos Fiat, the sailing aficionado, maintains a picasa wall of fame, of those who braved the sea on his boat. Enjoy.

Chocolate Poem

Thanks to Oren and automatic translation.

In the end Ramat Gan there is a special place , There it's possible to stand and to smell chocolate. There is there high high house Windowless, with three chimnies, And thirty machinery of day and night work, And seventy work with apron and gloves, Preparing chocolate in all the forms. Little chocolate and big chocolate, Expensive chocolate and chocolate cheaply. Chocolate of walnuts and chocolate just , Chocolate are rich and chocolate to all. And the aroma for free. And all the citizens stop and smell Stop the children that run in the neighborhood, Curfew of the bus beyond the corner, The cats cease to flee from the dogs, The policemen stand next to the thiefs. All of them view on the chimnies And little by little the noses of all of them fill Latch of chocolate. In the end Ramat Gan there is a special place , There it's possible to stand and to smell chocolate.

*ריח של שוקולד/ יונתן גפן בסוף רמת גן יש מקום מיוחד, שם אפשר לעמוד ולהריח שוקולד. יש שם בית גבוה גבוה בלי חלונות, עם שלוש ארובות, ושלושים מכונות יום ולילה עובדות, ושבעים פועלים עם סינר וכפפות, מכינים שוקולד בכל הצורות. שוקולד קטן ושוקולד גדול, שוקולד יקר ושוקולד בזול. שוקולד אגוזים ושוקולד סתם, שוקולד לעשירים ושוקולד לכולם. והריח בחינם. וכל האזרחים עוצרים ומריחים. עוצרים הילדים שרצים בשכונה, עוצר האוטובוס מעבר לפינה, החתולים מפסיקים לברוח מהכלבים, השוטרים עומדים ליד הגנבים. כולם מביטים על הארובות ולאט לאט האפים של כולם מתמלאים בריח של שוקולד. בסוף רמת גן יש מקום מיוחד, שם אפשר לעמוד ולהריח שוקולד.

Passage to Israel and Back

I find it more interesting to travel than to read or write travel logs. Still, what is a trip to Israel like?

• You will see friends at the airport even before you board your flight.
• You'd give talk (s), see dozens of researchers you know, and that would still be only \eps fraction of the people you must truly, absolutely see.
  
• You'd drive by the high school in Haifa (thanks to Gadi) that at one time or the other had the majority of Israeli theoretical computer scientists as boys in baggy shorts.
  
• You'd be busy with work (coding, meeting, and thanks to the machinery, interviewing) and not have time to get over the jetlag or tourist or just be, but not only your friends, your friends' friends will promise to be your party buddies and you will manage to grab a nite out on Tel Aviv, dance and laugh.
  
• You would have friends fret about how security services will treat you at the airport; the security will scan all your items and be intrigued trying to unravel your notebook from Rome, with its doodles.
  
• You would vow to prove at least one new lemma before you leave the land, and after scratching for an hour at the airport, get some success.
  
• You would: eat, art, beach, talk Times, and finally, you would vow to return.
  

I am happy being jetlagged on return, watch the sunrise from my apartment and start the day, better yet, the weekend, before others.

Featured Research

I don't know what it means in a cosmic sense, but Google Research Homepage features an algorithms/theory paper. The paper represents work done by an intern visitor, Eddie Nikolova. I don't want to be shameless in plugging the paper, the stars or the homepage, so let me say, this too shall pass, the paper will be an ex-feature, and the world will still spin along a slanted axis.

FYI: Conference WISDOM

There is an ongoing conference First ACM International Conference on Web Search and Data Mining (WSDM 2008, pronounced wisdom). It has some papers that from the titles sound interesting, now I must go, browse, and get soft copies.

Metaphors

Someone told me I speak in metaphors. I recently spoke about how the referees plop down the football where they believe the ball advanced, this is fairly rough, and then they take out a precise chain to measure out the yards. You give up some at one place and are painstakingly accurate elsewhere. Research and researchers tend to be that way too: we are less than angst-ridden in modeling an optimization problem, and then are painstakingly accurate in getting a precise approximation ratio. Sometimes the optimization may not capture the underlying bottleneck in the system in practice. Which brings me to another metaphor I am tempted to use as I go through the day and almost always manage to trap it before it tumbles past my lips: you don't go to war with the army you want, you go to war with the army you got.

Capturing the mood

I was up early, planning my travel to Israel, and stumbled upon these wonderful photos of what appears to be the CS dept at Tel Aviv University: researchers --- wellknown, budding or hardly begun --- caught outdoors in a social context. The photos capture the mood of a summer afternoon, there are signs of music, mentoring, and from the look on a few lost faces, even math was not left out.

Lists

Sometimes the world shows you something, a sparkle perhaps, and you know you should understand something from it, but you keep staring, trying to work it all out.

I got an email sometime ago with the list of top 10 algorithms (influential) in data mining: C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. See this page for details, including the pdf that describes the context, and the 18 candidates from which these 10 were culled. There is also a page of top 10 problems in data mining, but the list is quite broad.

FYI: STOC08

I had an idle moment, browsed a little, and hit goodies: accepted papers at STOC.