PR: Probability | Population Algorithms by Petar Maymounkov

Paul’s Canonical Tester – No Comments

Under Computer Science, Mathematics, PR: Probability, Property testing

Paul Valiant’s Canonical Tester is a one-stop-shop solution for testing any symmetric property of a distribution. If the Canonical Tester can’t do it, neither can you. The additional upshot is that the Canonical Tester is quite simple an algorithm, so proving lower bounds (impossibility results) usually takes short 5-line arguments explaining why the Canonical Tester can’t do it.

Testing asymmetric properties is now the next interesting question. Interesting it is indeed because most practical questions actually tend to involve asymmetric properties. A modified example of Paul’s talk goes like this. Imagine Amazon makes a change on their website, and they like to know whether more books compared to electronics were sold after the change. This is an asymmetric test.

Feige’s conjecture for sums with unbounded variance – 2

Under Combinatorial optimization, Computer Science, Mathematics, PR: Probability

I’d like to spell out a conjecture of Feige (which is pretty elegant and simple to state) if for no better reason so that I don’t forget it:

Let $X_1,\dots,X_n$ be independent random non-negative variables with $\E [X_i]=1$ (and arbitrary variance). Then $\Pr[\sum X_i < n + 1] \ge 1/e$ .

The conjecture is a little more general than that, but I’ve purified it for simplicity and, in fact, the above statement is the crux of the conjecture. Feige already proved the conjecture when $1/e$ is replaced by $1/13$ using a, well, horrendous case analysis. So the goal here is really to get the constant $1/e$ and hopefully with a more natural argument.

This conjecture appears in On the sum of nonnegative independent random variables with unbounded variance, Feige’03. I believe that solving implies a better approximation constant for a certain sub-modular optimization problem.