Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-191 | 15th December 2017 16:02

Prediction from Partial Information and Hindsight, an Alternative Proof



Let $X$ be a random variable distributed over $n$-bit strings with $H(X) \ge n - k$, where $k \ll n$. Using subadditivity we know that a random coordinate looks random. Meir and Wigderson [TR17-149] showed 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.

ISSN 1433-8092 | Imprint