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 #4 to TR17-149 | 28th June 2018 11:40

Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds

RSS-Feed




Revision #4
Authors: Or Meir, Avi Wigderson
Accepted on: 28th June 2018 11:40
Downloads: 23
Keywords: 


Abstract:

Consider a random sequence of $n$ bits that has entropy at least $n-k$, where $k\ll n$. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that says, roughly, that the average coordinate looks random to an adversary that is allowed to query $\approx\frac{n}{k}$ other coordinates of the sequence, even if the adversary is non-deterministic. This setting generalizes decision trees and certificates for Boolean functions.

As an application of this result, we prove a new result on depth-$3$ circuits, which recovers as a direct corollary the known lower bounds for the parity and majority functions, as well as a lower bound on sensitive functions due to Boppana (IPL 63(5), 1997). An interesting feature of this proof is that it works in the framework of Karchmer and Wigderson (SIDMA 3(2), 1990), and in particular it is a “top-down” proof (Hastad, Jukna and Pudlak, Computational Complexity 5(2), 1995). Finally, it yields a new kind of a random restriction lemma for non-product distributions, which may be of independent interest.



Changes to previous version:

Added discussion of the connection to the satisfiability coding lemma.


Revision #3 to TR17-149 | 17th January 2018 14:49

Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds





Revision #3
Authors: Or Meir, Avi Wigderson
Accepted on: 17th January 2018 14:50
Downloads: 120
Keywords: 


Abstract:

Consider a random sequence of $n$ bits that has entropy at least $n-k$, where $k\ll n$. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that says, roughly, that the average coordinate looks random to an adversary that is allowed to query $\approx\frac{n}{k}$ other coordinates of the sequence, even if the adversary is non-deterministic. This setting generalizes decision trees and certificates for Boolean functions.

As an application of this result, we prove a new result on depth-$3$ circuits, which recovers as a direct corollary the known lower bounds for the parity and majority functions, as well as a lower bound on sensitive functions due to Boppana (IPL 63(5), 1997). An interesting feature of this proof is that it works in the framework of Karchmer and Wigderson (SIDMA 3(2), 1990), and in particular it is a “top-down” proof (Hastad, Jukna and Pudlak, Computational Complexity 5(2), 1995). Finally, it yields a new kind of a random restriction lemma for non-product distributions, which may be of independent interest.


Revision #2 to TR17-149 | 15th January 2018 17:09

Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds





Revision #2
Authors: Or Meir, Avi Wigderson
Accepted on: 15th January 2018 17:09
Downloads: 80
Keywords: 


Abstract:

Consider a random sequence of $n$ bits that has entropy at least $n-k$, where $k\ll n$. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that says, roughly, that the average coordinate looks random to an adversary that is allowed to query $\approx\frac{n}{k}$ other coordinates of the sequence, even if the adversary is non-deterministic. This setting generalizes decision trees and certificates for Boolean functions.

As an application of this result, we prove a new result on depth-$3$ circuits, which recovers as a direct corollary the known lower bounds for the parity and majority functions, as well as a lower bound on sensitive functions due to Boppana (IPL 63(5), 1997). An interesting feature of this proof is that it works in the framework of Karchmer and Wigderson (SIDMA 3(2), 1990), and in particular it is a “top-down” proof (Hastad, Jukna and Pudlak, Computational Complexity 5(2), 1995). Finally, it yields a new kind of a random restriction lemma for non-product distributions, which may be of independent interest.



Changes to previous version:

Fixed some typos, and added discussion of a recent follow-up work.


Revision #1 to TR17-149 | 13th November 2017 18:49

Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds





Revision #1
Authors: Or Meir, Avi Wigderson
Accepted on: 13th November 2017 18:49
Downloads: 115
Keywords: 


Abstract:

Consider a random sequence of $n$ bits that has entropy at least $n-k$, where $k\ll n$. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that says, roughly, that the average coordinate looks random to an adversary that is allowed to query $\approx\frac{n}{k}$ other coordinates of the sequence, even if the adversary is non-deterministic. This setting generalizes decision trees and certificates for Boolean functions.

As an application of this result, we prove a new result on depth-$3$ circuits, which recovers as a direct corollary the known lower bounds for the parity and majority functions, as well as a lower bound on sensitive functions due to Boppana (IPL 63(5), 1997). An interesting feature of this proof is that it works in the framework of Karchmer and Wigderson (SIDMA 3(2), 1990), and in particular it is a “top-down” proof (Hastad, Jukna and Pudlak, Computational Complexity 5(2), 1995). Finally, it yields a new kind of a random restriction lemma for non-product distributions, which may be of independent interest.



Changes to previous version:

Fixed a small error in the introduction, and clarified the connection between Proposition 1.7 and Claim 3.2.


Paper:

TR17-149 | 7th October 2017 17:08

Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds


Abstract:

Consider a random sequence of $n$ bits that has entropy at least $n-k$, where $k\ll n$. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that says, roughly, that the average coordinate looks random to an adversary that is allowed to query $\approx\frac{n}{k}$ other coordinates of the sequence, even if the adversary is non-deterministic. This setting generalizes decision trees and certificates for Boolean functions.

As an application of this result, we prove a new result on depth-$3$ circuits, which recovers as a direct corollary the known lower bounds for the parity and majority functions, as well as a lower bound on sensitive functions due to Boppana (IPL 63(5), 1997). An interesting feature of this proof is that it works in the framework of Karchmer and Wigderson (SIDMA 3(2), 1990), and in particular it is a “top-down” proof (Hastad, Jukna and Pudlak, Computational Complexity 5(2), 1995). Finally, it yields a new kind of a random restriction lemma for non-product distributions, which may be of independent interest.



ISSN 1433-8092 | Imprint