{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T00:52:38Z","timestamp":1778028758983,"version":"3.51.4"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,4,6]],"date-time":"2019-04-06T00:00:00Z","timestamp":1554508800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00037-019-00177-4","type":"journal-article","created":{"date-parts":[[2019,4,7]],"date-time":"2019-04-07T01:44:59Z","timestamp":1554601499000},"page":"145-183","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds"],"prefix":"10.1007","volume":"28","author":[{"given":"Or","family":"Meir","sequence":"first","affiliation":[]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,4,6]]},"reference":[{"issue":"1","key":"177_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"Mikl\u00f3s Ajtai","year":"1983","unstructured":"Ajtai, Mikl\u00f3s: $$\\Sigma _1^1$$ \u03a3 1 1 -Formulae on finite structures. Annals of Pure and Applied Logic 24(1), 1\u201348 (1983)","journal-title":"Annals of Pure and Applied Logic"},{"key":"177_CR2","volume-title":"Boolean Complexity and Probabilistic Constructions, 140\u2013164","author":"Mikl\u00f3s Ajtai","year":"1992","unstructured":"Ajtai, Mikl\u00f3s: Boolean Complexity and Probabilistic Constructions, 140\u2013164. London Mathematical Society Lecture Note Series, Cambridge University Press (1992)"},{"key":"177_CR3","unstructured":"Mikl\u00f3s Ajtai (1993). Geometric Properties of Sets Defined by Constant Depth Circuits. In Combinatorics, Paul Erd\u0151s is eighty. Budapest, Hungary : J\u00e1nos Bolyai Mathematical Society. ISBN 9638022736 (set)"},{"issue":"4","key":"177_CR4","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.jcss.2003.11.006","volume":"68","author":"TS Ziv Bar-Yossef","year":"2004","unstructured":"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\u2013732 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"177_CR5","unstructured":"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"},{"issue":"5","key":"177_CR6","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0020-0190(97)00131-2","volume":"63","author":"Ravi B Boppana","year":"1997","unstructured":"Boppana, Ravi B.: The Average Sensitivity of Bounded-Depth Circuits. Inf. Process. Lett. 63(5), 257\u2013261 (1997)","journal-title":"Inf. Process. Lett."},{"key":"177_CR7","unstructured":"Xi\u00a0Chen, Igor\u00a0Carboni Oliveira, Rocco\u00a0A. 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\u201321, 2016, 612\u2013625"},{"key":"177_CR8","unstructured":"Thomas\u00a0M. Cover & Joy\u00a0A. Thomas (1991). Elements of information theory. Wiley-Interscience. ISBN 0-471-06259-6"},{"key":"177_CR9","unstructured":"Irit Dinur & Or\u00a0Meir (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\u20133:51"},{"issue":"1","key":"177_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(87)90037-X","volume":"73","author":"Pavol Duris","year":"1987","unstructured":"Duris, Pavol, Galil, Zvi, Schnitger, Georg: Lower Bounds on Communication Complexity. Inf. Comput. 73(1), 1\u201322 (1987)","journal-title":"Inf. Comput."},{"issue":"3","key":"177_CR11","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/s00037-001-8195-x","volume":"10","author":"Jeff Edmonds","year":"2001","unstructured":"Edmonds, Jeff, Impagliazzo, Russell, Rudich, Steven, Sgall, Jiri: Communication complexity towards lower bounds on circuit depth. Computational Complexity 10(3), 210\u2013246 (2001)","journal-title":"Computational Complexity"},{"issue":"1","key":"177_CR12","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"Merrick L Furst","year":"1984","unstructured":"Furst, Merrick L., Saxe, James B., Sipser, Michael: Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory 17(1), 13\u201327 (1984)","journal-title":"Mathematical Systems Theory"},{"key":"177_CR13","doi-asserted-by":"crossref","unstructured":"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\u201321, 2014, 176\u2013185","DOI":"10.1109\/FOCS.2014.27"},{"key":"177_CR14","doi-asserted-by":"crossref","unstructured":"Dmitry Gavinsky, Or\u00a0Meir, 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\u2013222","DOI":"10.1145\/2591796.2591856"},{"key":"177_CR15","unstructured":"Michelangelo Grigni & Michael Sipser (1991). Monotone Separation of Logspace from NC. In Structure in Complexity Theory Conference, 294\u2013298"},{"key":"177_CR16","first-page":"61","volume":"25","author":"Aryeh Grinberg","year":"2018","unstructured":"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)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"177_CR17","doi-asserted-by":"crossref","unstructured":"Johan H\u00e5stad (1986). Almost Optimal Lower Bounds for Small Depth Circuits. In STOC, 6\u201320","DOI":"10.1145\/12130.12132"},{"issue":"2","key":"177_CR18","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01268140","volume":"5","author":"Johan H\u00e5stad","year":"1995","unstructured":"H\u00e5stad, Johan, Jukna, Stasys, Pudl\u00e1k, Pavel: Top-Down Lower Bounds for Depth-Three Circuits. Computational Complexity 5(2), 99\u2013112 (1995)","journal-title":"Computational Complexity"},{"key":"177_CR19","doi-asserted-by":"crossref","unstructured":"Hossein Jowhari, Mert S\u0103glam & G\u00e1bor 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\u201316, 2011, Athens, Greece, 49\u201358","DOI":"10.1145\/1989284.1989289"},{"key":"177_CR20","doi-asserted-by":"crossref","unstructured":"Mauricio Karchmer, Eyal Kushilevitz & Noam Nisan (1995a). Fractional Covers and Communication Complexity. SIAM J. Discrete Math. 8(1), 76\u201392","DOI":"10.1137\/S0895480192238482"},{"key":"177_CR21","doi-asserted-by":"crossref","unstructured":"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\u2013204","DOI":"10.1007\/BF01206317"},{"issue":"2","key":"177_CR22","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/0403021","volume":"3","author":"Mauricio Karchmer & Avi Wigderson","year":"1990","unstructured":"Mauricio Karchmer & Avi Wigderson: Monotone Circuits for Connectivity Require Super-Logarithmic Depth. SIAM J. Discrete Math. 3(2), 255\u2013265 (1990)","journal-title":"SIAM J. Discrete Math."},{"key":"177_CR23","first-page":"474","volume":"10","author":"VM Khrapchenko","year":"1972","unstructured":"Khrapchenko, V.M.: A method of obtaining lower bounds for the complexity of $$\\pi $$ \u03c0 -schemes. Mathematical Notes Academy of Sciences USSR 10, 474\u2013479 (1972)","journal-title":"Mathematical Notes Academy of Sciences USSR"},{"key":"177_CR24","unstructured":"Maria\u00a0M. Klawe, Wolfgang\u00a0J. 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\u2013487"},{"key":"177_CR25","doi-asserted-by":"crossref","unstructured":"Gillat Kol & Ran Raz (2013). Interactive channel capacity. In Symposium on Theory of Computing onference, STOC'13, Palo Alto, CA, USA, June 1\u20134, 2013, 715\u2013724","DOI":"10.1145\/2488608.2488699"},{"issue":"3","key":"177_CR26","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"Nathan Linial","year":"1993","unstructured":"Linial, Nathan, Mansour, Yishay, Nisan, Noam: Constant Depth Circuits, Fourier Transform, and Learnability. J. ACM 40(3), 607\u2013620 (1993)","journal-title":"J. ACM"},{"key":"177_CR27","unstructured":"Lyle\u00a0A. Mcgeoch (1986). A Strong Separation betweem $$k$$ k and $$k-1$$ k - 1 Round Communication Complexity for a Constructive Language. Technical Report CMU-CS-86-157, Carnegie Mellon University"},{"key":"177_CR28","first-page":"129","volume":"24","author":"Or Meir","year":"2017","unstructured":"Meir, Or: An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Three Rounds. Electronic Colloquium on Computational Complexity (ECCC) 24, 129 (2017)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"issue":"1","key":"177_CR29","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1137\/0222016","volume":"22","author":"Noam Nisan & Avi Wigderson","year":"1993","unstructured":"Noam Nisan & Avi Wigderson: Rounds in Communication Complexity Revisited. SIAM J. Comput. 22(1), 211\u2013219 (1993)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"177_CR30","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1006\/jcss.1996.0004","volume":"52","author":"Noam Nisan & David Zuckerman","year":"1996","unstructured":"Noam Nisan & David Zuckerman: Randomness is Linear in Space. J. Comput. Syst. Sci. 52(1), 43\u201352 (1996)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"177_CR31","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/0022-0000(84)90069-2","volume":"28","author":"Christos H Papadimitriou","year":"1984","unstructured":"Papadimitriou, Christos H., Sipser, Michael: Communication Complexity. J. Comput. Syst. Sci. 28(2), 260\u2013269 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"177_CR32","volume-title":"Pavel Pudl\u00e1k & Francis Zane (1999)","author":"Ramamohan Paturi","year":"1999","unstructured":"Paturi, Ramamohan: Pavel Pudl\u00e1k & Francis Zane (1999). Satisfiability Coding Lemma. Chicago J. Theor. Comput, Sci (1999)"},{"key":"177_CR33","doi-asserted-by":"crossref","unstructured":"Toniann Pitassi, Benjamin Rossman, Rocco\u00a0A. 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\u201321, 2016, 644\u2013657","DOI":"10.1145\/2897518.2897637"},{"issue":"3","key":"177_CR34","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"Ran Raz","year":"1998","unstructured":"Raz, Ran: A Parallel Repetition Theorem. SIAM J. Comput. 27(3), 763\u2013803 (1998)","journal-title":"SIAM J. Comput."},{"key":"177_CR35","unstructured":"Ran Raz & Avi Wigderson (1989). Probabilistic Communication Complexity of Boolean Relations (Extended Abstract). In FOCS, 562\u2013567"},{"issue":"3","key":"177_CR36","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1145\/146637.146684","volume":"39","author":"Ran Raz & Avi Wigderson","year":"1992","unstructured":"Ran Raz & Avi Wigderson: Monotone Circuits for Matching Require Linear Depth. J. ACM 39(3), 736\u2013744 (1992)","journal-title":"J. ACM"},{"key":"177_CR37","doi-asserted-by":"crossref","unstructured":"A.\u00a0A. Razborov (1992a). On Submodular Complexity Measures. In Poceedings of the London Mathematical Society Symposium on Boolean Function Complexity, 76\u201383. Cambridge University Press, New York, NY, USA. ISBN 0-521-40826-1","DOI":"10.1017\/CBO9780511526633.007"},{"issue":"1","key":"177_CR38","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02122698","volume":"10","author":"Alexander A Razborov","year":"1990","unstructured":"Razborov, Alexander A.: Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica 10(1), 81\u201393 (1990)","journal-title":"Combinatorica"},{"key":"177_CR39","doi-asserted-by":"crossref","unstructured":"Alexander\u00a0A. Razborov (1992b). On the Distributional Complexity of Disjointness. Theor. Comput. Sci. 106(2), 385\u2013390","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"177_CR40","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.ipl.2018.04.011","volume":"136","author":"Alexander V Smal","year":"2018","unstructured":"Smal, Alexander V., Talebanfard, Navid: Prediction from partial information and hindsight, an alternative proof. Inf. Process. Lett. 136, 102\u2013104 (2018)","journal-title":"Inf. Process. Lett."},{"key":"177_CR41","unstructured":"Emanuele Viola (2018). AC0 unpredictability. Electronic Colloquium on Computational Complexity (ECCC) 209"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-019-00177-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-019-00177-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-019-00177-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T13:24:57Z","timestamp":1694784297000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-019-00177-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,6]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["177"],"URL":"https:\/\/doi.org\/10.1007\/s00037-019-00177-4","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,6]]},"assertion":[{"value":"19 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 April 2019","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}