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 implies corresponding results for 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 (Circuits Inf Process Lett 63(5):257–261, 1997). An interesting feature of this proof is that it works in the framework of Karchmer and Wigderson (SIAM J Discrete Math 3(2):255–265, 1990), and, in particular, it is a “top-down” proof (Håstad et al. in Computat Complex 5(2):99–112, 1995). Finally, it yields a new kind of a random restriction lemma for non-product distributions, which may be of independent interest.
Similar content being viewed by others
References
Ajtai, Miklós: \(\Sigma _1^1\)-Formulae on finite structures. Annals of Pure and Applied Logic 24(1), 1–48 (1983)
Ajtai, Miklós: Boolean Complexity and Probabilistic Constructions, 140–164. London Mathematical Society Lecture Note Series, Cambridge University Press (1992)
Miklós Ajtai (1993). Geometric Properties of Sets Defined by Constant Depth Circuits. In Combinatorics, Paul Erdős is eighty. Budapest, Hungary : János Bolyai Mathematical Society. ISBN 9638022736 (set)
Ziv Bar-Yossef, T.S., Jayram, Ravi Kumar, Sivakumar, D.: An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci. 68(4), 702–732 (2004)
Paul Beame (1994). A switching lemma primer. Technical report, Technical Report UW-CSE-95-07-01, Department of Computer Science and Engineering, University of Washington
Boppana, Ravi B.: The Average Sensitivity of Bounded-Depth Circuits. Inf. Process. Lett. 63(5), 257–261 (1997)
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio & Li-Yang Tan (2016). Near-optimal small-depth lower bounds for small distance connectivity. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18–21, 2016, 612–625
Thomas M. Cover & Joy A. Thomas (1991). Elements of information theory. Wiley-Interscience. ISBN 0-471-06259-6
Irit Dinur & Or Meir (2016). Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, 3:1–3:51
Duris, Pavol, Galil, Zvi, Schnitger, Georg: Lower Bounds on Communication Complexity. Inf. Comput. 73(1), 1–22 (1987)
Edmonds, Jeff, Impagliazzo, Russell, Rudich, Steven, Sgall, Jiri: Communication complexity towards lower bounds on circuit depth. Computational Complexity 10(3), 210–246 (2001)
Furst, Merrick L., Saxe, James B., Sipser, Michael: Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory 17(1), 13–27 (1984)
Anat Ganor, Gillat Kol & Ran Raz (2014). Exponential Separation of Information and Communication. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18–21, 2014, 176–185
Dmitry Gavinsky, Or Meir, Omri Weinstein & Avi Wigderson (2014). Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, 213–222
Michelangelo Grigni & Michael Sipser (1991). Monotone Separation of Logspace from NC. In Structure in Complexity Theory Conference, 294–298
Grinberg, Aryeh, Shaltiel, Ronen, Viola, Emanuele: Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs. Electronic Colloquium on Computational Complexity (ECCC) 25, 61 (2018)
Johan Håstad (1986). Almost Optimal Lower Bounds for Small Depth Circuits. In STOC, 6–20
Håstad, Johan, Jukna, Stasys, Pudlák, Pavel: Top-Down Lower Bounds for Depth-Three Circuits. Computational Complexity 5(2), 99–112 (1995)
Hossein Jowhari, Mert Săglam & Gábor Tardos (2011). Tight bounds for Lp samplers, finding duplicates in streams, and related problems. In Proceedings of the 30th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2011, June 12–16, 2011, Athens, Greece, 49–58
Mauricio Karchmer, Eyal Kushilevitz & Noam Nisan (1995a). Fractional Covers and Communication Complexity. SIAM J. Discrete Math. 8(1), 76–92
Mauricio Karchmer, Ran Raz & Avi Wigderson (1995b). Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity. Computational Complexity 5(3/4), 191–204
Mauricio Karchmer & Avi Wigderson: Monotone Circuits for Connectivity Require Super-Logarithmic Depth. SIAM J. Discrete Math. 3(2), 255–265 (1990)
Khrapchenko, V.M.: A method of obtaining lower bounds for the complexity of \(\pi \)-schemes. Mathematical Notes Academy of Sciences USSR 10, 474–479 (1972)
Maria M. Klawe, Wolfgang J. Paul, Nicholas Pippenger & Mihalis Yannakakis (1984). On Monotone Formulae with Restricted Depth (Preliminary Version). In Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA, 480–487
Gillat Kol & Ran Raz (2013). Interactive channel capacity. In Symposium on Theory of Computing onference, STOC'13, Palo Alto, CA, USA, June 1–4, 2013, 715–724
Linial, Nathan, Mansour, Yishay, Nisan, Noam: Constant Depth Circuits, Fourier Transform, and Learnability. J. ACM 40(3), 607–620 (1993)
Lyle A. Mcgeoch (1986). A Strong Separation betweem \(k\) and \(k-1\) Round Communication Complexity for a Constructive Language. Technical Report CMU-CS-86-157, Carnegie Mellon University
Meir, Or: An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Three Rounds. Electronic Colloquium on Computational Complexity (ECCC) 24, 129 (2017)
Noam Nisan & Avi Wigderson: Rounds in Communication Complexity Revisited. SIAM J. Comput. 22(1), 211–219 (1993)
Noam Nisan & David Zuckerman: Randomness is Linear in Space. J. Comput. Syst. Sci. 52(1), 43–52 (1996)
Papadimitriou, Christos H., Sipser, Michael: Communication Complexity. J. Comput. Syst. Sci. 28(2), 260–269 (1984)
Paturi, Ramamohan: Pavel Pudlák & Francis Zane (1999). Satisfiability Coding Lemma. Chicago J. Theor. Comput, Sci (1999)
Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio & Li-Yang Tan (2016). Poly-logarithmic Frege depth lower bounds via an expander switching lemma. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18–21, 2016, 644–657
Raz, Ran: A Parallel Repetition Theorem. SIAM J. Comput. 27(3), 763–803 (1998)
Ran Raz & Avi Wigderson (1989). Probabilistic Communication Complexity of Boolean Relations (Extended Abstract). In FOCS, 562–567
Ran Raz & Avi Wigderson: Monotone Circuits for Matching Require Linear Depth. J. ACM 39(3), 736–744 (1992)
A. A. Razborov (1992a). On Submodular Complexity Measures. In Poceedings of the London Mathematical Society Symposium on Boolean Function Complexity, 76–83. Cambridge University Press, New York, NY, USA. ISBN 0-521-40826-1
Razborov, Alexander A.: Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica 10(1), 81–93 (1990)
Alexander A. Razborov (1992b). On the Distributional Complexity of Disjointness. Theor. Comput. Sci. 106(2), 385–390
Smal, Alexander V., Talebanfard, Navid: Prediction from partial information and hindsight, an alternative proof. Inf. Process. Lett. 136, 102–104 (2018)
Emanuele Viola (2018). AC0 unpredictability. Electronic Colloquium on Computational Complexity (ECCC) 209
Acknowledgements
We would like to thank Oded Goldreich and Benjamin Rossman for valuable discussions and ideas. We would also like to thank Roei Tell for pointing out an error in the introduction of an earlier version of this work. Finally, we thank anonymous referees for comments that improved the presentation of this work and for pointing out connections to the work of Paturi et al. (1999).
Or Meir is partially supported by the Israel Science Foundation (Grant No. 1445/16). Part of this research was done while Or Meir was partially supported by NSF Grant CCF-1412958. Avi Wigderson was partially supported from NSF Grant CCF-1412958.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Meir, O., Wigderson, A. Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds. comput. complex. 28, 145–183 (2019). https://doi.org/10.1007/s00037-019-00177-4
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-019-00177-4
Keywords
- Certificate complexity
- Circuit complexity
- Circuit complexity lower bounds
- Decision tree complexity
- Information theoretic
- Query complexity
- Sensitivity