In this post I’d like to report a new and simple proof we found for theorem by Berenbrink, Czumaj, Steger, Vöcking on the imbalance of the balls-into-bins process known as the multiple choice scheme. Full details could be found in the paper. Probably many are familiar with this process, Kunal blogged about some variations of it a few months … Continue reading Balls-and-Bins made simpler

I continue the discussion from last post. We are trying to add unpredictability to tennis by looking for a monotone, transitive and balanced function $latex f$ such that $latex E_p(f)$ has a wide threshold window, that is, we want the range of $latex p$ where $latex E_p(f)$ is, say, between 0.01 and 0.99, to be as large … Continue reading Tennis for the People II

I love sports, at least watching it. I could be tempted to follow any competition in any sport (with the obvious exceptions of baseball, cricket and golf). Now that the London Olympic games are almost forgotten and the world cup a full year and a half away (576 days to be precise) I want to … Continue reading Tennis for the People

In memory of Mihai  Pătraşcu Written by Rasmus Pagh, Rina Panigrahy, Kunal Talwar and Udi Wieder Reductions are arguably at the heart of complexity theory. They show that one problem is at least as hard as another. Finding reductions often requires creativity and considerable technical skill; some reductions seem as if they were pulled from thin air. The most difficult … Continue reading The Art of Reductions

This post has some tidbits regarding the problem of computing a 'fingerprint' of a long sequence of characters, often called 'string hashing'. Most of the results I will describe are quite old, but they are scattered upon several papers, so I think it is worthwhile to have a post where they are  put together. This … Continue reading How to collapse the universe?