期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2017
卷号：2017
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Let X be a random variable distributed over n -bit strings with H ( X ) n − k , where k 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.
