When X is Enough

My advisor Joel Spencer derives pleasure from his result Six standard deviations suffice. The point of course is that often there is a pesky log factor in applications of the probabilistic method, and reducing it is a challenge, replacing it with an absolute constant is pure fun.

I was reminded of this when Meeyoung Cha pointed me to the SocialNets Conf she Chaired. One of the papers got my attention: Eight friends are enough. The paper argues that the Facebook tradition of showing eight friends in a profile page reveals far too much.

GhostNet Attack

For those who care, here is a detailed report of the GhostNet cyber attack. The report lists IP addresses, examples of attack, etc.

Pizza Ride

Yesterday I went to the park and peered at the trees for prescient signs of the spring (buds); today, the spring is here and I went for a ride to get some pizza.

Over the Williamsburg bridge to stop off at the metal worker artist (mine), via the buzz to Fort Greene and furniture (home and abroad), into Carroll Garden for South Brooklyn Pizza, and returned via the Brooklyn Bridge. 10+ miles of bicycle ride, see the map. The ride through many immigrant neighborhoods reminded me about the constancy of good pizza in NY: a good slice of pizza in one's neighborhood (3 blocks, 5 blocks, whatever is your neighborhood) is an inalienable right of a New Yorker (taxpayer or not), and not owned by any group. And that there is no such thing as the "best pizza" in NY, just merely the constellation of superb pizzas. South Brooklyn Pizza belongs to the constellation.

FOCS facts

UPDATE: Umesh has posted a writeup of the original proposal for introducing "brief descriptions" in FOCS. It is a very well made argument. Enjoy!

As we now know, FOCS 09 papers are due on April 2nd, and here is the novelty, a "brief description" is due a week later, on April 9th. These brief descriptions should fit within two pages. They may be informal, and need not meet the standards of a formal publication. Now, there are examples online.

Umesh Vazirani, a true sage, described the rationale for these brief descriptions better than anything I have heard: in a FOCS submission, you tend me make results general, details as needed to convince the referee of the correctness, and be scholarly. On the other hand, in informal discussions with an expert colleague or while giving a talk on the same result, you have a different conversation, one based more on intuition, getting quickly to the novelty and insights. The brief discussions will hopefully have this flavor.

ps: Everyone understands why brief descriptions are better after the deadline, not before. :)

Berra Time

Some weeks, partying begins on Thursdays. Not this week. Still here is a little distraction, some things people said, paraphrased, mangled, perhaps not even close to their original intent (think Berra who said "I didn't really say everything I said."):

• Garrett Cronin: At any given time, you feel only one pain, never two.
  
• Leslie Valiant: Why would humans know so many things, but at any time hold no more than say 5 things on their mind?
  
• T. S. Jayram : Streaming research holds a limited memory of prior work.
  
• Noam Nisan, referring to a bureaucracy: it has geological layers.
  

WWWs

WWW 2009 is not over yet, so even while looking forward to that excitement, the preparations for WWW 2010 have begun. The website, aptly, has a blog feel at this early stage. They have tapped two researchers, Juliana Friere and Soumen Chakrabarti, colleagues and coauthors from another place and time, to run the PC.

Green For a Day

NY is an Irish town on regular days (don't let anyone --- in particular, people who visit from Ireland --- tell you otherwise), on St. Patrick's even more so, with everyone just a little green. I too went green for the evening and spent it at Freddy's Backroom in Brooklyn, listening to songs about women, flowers and some sweet bluegrass.

Kanellakis Award

This year's Kanellakis award deservedly goes to Corinna Cortes and Vladimir Vapnik for their work on Support Vector Machines. This award has one of the toughest metrics to meet: one's work should triumph not only in math/theory (a tough bar by itself) but should also triumph in measurable, demonstrable use in practice (not just in potential use). Congratulations to Corinna and Vladimir!

On India

In India, every day, extremes of life mix, but retain their essential character. Like a good curry. The secret to a good curry that people don't understand is not the mixture of the tastes, but that each component retains its essence and your taste buds should pick them up individually.

In the video on the left, the moghul emperor Akbar marries a Rajput princess, and the sufi's sing. Colors, fire, tears and Qawali collide and in a stirring finale, the great emperor joins them in the sufi whirl.

I am not a fan of panning panoramic camera shots, but this captures the ethereal role of the Emperor best understood by reading The Miniaturist by Kunal Basu in which a great painter is charged with spending his life making miniature paintings for the grand book of the Emperor Akbar's life, and has never even seen the Emperor.

Puzzle via blogs

Researchers in histogram construction (yes, there are several) will recognize the following problem: given an array A of size N, for each interval [l,r] in [1,N], determine the median of items in the interval A[l],A[l+1],....,A[r]. How quickly can one solve this problem? I had a few playful moments a couple of weeks ago and wrote this note, but with more play time, one should have a simpler, O(N^2) time algorithm. Further, one should be able to do this using o(N^2) space, not counting the output size. No approximations please. Enjoy!

Women Flicks

Coincidentally I watched 8 femmes, Memoirs of Geisha, and Bonneville recently, let us just say I did not have a choice, being strapped down inside a large metallic tube at 30000 ft. These have different cultural contexts, french, japanese and north american resp. Still, they have one thing in common: they load up on stars. 8 femmes has nearly every french actress I know including Catherine Deneuve, Emmanuelle Beart, (my fave from this near-real time movie) Virginie Ledoyen and Ludivine Sagnier. Memoirs of Geisha has nearly all Asian actresses I know including Gong Li, Michelle Yeoh and the incomparable Ziyi Zhang. Bonneville loads up too, including Jessica Lange, Kathy Bates and Joan Allen. What's the deal.

Reporting on Barbados

I was in Barbados last week teaching data stream algorithms. Here are some notes linked from my algo.research page (topics, links to papers, and some commentary, including unsolicited advice for the future lecturers); lecture notes will appear later. See details about this 09 meeting, including the list of participants. ps: Yahoo! has released datasets useful for researchers. I found this course which looks interesting (eg, the database view of MapReduce).