Revision #2 Authors: Alexander Smal, Navid Talebanfard

Accepted on: 1st June 2018 14:26

Downloads: 627

Keywords:

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.

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

Revision #1 Authors: Alexander Smal, Navid Talebanfard

Accepted on: 27th March 2018 23:42

Downloads: 673

Keywords:

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.

There was a flaw in the proof of Lemma 1.

New proof works only for $\epsilon = 1$.

TR17-191 Authors: Alexander Smal, Navid Talebanfard

Publication: 26th December 2017 20:14

Downloads: 1049

Keywords:

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.