{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T10:56:50Z","timestamp":1780916210244,"version":"3.54.1"},"reference-count":76,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,3,22]],"date-time":"2018-03-22T00:00:00Z","timestamp":1521676800000},"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":[[2018,6]]},"DOI":"10.1007\/s00037-018-0166-6","type":"journal-article","created":{"date-parts":[[2018,3,22]],"date-time":"2018-03-22T10:16:20Z","timestamp":1521713780000},"page":"245-304","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["The Landscape of Communication Complexity Classes"],"prefix":"10.1007","volume":"27","author":[{"given":"Mika","family":"G\u00f6\u00f6s","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Watson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,3,22]]},"reference":[{"issue":"2063","key":"166_CR1","doi-asserted-by":"publisher","first-page":"3473","DOI":"10.1098\/rspa.2005.1546","volume":"461","author":"Scott Aaronson","year":"2005","unstructured":"Aaronson, Scott: Quantum Computing, Postselection, and Probabilistic Polynomial-Time. Proceedings of the Royal Society A 461(2063), 3473\u20133482 (2005)","journal-title":"Proceedings of the Royal Society A"},{"key":"166_CR2","doi-asserted-by":"crossref","unstructured":"Scott Aaronson & Avi Wigderson (2009). Algebrization: A New Barrier in Complexity Theory. ACM Transactions on Computation Theory 1(1).","DOI":"10.1145\/1490270.1490272"},{"key":"166_CR3","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Babai, Peter Frankl & Janos Simon (1986). Complexity Classes in Communication Complexity Theory. In Proceedings of the 27th Symposium on Foundations of Computer Science (FOCS), 337\u2013347. IEEE.","DOI":"10.1109\/SFCS.1986.15"},{"issue":"4","key":"166_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. Journal of Computer and System Sciences 68(4), 702\u2013732 (2004)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"166_CR5","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0304-3975(91)90160-4","volume":"84","author":"Richard Beigel","year":"1991","unstructured":"Beigel, Richard: Bounded Queries to SAT and the Boolean Hierarchy. Theoretical Computer Science 84(2), 199\u2013223 (1991)","journal-title":"Theoretical Computer Science"},{"issue":"1\u20133","key":"166_CR6","first-page":"80","volume":"55","author":"Andreas Blass & Yuri Gurevich","year":"1982","unstructured":"Andreas Blass & Yuri Gurevich: On the Unique Satisfiability Problem. Information and Control 55(1\u20133), 80\u201388 (1982)","journal-title":"Information and Control"},{"issue":"6","key":"166_CR7","doi-asserted-by":"publisher","first-page":"1043","DOI":"10.1016\/j.jcss.2006.05.001","volume":"72","author":"Elmar B\u00f6hler","year":"2006","unstructured":"B\u00f6hler, Elmar, Gla\u00dfer, Christian, Meister, Daniel: Error-Bounded Probabilistic Computations Between MA and AM. Journal of Computer and System Sciences 72(6), 1043\u20131076 (2006)","journal-title":"Journal of Computer and System Sciences"},{"key":"166_CR8","doi-asserted-by":"crossref","unstructured":"Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler & Prashant Vasudevan (2017). On the Power of Statistical Zero Knowledge. In Proceedings of the 58th Symposium on Foundations of Computer Science, 708\u2013719. IEEE.","DOI":"10.1109\/FOCS.2017.71"},{"key":"166_CR9","doi-asserted-by":"crossref","unstructured":"Harry Buhrman, Nikolai Vereshchagin & Ronald de\u00a0Wolf (2007). On Computation and Communication with Small Bias. In Proceedings of the 22nd Conference on Computational Complexity (CCC), 24\u201332. IEEE.","DOI":"10.1109\/CCC.2007.18"},{"issue":"1","key":"166_CR10","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.jcss.2003.07.015","volume":"73","author":"Jin-Yi Cai","year":"2007","unstructured":"Cai, Jin-Yi: $${\\rm S}_2{\\rm P} \\subseteq {\\rm ZPP}^{\\rm NP}$$ S 2 P \u2286 ZPP NP . Journal of Computer and System Sciences 73(1), 25\u201335 (2007)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"166_CR11","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10878-006-7130-0","volume":"11","author":"Jin-Yi Cai & Venkatesan Chakaravarthy","year":"2006","unstructured":"Jin-Yi Cai & Venkatesan Chakaravarthy: On Zero Error Algorithms Having Oracle Access to One Query. Journal of Combinatorial Optimization 11(2), 189\u2013202 (2006)","journal-title":"Journal of Combinatorial Optimization"},{"issue":"5","key":"166_CR12","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0020-0190(96)00016-6","volume":"57","author":"Ran Canetti","year":"1996","unstructured":"Canetti, Ran: More on BPP and the Polynomial-Time Hierarchy. Information Processing Letters 57(5), 237\u2013241 (1996)","journal-title":"Information Processing Letters"},{"key":"166_CR13","doi-asserted-by":"crossref","unstructured":"Amit Chakrabarti, Graham Cormode, Navin Goyal & Justin Thaler (2014a). Annotations for Sparse Data Streams. In Proceedings of the 25th Symposium on Discrete Algorithms (SODA), 687\u2013706. ACM-SIAM.","DOI":"10.1137\/1.9781611973402.52"},{"issue":"1","key":"166_CR14","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/2636924","volume":"11","author":"Amit Chakrabarti","year":"2014","unstructured":"Chakrabarti, Amit, Cormode, Graham, McGregor, Andrew, Thaler, Justin: Annotations in Data Streams. ACM Transactions on Algorithms 11(1), 7 (2014b)","journal-title":"ACM Transactions on Algorithms"},{"key":"166_CR15","unstructured":"Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler & Suresh Venkatasubramanian (2015). Verifiable Stream Computation and Arthur\u2013Merlin Communication. In Proceedings of the 30th Computational Complexity Conference (CCC), 217\u2013243. Schloss Dagstuhl."},{"issue":"3","key":"166_CR16","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1006\/jcss.1995.1028","volume":"50","author":"Richard Chang","year":"1995","unstructured":"Chang, Richard, Kadin, Jim, Rohatgi, Pankaj: On Unique Satisfiability and the Threshold Behavior of Randomized Reductions. Journal of Computer and System Sciences 50(3), 359\u2013373 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"166_CR17","unstructured":"Richard Chang & Suresh Purini (2008). Amplifying $${\\rm ZPP}^{\\rm SAT[1]}$$ ZPP SAT [ 1 ] and the Two Queries Problem. In Proceedings of the 23rd Conference on Computational Complexity (CCC), 41\u201352. IEEE."},{"key":"166_CR18","unstructured":"Arkadev Chattopadhyay & Nikhil Mande (2017). Weights at the Bottom Matter When the Top is Heavy. Technical Report TR17-083, Electronic Colloquium on Computational Complexity (ECCC). URL http:\/\/eccc.weizmann.ac.il\/report\/2017\/083\/ ."},{"issue":"2","key":"166_CR19","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.jcss.2004.03.002","volume":"69","author":"Carsten Damm","year":"2004","unstructured":"Damm, Carsten, Krause, Matthias, Meinel, Christoph, Waack, Stephan: On Relations Between Counting Communication Complexity Classes. Journal of Computer and System Sciences 69(2), 259\u2013280 (2004)","journal-title":"Journal of Computer and System Sciences"},{"key":"166_CR20","unstructured":"Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Lauri\u00e8re & J\u00e9r\u00e9mie Roland (2016). Relative Discrepancy Does Not Separate Information and Communication Complexity. ACM Transactions on Computation Theory 9(1), 4:1\u20134:15."},{"issue":"4","key":"166_CR21","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1016\/S0022-0000(02)00019-3","volume":"65","author":"J\u00fcrgen Forster","year":"2002","unstructured":"Forster, J\u00fcrgen: A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity. Journal of Computer and System Sciences 65(4), 612\u2013625 (2002)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"166_CR22","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s00037-008-0252-2","volume":"17","author":"Lance Fortnow","year":"2008","unstructured":"Fortnow, Lance, Impagliazzo, Russell, Kabanets, Valentine, Umans, Christopher: On the Complexity of Succinct Zero-Sum Games. Computational Complexity 17(3), 353\u2013376 (2008)","journal-title":"Computational Complexity"},{"key":"166_CR23","unstructured":"Anat Ganor, Gillat Kol & Ran Raz (2016). Exponential Separation of Information and Communication for Boolean Functions. Journal of the ACM 63(5), 46:1\u201346:31."},{"key":"166_CR24","unstructured":"Dmitry Gavinsky & Shachar Lovett (2014). En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), 514\u2013524. Springer."},{"issue":"1","key":"166_CR25","doi-asserted-by":"publisher","first-page":"227","DOI":"10.4086\/toc.2010.v006a010","volume":"6","author":"Dmitry Gavinsky & Alexander Sherstov","year":"2010","unstructured":"Dmitry Gavinsky & Alexander Sherstov: A Separation of NP and coNP in Multiparty Communication Complexity. Theory of Computing 6(1), 227\u2013245 (2010)","journal-title":"Theory of Computing"},{"key":"166_CR26","unstructured":"Oded Goldreich & David Zuckerman (2011). Another Proof That $$\\rm BPP\\it \\subseteq \\rm PH\\it $$ BPP \u2286 PH (and More). In Studies in Complexity and Cryptography, 40\u201353. Springer."},{"key":"166_CR27","doi-asserted-by":"crossref","unstructured":"Shafi Goldwasser & Michael Sipser (1986). Private Coins versus Public Coins in Interactive Proof Systems. In Proceedings of the 18th Symposium on Theory of Computing (STOC), 59\u201368. ACM.","DOI":"10.1145\/12130.12137"},{"key":"166_CR28","unstructured":"Mika G\u00f6\u00f6s, Pritish Kamath, Toniann Pitassi & Thomas Watson (2017). Query-to-Communication Lifting for $${\\rm P}^{\\rm NP}$$ P NP . In Proceedings of the 32nd Computational Complexity Conference (CCC), 12:1\u201312:16. Schloss Dagstuhl."},{"issue":"5","key":"166_CR29","doi-asserted-by":"publisher","first-page":"1835","DOI":"10.1137\/15M103145X","volume":"45","author":"Mika G\u00f6\u00f6s","year":"2016","unstructured":"G\u00f6\u00f6s, Mika, Lovett, Shachar, Meka, Raghu, Watson, Thomas, Zuckerman, David: Rectangles Are Nonnegative Juntas. SIAM Journal on Computing 45(5), 1835\u20131869 (2016a)","journal-title":"SIAM Journal on Computing"},{"key":"166_CR30","doi-asserted-by":"crossref","unstructured":"Mika G\u00f6\u00f6s, Toniann Pitassi & Thomas Watson (2016b). Zero-Information Protocols and Unambiguity in Arthur\u2013Merlin Communication. Algorithmica 76(3), 684\u2013719. Special issue on information complexity and applications.","DOI":"10.1007\/s00453-015-0104-9"},{"key":"166_CR31","unstructured":"Mika G\u00f6\u00f6s & Thomas Watson (2016). Communication Complexity of Set-Disjointness for All Probabilities. Theory of Computing 12(1), 1\u201323. Special issue for selected papers from APPROX\u2013RANDOM 2014."},{"issue":"4","key":"166_CR32","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s00224-003-1158-7","volume":"36","author":"Vince Grolmusz & G\u00e1bor Tardos","year":"2003","unstructured":"Vince Grolmusz & G\u00e1bor Tardos: A Note on Non-Deterministic Communication Complexity with Few Witnesses. Theory of Computing Systems 36(4), 387\u2013391 (2003)","journal-title":"Theory of Computing Systems"},{"key":"166_CR33","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.ic.2014.12.011","volume":"243","author":"Tom Gur & Ran Raz","year":"2015","unstructured":"Tom Gur & Ran Raz: Arthur-Merlin Streaming Complexity. Information and Computation 243, 145\u2013165 (2015)","journal-title":"Information and Computation"},{"key":"166_CR34","doi-asserted-by":"crossref","unstructured":"Tom Gur & Ron Rothblum (2015). Non-Interactive Proofs of Proximity. In Proceedings of the 6th Innovations in Theoretical Computer Science Conference (ITCS), 133\u2013142. ACM.","DOI":"10.1145\/2688073.2688079"},{"issue":"3","key":"166_CR35","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1016\/0022-0000(90)90027-I","volume":"41","author":"Bernd Halstenberg & R\u00fcdiger Reischuk","year":"1990","unstructured":"Bernd Halstenberg & R\u00fcdiger Reischuk: Relations Between Communication Complexity Classes. Journal of Computer and System Sciences 41(3), 402\u2013429 (1990)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"166_CR36","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1137\/S0097539792240467","volume":"26","author":"Yenjo Han","year":"1997","unstructured":"Han, Yenjo, Hemaspaandra, Lane, Thierauf, Thomas: Threshold Computation and Cryptographic Security. SIAM Journal on Computing 26(1), 59\u201378 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"166_CR37","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo & Ryan Williams (2010). Communication Complexity with Synchronized Clocks. In Proceedings of the 25th Conference on Computational Complexity (CCC), 259\u2013269. IEEE.","DOI":"10.1109\/CCC.2010.32"},{"key":"166_CR38","doi-asserted-by":"crossref","unstructured":"T.S. Jayram, Ravi Kumar & D.\u00a0Sivakumar (2003). Two Applications of Information Complexity. In Proceedings of the 35th Symposium on Theory of Computing (STOC), 673\u2013682. ACM.","DOI":"10.1145\/780542.780640"},{"issue":"6","key":"166_CR39","doi-asserted-by":"publisher","first-page":"855","DOI":"10.1017\/S0963548306007620","volume":"15","author":"Stasys Jukna","year":"2006","unstructured":"Jukna, Stasys: On Graph Complexity. Combinatorics, Probability, & Computing 15(6), 855\u2013876 (2006)","journal-title":"Combinatorics, Probability, & Computing"},{"key":"166_CR40","unstructured":"Stasys Jukna (2012). Boolean Function Complexity: Advances and Frontiers, volume\u00a027 of Algorithms and Combinatorics. Springer."},{"issue":"2","key":"166_CR41","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/s00454-014-9655-9","volume":"53","author":"Volker Kaibel & Stefan Weltge","year":"2015","unstructured":"Volker Kaibel & Stefan Weltge: A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially. Discrete & Computational Geometry 53(2), 397\u2013401 (2015)","journal-title":"Discrete & Computational Geometry"},{"issue":"2","key":"166_CR42","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/S0022-0000(05)80049-2","volume":"49","author":"Mauricio Karchmer","year":"1994","unstructured":"Karchmer, Mauricio, Newman, Ilan, Saks, Michael, Wigderson, Avi: Non-Deterministic Communication Complexity with Few Witnesses. Journal of Computer and System Sciences 49(2), 247\u2013257 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"166_CR43","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck (2003). Rectangle Size Bounds and Threshold Covers in Communication Complexity. In Proceedings of the 18th Conference on Computational Complexity (CCC), 118\u2013134. IEEE.","DOI":"10.1109\/CCC.2003.1214415"},{"issue":"1","key":"166_CR44","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1137\/S0097539702405620","volume":"37","author":"Hartmut Klauck","year":"2007","unstructured":"Klauck, Hartmut: Lower Bounds for Quantum Communication Complexity. SIAM Journal on Computing 37(1), 20\u201346 (2007)","journal-title":"SIAM Journal on Computing"},{"key":"166_CR45","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck (2010). A Strong Direct Product Theorem for Disjointness. In Proceedings of the 42nd Symposium on Theory of Computing (STOC), 77\u201386. ACM.","DOI":"10.1145\/1806689.1806702"},{"key":"166_CR46","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck (2011). On Arthur Merlin Games in Communication Complexity. In Proceedings of the 26th Conference on Computational Complexity (CCC), 189\u2013199. IEEE.","DOI":"10.1109\/CCC.2011.33"},{"key":"166_CR47","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck & Ved Prakash (2013). Streaming Computations with a Loquacious Prover. In Proceedings of the 4th Innovations in Theoretical Computer Science Conference (ITCS), 305\u2013320. ACM.","DOI":"10.1145\/2422436.2422471"},{"key":"166_CR48","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck & Ved Prakash (2014). An Improved Interactive Streaming Algorithm for the Distinct Elements Problem. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), 919\u2013930. Springer.","DOI":"10.1007\/978-3-662-43948-7_76"},{"key":"166_CR49","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz & Noam Nisan (1997). Communication Complexity. Cambridge University Press.","DOI":"10.1016\/S0065-2458(08)60342-3"},{"issue":"2","key":"166_CR50","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1016\/0022-0000(92)90025-E","volume":"44","author":"Tak Wah Lam & Walter Ruzzo","year":"1992","unstructured":"Tak Wah Lam & Walter Ruzzo: Results on Communication Complexity Classes. Journal of Computer and System Sciences 44(2), 324\u2013342 (1992)","journal-title":"Journal of Computer and System Sciences"},{"key":"166_CR51","doi-asserted-by":"crossref","unstructured":"Jianhua Lin (1991). Divergence Measures Based on the Shannon Entropy. IEEE Transactions on Information Theory 37(1), 145\u2013151. ISSN 0018-9448.","DOI":"10.1109\/18.61115"},{"issue":"1\u20132","key":"166_CR52","first-page":"227","volume":"18","author":"Nathan Linial & Adi Shraibman","year":"2009","unstructured":"Nathan Linial & Adi Shraibman: Learning Complexity vs Communication Complexity. Combinatorics, Probability, & Computing 18(1\u20132), 227\u2013245 (2009)","journal-title":"Combinatorics, Probability, & Computing"},{"issue":"3","key":"166_CR53","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1006\/jcss.2001.1786","volume":"63","author":"Satyanarayana Lokam","year":"2001","unstructured":"Lokam, Satyanarayana: Spectral Methods for Matrix Rigidity with Applications to Size-Depth Trade-offs and Communication Complexity. Journal of Computer and System Sciences 63(3), 449\u2013473 (2001)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1\u20132","key":"166_CR54","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/0400000011","volume":"4","author":"Satyanarayana Lokam","year":"2009","unstructured":"Lokam, Satyanarayana: Complexity Lower Bounds using Linear Algebra. Foundations and Trends in Theoretical Computer Science 4(1\u20132), 1\u2013155 (2009)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"166_CR55","doi-asserted-by":"crossref","unstructured":"Ilan Newman (1991). Private vs. Common Random Bits in Communication Complexity. Information Processing Letters 39(2), 67\u201371.","DOI":"10.1016\/0020-0190(91)90157-D"},{"issue":"2","key":"166_CR56","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"Noam Nisan & Avi Wigderson","year":"1994","unstructured":"Noam Nisan & Avi Wigderson: Hardness vs. Randomness. Journal of Computer and System Sciences 49(2), 149\u2013167 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"166_CR57","unstructured":"Ryan O'Donnell & A.\u00a0C.\u00a0Cem Say (2016). The Weakness of CTC Qubits and the Power of Approximate Counting. Technical Report TR16-147, Electronic Colloquium on Computational Complexity (ECCC). URL http:\/\/eccc.hpi-web.de\/report\/2016\/147\/ ."},{"issue":"2","key":"166_CR58","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"Christos Papadimitriou & Mihalis Yannakakis","year":"1984","unstructured":"Christos Papadimitriou & Mihalis Yannakakis: The Complexity of Facets (and Some Facets of Complexity). Journal of Computer and System Sciences 28(2), 244\u2013259 (1984)","journal-title":"Journal of Computer and System Sciences"},{"key":"166_CR59","doi-asserted-by":"crossref","unstructured":"Periklis Papakonstantinou, Dominik Scheder & Hao Song (2014). Overlays and Limited Memory Communication. In Proceedings of the 29th Conference on Computational Complexity (CCC), 298\u2013308. IEEE.","DOI":"10.1109\/CCC.2014.37"},{"issue":"1","key":"166_CR60","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/0022-0000(86)90046-2","volume":"33","author":"Ramamohan Paturi & Janos Simon","year":"1986","unstructured":"Ramamohan Paturi & Janos Simon: Probabilistic Communication Complexity. Journal of Computer and System Sciences 33(1), 106\u2013123 (1986)","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"166_CR61","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF00279952","volume":"25","author":"Pavel Pudl\u00e1k","year":"1988","unstructured":"Pudl\u00e1k, Pavel, R\u00f6dl, Vojtech, Savick\u00fd, Petr: Graph Complexity. Acta Informatica 25(5), 515\u2013535 (1988)","journal-title":"Acta Informatica"},{"key":"166_CR62","doi-asserted-by":"crossref","unstructured":"Ran Raz & Amir Shpilka (2004). On the Power of Quantum Proofs. In Proceedings of the 19th Conference on Computational Complexity (CCC), 260\u2013274. IEEE.","DOI":"10.1109\/CCC.2004.1313849"},{"key":"166_CR63","volume-title":"On Rigid Matrices","author":"Alexander Razborov","year":"1989","unstructured":"Razborov, Alexander: On Rigid Matrices. Technical report, Steklov Mathematical Institute (1989). In Russian"},{"issue":"2","key":"166_CR64","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"Alexander Razborov","year":"1992","unstructured":"Razborov, Alexander: On the Distributional Complexity of Disjointness. Theoretical Computer Science 106(2), 385\u2013390 (1992)","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"166_CR65","doi-asserted-by":"publisher","first-page":"1833","DOI":"10.1137\/080744037","volume":"39","author":"Alexander Razborov & Alexander Sherstov","year":"2010","unstructured":"Alexander Razborov & Alexander Sherstov: The Sign-Rank of $${\\rm AC}^0$$ AC 0 . SIAM Journal on Computing 39(5), 1833\u20131855 (2010)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"166_CR66","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/s000370050007","volume":"7","author":"Alexander Russell & Ravi Sundaram","year":"1998","unstructured":"Alexander Russell & Ravi Sundaram: Symmetric Alternation Captures BPP. Computational Complexity 7(2), 152\u2013162 (1998)","journal-title":"Computational Complexity"},{"issue":"2","key":"166_CR67","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s00037-008-0242-4","volume":"17","author":"Alexander Sherstov","year":"2008","unstructured":"Sherstov, Alexander: Halfspace Matrices. Computational Complexity 17(2), 149\u2013178 (2008)","journal-title":"Computational Complexity"},{"issue":"6","key":"166_CR68","doi-asserted-by":"publisher","first-page":"1969","DOI":"10.1137\/080733644","volume":"40","author":"Alexander Sherstov","year":"2011","unstructured":"Sherstov, Alexander: The Pattern Matrix Method. SIAM Journal on Computing 40(6), 1969\u20132000 (2011a)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"166_CR69","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1007\/s00493-011-2580-0","volume":"31","author":"Alexander Sherstov","year":"2011","unstructured":"Sherstov, Alexander: The Unbounded-Error Communication Complexity of Symmetric Functions. Combinatorica 31(5), 583\u2013614 (2011b)","journal-title":"Combinatorica"},{"issue":"5","key":"166_CR70","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"Seinosuke Toda","year":"1991","unstructured":"Toda, Seinosuke: PP is as Hard as the Polynomial-Time Hierarchy. SIAM Journal on Computing 20(5), 865\u2013877 (1991)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"166_CR71","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s00224-008-9126-x","volume":"46","author":"Rahul Tripathi","year":"2010","unstructured":"Tripathi, Rahul: The 1-Versus-2 Queries Problem Revisited. Theory of Computing Systems 46(2), 193\u2013221 (2010)","journal-title":"Theory of Computing Systems"},{"key":"166_CR72","doi-asserted-by":"crossref","unstructured":"Leslie Valiant (1977). Graph-Theoretic Arguments in Low-Level Complexity. In Proceedings of the 6th Symposium on Mathematical Foundations of Computer Science (MFCS), 162\u2013176. Springer.","DOI":"10.1007\/3-540-08353-7_135"},{"issue":"3","key":"166_CR73","first-page":"85","volume":"47","author":"Leslie Valiant & Vijay Vazirani","year":"1986","unstructured":"Leslie Valiant & Vijay Vazirani: NP is as Easy as Detecting Unique Solutions. Theoretical Computer Science 47(3), 85\u201393 (1986)","journal-title":"Theoretical Computer Science"},{"key":"166_CR74","doi-asserted-by":"crossref","unstructured":"Nikolai Vereshchagin (1995). Lower Bounds for Perceptrons Solving some Separation Problems and Oracle Separation of AM from PP. In Proceedings of the 3rd Israel Symposium on Theory of Computing and Systems (ISTCS), 46\u201351. IEEE.","DOI":"10.1109\/ISTCS.1995.377047"},{"key":"166_CR75","doi-asserted-by":"crossref","unstructured":"Nikolai Vereshchagin (1999). Relativizability in Complexity Theory. In Provability, Complexity, Grammars, volume 192 of AMS Translations, Series 2, 87\u2013172. American Mathematical Society.","DOI":"10.1090\/trans2\/192\/03"},{"issue":"3","key":"166_CR76","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s00037-011-0021-5","volume":"21","author":"Henning Wunderlich","year":"2012","unstructured":"Wunderlich, Henning: On a Theorem of Razborov. Computational Complexity 21(3), 431\u2013477 (2012)","journal-title":"Computational Complexity"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-018-0166-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-018-0166-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-018-0166-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T18:46:49Z","timestamp":1693594009000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-018-0166-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,22]]},"references-count":76,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["166"],"URL":"https:\/\/doi.org\/10.1007\/s00037-018-0166-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,22]]},"assertion":[{"value":"2 May 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2018","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}