Does This Fact Have a Name?

Does the following fact have a name?

Theorem 1 Suppose {X_1,\ldots,X_n,\ldots} are a countable collection of 0/1 random variables over a probability space {(\Omega, {\cal B}, \mathop{\mathbb P})} such that for every integer {n} and bits {b_1,\ldots,b_n} the event

\displaystyle  X_1 = b_1 \wedge \cdots \wedge X_n = b_n

is measurable.

Suppose that

\displaystyle  \sum_{i=1}^\infty \mathop{\mathbb E} X_i \ \ \ {\rm converges}


\displaystyle  \mathop{\mathbb P} \left[ \sum_i X_i = \infty \right] = 0

Proof: Intuitively, we want to say that by linearity of expectation we have {\mathop{\mathbb E} [ \sum_{i=1}^\infty X_i ] = O(1)} and so by Markov’s inequality

\displaystyle  \mathop{\mathbb P} \left[ \sum_{i=1}^\infty X_i = \infty\right] \leq \frac{O(1)}{\infty} = 0

Just to make sure that this can be made rigorous, let’s belabor the proof step by step, doing everything completely from first principles. Continue reading

Small-bias Distributions and DNFs

Two of my favorite challenges in unconditional derandomization are to find logarithmic-seed pseudorandom generators which are good against:

  1. log-space randomized algorithms
  2. {AC^0}, that is, constant depth circuits of polynomial size

Regarding the first challenge, the best known pseudorandom generator remains Nisan’s, from 1990, which requires a seed of {O(\log^2 n)} bits. Maddeningly, even if we look at width-3 oblivious branching programs, that is, non-uniform algorithms that use only {\log_2 3} bits of memory, nobody knows how to beat Nisan’s generator.

Regarding the second challenge, Nisan showed in 1988 that for every {d} there is a pseudorandom generator of seed length {O(\log^{2d+6} n)} against depth-{d} circuits of size {n}. The simplest case is that of depth-2 circuits, or, without loss of generality, of disjunctive-normal-form (DNF) formulas. When specialized to DNF formulas, Nisan’s generator has seed length {O(\log^{10} n)}, but better constructions are known in this case.

Luby, Velickovic and Wigderson improved the seed length to {O(\log^4 n)} in 1993. Bazzi’s celebrated proof of the depth-2 case of the Linian-Nisan conjecture implies that a {O(\log^2 m/\delta)}-wise independent distribution “{\delta}-fools” every {m}-term DNF, by which we mean that for every such DNF formula {\phi} and every such distribution {X} we have

\displaystyle  \left| \mathop{\mathbb P}_{x\sim X} [ \phi(x) = 1] - \mathop{\mathbb P}_{x\sim U} [\phi(x) = 1] \right| \leq \delta

where {U} is the uniform distribution over assignments. This leads to a pseudorandom generator that {\delta}-fools {n}-variable, {m}-term DNF formulas and whose seed length is {O(\log n \cdot \log^2 m/\delta)}, which is {O(\log^3 n)} when {m,n,\delta^{-1}} are polynomially related.

In a new paper with Anindya De, Omid Etesami, and Madhur Tulsiani, we show that an {n}-variable, {m}-term DNF can be {\delta}-fooled by a generator of seed length {O(\log n + \log^2 m/\delta \cdot \log\log m/\delta)}, which is {O(\log^{2+o(1)} n)} when {n,m,\delta^{-1}} are polynomially related.

Our approach is similar to the one in Razborov’s proof of Bazzi’s result, but we use small-bias distribution instead of {k}-wise independent distributions

Continue reading

On the Importance of Fast Encryption

The CNN reports that Iraqi insurgents have been able to see the video feeds from the cameras of the remote-control planes (“drones”) that are used by American forces to gather intelligence and for targeted strikes.

How did the Iraqi insurgents manage to break the encryption used by the American military? That was easy: the video feed is sent in the clear from (some of) the drones. And with what sophisticated eavesdropping devices did the Iraqi insurgents manage to capture the video signal? With standard satellite dishes, and with a Russian program originally written to watch satellite TV channels for free.

Well, thanks God this incredible oversight has been exposed, so that it can be fixed.

“We have known about this for years.” Military sources told CNN. In fact, during the 2003 invasion, the Iraqi army was able to see the feeds from the drones, and hence locate and destroy some of them.

And what exactly was anybody thinking? “Encryption was found to slow the real-time link.” The military source told CNN: “The encryption therefore was removed from many feeds.”

Lies, Damn Lies, and New York Times Reporting

Exercise for the reader: find what is wrong with the following paragraphs from an article in the New York Times about the high cost of certain cancer drugs.

In the clinical trial that led to approval of the drug, 27 percent of the 109 patients experienced a reduction in tumor size. The reductions lasted a median of 9.4 months.

But considering all the patients in the trial, only 12 percent had a reduction in tumor size that lasted for more than 14 weeks.

Update: from the press release of the pharmaceutical company:

The results of the trial demonstrated that 29 of 109 evaluable patients, or 27%, responded to FOLOTYN. The median duration of response was 287 days, or 9.4 months (range 1-503 days). Thirteen of 109 evaluable patients had a duration of response ≥ 14 weeks (range 98-503 days).

So the median of 29 numbers is 287, and 16 of those numbers are less than 98.