Population Algorithms by Petar Maymounkov

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.

Positive semidefinite operators and norm polytopes – 5

Under FA: Functional Analysis, Question

I’ve been obsessing over the following conjecture. And to be honest I haven’t been able to find any counterexamples, nor make any significant progress towards proving it. So, here goes:

If $A,B$ are positive semidefinite and $A\preccurlyeq B$ , then $\|A\|_{1\rightarrow 1} \le \|B\|_{1\rightarrow 1}$ .

In fact, it seems that if this is true for the $\|\cdot\|_{1\rightarrow 1}$ -norm, it probably is true for all norms of the form $\|\cdot\|_{p\rightarrow p}$ . Any ideas or references would be greatly appreciated.

Resistance vs. density – No Comments

Under Computer Science, Graph spectra

In a recent paper “Graph sparsification by effective resistances”, Spielman, Srivastava (STOC’08) show that one can sparsify a graph by essentially randomly getting rid of edges with very low effective resistance. Here we discuss an interesting corollary of one of the lemmas in this paper, which is not explicitly mentioned in the paper. In particular, we show a direct connection between the edge density of a graph and the smallest effective resistance.

For a graph $G$ define $\Pi=W^{1/2}BL^{-1}B^* W^{1/2}\in\mathds{R}^{E\times E}$ . This is all standard notation: $W$ is the diagonal edge-weights matrix, $B\in\mathds{R}^{E\times V}$ is the edge orientation matrix, and $L$ is the Laplacian. (Note we have that $L=B^*WB$ .)

The matrix $\Pi$ has the property that $\Pi_{e,e}=w_eR_e$ , where $R_e$ is the effective resistance of edge $e$ , and $w_e$ is its weight. We’ll focus on the case when all $w_e=1$ for simplicity. We prove the following statement:

If graph $G$ has $n$ vertices and $m$ edges, then there is an edge of effective resistance at most $(n-1)/m$ .

To see this, we use Lemma 3 in the paper which states that $\Pi$ has eigenvalue $1$ of multiplicity $n-1$ , and eigenvalue 0 of multiplicity $m-n+1$ . The sum of the eigenvalues thus equals $n-1$ . On the other hand, the trace of $\Pi$ equals $\sum_e w_eR_e$ . Equating the two (and using $w_e=1$ ) we get $\sum_e R_e = n-1$ . Therefore $\E\cdot R_e = (n-1)/m$ . Thus, there must exist at least one edge with effective resistance at most $(n-1)/m$ .

This inequality is tight in various small-graph cases that one could think of. And it is asymptotically tight in others (a long cycle with a shortcut in the middle). It is interesting to find out whether it is tight for large graphs of intermediate density (more than linear, less than quadratic).

Let’s see how this equality relates (directly) to sparsification. A close inspection of Lemma 4 in the paper asserts the following statement:

If we remove an edge $e$ from a graph, then the Laplacian of the new and the old graph are related by $(1-w_e R_e)L\preccurlyeq\tilde{L}\preccurlyeq L$ . This inequality is tight on both sides.

On the left equality is attained when considering the vector of potentials corresponding to a unit electric flow between the endpoints of $e$ . On the right equality is attained by considering any vector that equals 0 over the endpoints of $e$ .

The last statement combined with the inequality (that relates effective resistance to density) beg the question whether one can sparsify a graph by removing one edge at a time (and re-weighting the rest appropriately). If this is indeed a possibility, it would also have to be true that any sequence of removed edges $e_1,\dots,e_k$ that leads to a best sparsification must contain the edge of smallest effective resistance in the original graph.

The questions mentioned here are important since they relate to the conjecture that all graphs have linear-size sparsifiers. It is also a possibility that a one-edge-at-a-time procedure may lead to a more practical sparsification (in the Laplacian sense) algorithm than the currently available alternatives.

Breakfast for Champions – No Comments

Under Spontaneous

I believe one day I will look back and wonder, what have I had for breakfast all those years. What are my ingredients, so to speak. Here’s what I had today then:

Naked “Orange Mango Motion” juice — all natural and it has 100% of something
Fage greek yoghurt — the best yoghurt on the market. Keep in mind that I am Bulgarian. We have the best yoghurt bacteria in the world. So if I tell you that Fage is awesome-est, then it is
Flaxseed Oil — this, my friends, is the secret ingredient which when mixed with the yoghurt (above) turns you into a gladiator
A plain croissant — often all that one needs for a successful day, croissant and coffee and off you go

And, if you are questioning what is so fascinating about my breakfast: I prepended some yoga before it, which essentially doubles the pleasure of anything that comes afterwards — breakfast and work alike!

3-coloring year 2006 – 2

Under Puzzles

Let COL be a 3-coloring of the numbers 1, …, 2006. Show that there exist numbers X and Y such that COL(X) = COL(Y) and |X − Y| is a square. Appeared on Maryland Math Olympiad 2006. Acquired from Luca Trevisan’s blog.

Approximating square roots – 2

Under Puzzles

Approximate $\sqrt{1} + \sqrt{2} + \cdots + \sqrt{50}$ in your head (or using a sheet of paper or two) as best as you can. Anonymous.

Counting set bits – No Comments

Under Puzzles

You are given a computer with an n-bit machine word, which supports the standard bitwise operations: AND, OR, NOT, XOR, LEFT SHIFT, and RIGHT SHIFT. Given a machine word W, what is the smallest number of bitwise operations you need to perform to determine the number of set bits in W? You can assume you have arbitrarily many registers to use and COPY operations are not counted. The result has to be presented in the form of an integer represented in a machine word. Communicated by teacher David Karger.

Crystal orbs – 3

Under Puzzles

You have two identical crystal orbs. Your goal is to figure out how high a floor an orb can fall from a 100 story building before it breaks. What is the largest number of orb-drops you would ever have to do to find the right floor (i.e. what is the most efficient strategy by a worst-case measure)? You can break both orbs in your search, provided you yield a unique and correct answer. By former employer Mark Gorton.

Balls on scales – No Comments

Under Puzzles

You are presented with 12 identically looking balls of which, you are told, only one differs in weight from the others. Your goal is to find which one it is and whether it is lighter or heavier than the rest. Your only tool is a scales, which can be used by putting balls (and only balls) on either side and observing the outcome. The scales can be used at most three times. Folklore.

Four dogs and a prisoner – No Comments

Under Puzzles

A prisoner is enclosed inside a square. You are given 4 dogs that can roam the perimeter of the square. They run 1.5 times the speed of the prisoner. He escapes if he can cross the border without two or more of the dogs converging on him. Your challange is to pick an initial placement for the prisoner and the dogs and to program the dogs to keep him inside. You can give each dog a unique program, if you like. Communicated by friend Sam Yagan via friend Chris Coyne.