Prediction from Partial Information and Hindsight, An Alternative Proof

Abstract

Let $X$ be a random variable distributed over $n$-bit strings with $H(X) \le n−k$, where $k \ll n$. Using subadditivity we know that the average coordinate has high entropy. Meir and Wigderson [ECCC-TR17-149] showed that a random coordinate looks random to an adversary who is allowed to query around $n/k$ other coordinates non-deterministically. They used this result to obtain top-down arguments in depth-3 circuit lower bounds. In this note we give an alternative proof of their main result which tightens their parameters. Our proof is inspired by a paper of Paturi, Pudlák, and Zane who gave a non-trivial k-SAT algorithm and tight depth-3 circuit lower bounds for parity.

Publication
Information Processing Letters
Date