We have a dictionary D of vectors to be preprocessed, and a query vector q. We need to find nearest neighbor of q in D. Distance d(u,v) is the Hamming distance but any position i in which u and v differ can not differ by more than k (|u[i]-v[i]| \leq...

We now know how to compress individual strings, down to the various notions of optimal entropy inherent in Lempel-Ziv to Burrows-Wheeler methods. But what is the theory of compressing a set S of strings, ie, what are optimal compression methods and...

Say you have a slot and multiple bids b_i's. We can assign it proportional to the bids, b_i/sum_i b_i. In a nice paper, Johari and Tsitsiklis showed that even in presence of strategic bidders, the total utility to the bidders is no worse than 3/4 of...

Travel to Italy should really be about food, friends and Fabriano on the left (making paper since 1264 AD). But it was all about flying. I don't mean just the angst of Alitalia (the security announcements were muffled, the remote for the entertainment...

Exactly a week after Friday the 13th was the day of celebration of 20th Anniversary of DIMACS. I was there with my notebook, a journalist for part of the day. Ron Graham led, talking about embedding graphs into the Hypercube (into {0,1,*}^D space with...