Yelp Data Challenge

Yelp runs a data analysis challenge: Predict health metrics of restaurants. Enjoy. 

Condolences

My thoughts are with the family and friends of my neighbor, friend and an incredibly thoughtful soul Dan who fell pursuing Mr. Everest, a victim of the quake. 

Streaming H

Items  I_i s (+ve integers,  I_i \in [1,U]) arrive one after another, and for any n, after having seen n items, you have to return an approximation to H_n which is the H-index of the first n items. I_1,...,I_n  (The H-index of a set of number is largest k such that there are at least k items each >= k). A student in Rutgers posed this problem.

This problem has a simple worstcase solution: sing log_{1+\eps} U space, get  (1+\eps) one-sided error approximation by maintaining an exponential histogram on the domain and counting the number of items in each bucket. (The same solution works if items arrive and depart as well. ) Now, U can be replace by max_{i <=n} I_i after n items, so it is input data-sensitive. If items are drawn from domain [L,R], you can splice out the lower buckets and the same solution works with about (log R-log L)  buckets (better than log (R-L)).  None of this is particularly interesting theory wise.

Is there an interesting version of this problem if the items are drawn iid from unknown distribution repeatedly? Curious people should see the connection to the Prophet inequality and frugal streaming results.

Bernal Heights Park

Someone asked me to poet about the Bernal Heights Park in my SF neighborhood, so here it goes:

Climb any which way, this pyramid of a hill with three trees on the top.
Look up whilest and see peoples' busts and  heads of unleashed dogs against the sky.
And head down to see the porcelain youth on Cortland Avenue.

Art Gravity Shifts: Whitney Museum among Meatpackers

Whitney, a real American museum --- forget the century old language of art elsewhere, here it is urgent, it is both now and the far future with its biennials ---   moves to meatpacking district next month. My great hope is, they will come for the High Line, stay for a real lesson in the past 50 yrs of American art and the next 50, and the world will be a far better place.

That aside, NY times shows the depth of the art galleries in NY, 10 in Chelsea to see.

DIMACS seeks an Associate Director

DIMACS continues to thrive, with its current Director Rebecca Wright, finding, following and leading the flow of Theoretical Computer Science as it meanders through ever new application areas and burrows to new foundations. DIMACS is looking for an Associate Director.

Short Blurb: 

The DIMACS Center at Rutgers University (dimacs.rutgers.edu) is seeking an Associate Director. DIMACS facilitates research, education, and outreach in discrete mathematics, computer science theory, algorithms, mathematical and statistical methods, and their applications..  The Associate Director is expected to play a leadership role in planning, developing, and running DIMACS activities and programs, including setting new directions.  A PhD in computer science, mathematics, operations research, statistics, or a related field is preferred. Applicants with a doctorate will be considered for Associate Director with a non-tenure-track calendar-year research faculty appointment at Rutgers. Highly qualified applicants without a doctorate will be considered for a staff appointment as Assistant Director. For more details, visit dimacs.rutgers.edu/AssociateDirector.