{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T02:01:06Z","timestamp":1648692066121},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,12,11]],"date-time":"2012-12-11T00:00:00Z","timestamp":1355184000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2013,9]]},"DOI":"10.1007\/s00037-012-0052-6","type":"journal-article","created":{"date-parts":[[2012,12,10]],"date-time":"2012-12-10T07:34:08Z","timestamp":1355124848000},"page":"595-622","source":"Crossref","is-referenced-by-count":3,"title":["Hadamard tensors and lower bounds on multiparty communication complexity"],"prefix":"10.1007","volume":"22","author":[{"given":"Jeff","family":"Ford","sequence":"first","affiliation":[]},{"given":"Anna","family":"G\u00e1l","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,12,11]]},"reference":[{"key":"52_CR1","unstructured":"N. Alon & J. H. Spencer (2000). The Probabilistic Method (second edition). John Willey & Sons."},{"key":"52_CR2","doi-asserted-by":"crossref","unstructured":"L. Babai, T. P. Hayes & P. G. Kimmel (1998). The Cost of the Missing Bit: Communication Complexity with Help. Proceedings of the 30th Annual ACM Symposium on Theory of Computing 673\u2013682.","DOI":"10.1145\/276698.276883"},{"issue":"2","key":"52_CR3","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/0022-0000(92)90047-M","volume":"45","author":"L. Babai","year":"1992","unstructured":"Babai L., Nisan N., Szegedy M. (1992) Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs. Journal of Computer and System Sciences 45(2): 204\u2013232","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"52_CR4","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. Barrington","year":"1989","unstructured":"Barrington D. (1989) Bounded-width polynomial size branching programs recognize exactly those languages in NC 1. Journal of Computer and System Sciences 38(1): 150\u2013164","journal-title":"Journal of Computer and System Sciences"},{"key":"52_CR5","unstructured":"P. Beame & D. Huynh-Ngoc (2009). Multiparty communication complexity and threshold circuit size of AC 0. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science 53\u201362."},{"key":"52_CR6","unstructured":"R. Beigel & J. Tarui (1991). On ACC. Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science 783\u2013792."},{"issue":"5","key":"52_CR7","first-page":"357","volume":"39","author":"M.R. Best","year":"1977","unstructured":"Best M.R. (1977) The Excess of a Hadamard Matrix. Indag. Math. 39(5): 357\u2013361","journal-title":"Math."},{"key":"52_CR8","unstructured":"A. Chandra, M. Furst & R. Lipton (1983). Multiparty protocols. Proceedings of the 15th Annual ACM Symposium on Theory of Computing 94\u201399."},{"key":"52_CR9","doi-asserted-by":"crossref","unstructured":"A. Chattopadhyay (2007). Discrepancy and the power of bottom fan-in depth-three circuits. Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science 449\u2013458.","DOI":"10.1109\/FOCS.2007.30"},{"key":"52_CR10","unstructured":"A. Chattopadhyay & A. Ada (2008). Multiparty communication complexity of disjointness, Technical report TR-08-002. Electronic Colloquium on Computational Complexity."},{"key":"52_CR11","first-page":"230","volume":"17","author":"B. Chor","year":"1988","unstructured":"Chor B., Goldreich O. (1988) Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity. SIAM J. Computing 17: 230\u2013261","journal-title":"Computing"},{"issue":"4","key":"52_CR12","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1002\/rsa.3240010401","volume":"1","author":"F. Chung","year":"1990","unstructured":"Chung F. (1990) Quasi-Random Classes of Hypergraphs. Random Structures and Algorithms 1(4): 363\u2013382","journal-title":"Random Structures and Algorithms"},{"issue":"1","key":"52_CR13","first-page":"110","volume":"6","author":"F. Chung","year":"1993","unstructured":"Chung F., Tetali P. (1993) Communication complexity and quasi randomness. SIAM J. Discrete Math. 6(1): 110\u2013123","journal-title":"Discrete Math."},{"key":"52_CR14","volume-title":"Probabilistic methods in combinatorics","author":"P. Erd\u0151s","year":"1974","unstructured":"Erd\u0151s P., Spencer J.H. (1974) Probabilistic methods in combinatorics. Academic Press, New York"},{"key":"52_CR15","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1006\/inco.1994.1051","volume":"112","author":"V. Grolmusz","year":"1994","unstructured":"Grolmusz V. (1994) The BNS Lower Bound for Multi-Party Protocols is Nearly Optimal. Information and Computation 112: 51\u201354","journal-title":"Information and Computation"},{"key":"52_CR16","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad & M. Goldmann (1991). On the power of small depth threshold circuits. Computational Complexity 113\u2013129.","DOI":"10.1007\/BF01272517"},{"key":"52_CR17","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1002\/jcd.20043","volume":"13","author":"H. Kharaghani","year":"2005","unstructured":"Kharaghani H., Tayfez-Rezaie B. (2005) A Hadamard matrix of order 428. Journal of Combinatorial Designs 13: 435\u2013440","journal-title":"Journal of Combinatorial Designs"},{"issue":"1","key":"52_CR18","first-page":"20","volume":"37","author":"H. Klauck","year":"2007","unstructured":"Klauck H. (2007) Lower bounds for quantum communication complexity. SIAM J. Comput. 37(1): 20\u201346","journal-title":"Comput."},{"key":"52_CR19","unstructured":"E. Kushilevitz & N. Nisan (1997). Communication complexity. Cambridge University Press."},{"issue":"2","key":"52_CR20","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/s00037-009-0276-2","volume":"18","author":"T. Lee","year":"2009","unstructured":"Lee T., Shraibman A. (2009) Disjointness is hard in the multi-party number-on-the-forehead model. Computational Complexity 18(2): 309\u2013336","journal-title":"Computational Complexity"},{"key":"52_CR21","unstructured":"J. H. van Lint & R. M. Wilson (1992). A course in combinatorics. Cambridge University Press."},{"key":"52_CR22","unstructured":"J.H. van Lint (1991). Introduction to Coding Theory. Springer-Verlag."},{"key":"52_CR23","first-page":"211","volume":"22","author":"N. Nisan","year":"1993","unstructured":"Nisan N., Wigderson A. (1993) Rounds in communication complexity revisited. SIAM J. Comp. 22: 211\u2013219","journal-title":"Comp."},{"key":"52_CR24","doi-asserted-by":"crossref","unstructured":"P. Pudl\u00e1k (1994). Unexpected upper bounds on the complexity of some communication games. Proceedings of the 21st International Colloquium on Automata, Languages and Programming 1\u201311.","DOI":"10.1007\/3-540-58201-0_53"},{"key":"52_CR25","first-page":"605","volume":"26","author":"P. Pudl\u00e1k","year":"1997","unstructured":"Pudl\u00e1k P., R\u00f6dl V., Sgall J. (1997) Boolean circuits, tensor ranks and communication complexity. SIAM J. Comp. 26: 605\u2013633","journal-title":"Comp."},{"issue":"2","key":"52_CR26","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/PL00001602","volume":"9","author":"R. Raz","year":"2000","unstructured":"Raz R. (2000) The BNS-Chung criterion for multiparty communication complexity. Computational Complexity 9(2): 113\u2013122","journal-title":"Computational Complexity"},{"key":"52_CR27","unstructured":"W. M. Schmidt (1978). Equations over finite fields: an elementary approach. Lecture Notes in Math., Springer Verlag 536."},{"key":"52_CR28","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1090\/S0025-5718-1990-0993933-0","volume":"54","author":"V. Shoup","year":"1990","unstructured":"Shoup V. (1990) New Algorithms for Finding Irreducible Polynomials over Finite Fields. Mathematics of Computation 54: 435\u2013447","journal-title":"Mathematics of Computation"},{"key":"52_CR29","unstructured":"J. Spencer (1987). Ten lectures on the probabilistic method. Society for Industrial and Applied Mathematics."},{"issue":"5","key":"52_CR30","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1073\/pnas.34.5.204","volume":"34","author":"A. Weil","year":"1948","unstructured":"Weil A. (1948) On some exponential sums. Proceedings of the National Academy of Sciences of the United States of America 34(5): 204\u2013207","journal-title":"Proceedings of the National Academy of Sciences of the United States of America"},{"key":"52_CR31","doi-asserted-by":"crossref","unstructured":"R. Williams (2011). Non-Uniform ACC Circuit Lower Bounds. To appear in Proc. of the 26th IEEE Conference on Computational Complexity.","DOI":"10.1109\/CCC.2011.36"},{"key":"52_CR32","unstructured":"A. Yao (1979). Some complexity questions related to distributed computing. Proceedings of the 11th Annual ACM Symposium on Theory of Computing 209\u2013213."},{"key":"52_CR33","doi-asserted-by":"crossref","unstructured":"A. Yao (1990). On ACC and threshold circuits. Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science 619\u2013627.","DOI":"10.1109\/FSCS.1990.89583"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0052-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-012-0052-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0052-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,6]],"date-time":"2019-07-06T17:57:19Z","timestamp":1562435839000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-012-0052-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,11]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["52"],"URL":"https:\/\/doi.org\/10.1007\/s00037-012-0052-6","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12,11]]}}}