Prediction from partial information and hindsight, an alternative proof

0489470 - MÚ 2019 RIV NL eng J - Journal Article
Smal, A.V. - Talebanfard, Navid
Prediction from partial information and hindsight, an alternative proof.
Information Processing Letters. Roč. 136, August (2018), s. 102-104. ISSN 0020-0190. E-ISSN 1872-6119
EU Projects: European Commission(XE) 339691 - FEALORA
Institutional support: RVO:67985840
Keywords : certificate complexity * circuit complexity * computational complexity
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 0.914, year: 2018
https://www.sciencedirect.com/science/article/pii/S0020019018300917?via%3Dihub

Let X be a random variable distributed over n-bit strings with H(X)≥n−k, where k«n. Using subadditivity we know that the average coordinate has high entropy. Meir and Wigderson [1] 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 [3] who gave a non-trivial k-SAT algorithm and tight depth-3 circuit lower bounds for parity.
Permanent Link: http://hdl.handle.net/11104/0283879