Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR17-191 | 1st June 2018 14:26

Prediction from Partial Information and Hindsight, an Alternative Proof

RSS-Feed




Revision #2
Authors: Alexander Smal, Navid Talebanfard
Accepted on: 1st June 2018 14:26
Downloads: 790
Keywords: 


Abstract:

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 the average coordinate has high entropy. Meir and Wigderson [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 [PPZ99] who gave a non-trivial k-SAT algorithm and tight depth-3 circuit lower bounds for parity.



Changes to previous version:

For arbitrary \epsilon we adapted our proof to give the optimal bound when witnesses can be represented by decision trees.


Revision #1 to TR17-191 | 27th March 2018 23:42

Prediction from Partial Information and Hindsight, an Alternative Proof





Revision #1
Authors: Alexander Smal, Navid Talebanfard
Accepted on: 27th March 2018 23:42
Downloads: 842
Keywords: 


Abstract:

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 the average coordinate has high entropy. Meir and Wigderson [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{\' a}k and Zane \cite{PPZ99} who gave a non-trivial k-SAT algorithm and tight depth-3 circuit lower bounds for parity.



Changes to previous version:

There was a flaw in the proof of Lemma 1.
New proof works only for \epsilon = 1.


Paper:

TR17-191 | 15th December 2017 16:02

Prediction from Partial Information and Hindsight, an Alternative Proof


Abstract:

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