{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:55:02Z","timestamp":1725512102856},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540792277"},{"type":"electronic","value":"9783540792284"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79228-4_30","type":"book-chapter","created":{"date-parts":[[2008,4,29]],"date-time":"2008-04-29T05:07:56Z","timestamp":1209445676000},"page":"342-350","source":"Crossref","is-referenced-by-count":1,"title":["A Well-Mixed Function with Circuit Complexity 5n \u00b1o(n): Tightness of the Lachish-Raz-Type Bounds"],"prefix":"10.1007","author":[{"given":"Kazuyuki","family":"Amano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Tarui","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1006\/jnth.1996.0029","volume":"56","author":"N. Alon","year":"1996","unstructured":"Alon, N., Nathanson, M.B., Ruzsa, I.: The Polynomial Method and Restricted Sums of Congruence Classes. J. Number Theory\u00a056, 404\u2013417 (1996)","journal-title":"J. Number Theory"},{"doi-asserted-by":"crossref","unstructured":"Andreev, A., Baskakov, J., Clementi, A., Rolim, J.: Small Pseudo-Random Sets yields Hard Functions: New Tight Explicit Lower Bounds for Branching Programs. In: Proc. 26th ICALP, pp. 179???189 (1999);","key":"#cr-split#-30_CR2.1","DOI":"10.1007\/3-540-48523-6_15"},{"unstructured":"Also in ECCC TR97-053 (1997)","key":"#cr-split#-30_CR2.2"},{"issue":"12","key":"30_CR3","doi-asserted-by":"publisher","first-page":"1580","DOI":"10.1109\/T-C.1971.223175","volume":"C-20","author":"C.C. Forster","year":"1971","unstructured":"Forster, C.C., Stockton, F.D.: Counting Responders in an Associative Memory. IEEE Trans. Comput.\u00a0C-20(12), 1580\u20131583 (1971)","journal-title":"IEEE Trans. Comput."},{"key":"30_CR4","volume-title":"An Introduction to the Theory of Numbers","author":"G.H. Hardy","year":"1978","unstructured":"Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 5th edn. Oxford University Press, Oxford (1978)","edition":"5"},{"doi-asserted-by":"crossref","unstructured":"Iwama, K., Morizumi, H.: An Explicit Lower Bound of 5n\u2009\u2212\u2009o(n) for Boolean Circuits. In: Proc. 27th MFCS, pp. 353\u2013364 (2002)","key":"30_CR5","DOI":"10.1007\/3-540-45687-2_29"},{"unstructured":"Iwama, K., Lachish, O., Morizumi, H., Raz, R.: An Explicit Lower Bound of 5n \u2212 o(n) for Boolean Circuits (manuscript, 2005), (preliminary versions are [9] and [5]), http:\/\/www.wisdom.weizmann.ac.il\/~ranraz\/publications\/","key":"30_CR6"},{"key":"30_CR7","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0304-3975(88)90166-1","volume":"57","author":"S.P. Jukna","year":"1988","unstructured":"Jukna, S.P.: Entropy of Contact Circuits and Lower Bounds on Their Complexity. Theoret. Comput. Sci.\u00a057, 113\u2013129 (1988)","journal-title":"Theoret. Comput. Sci."},{"issue":"8","key":"30_CR8","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1109\/TC.1980.1675657","volume":"29","author":"P. Klein","year":"1980","unstructured":"Klein, P., Paterson, M.S.: Asymptotically Optimal Circuit for a Storage Access Function. IEEE Trans. Comput.\u00a029(8), 737\u2013738 (1980)","journal-title":"IEEE Trans. Comput."},{"doi-asserted-by":"crossref","unstructured":"Lachish, O., Raz, R.: Explicit Lower Bound of 4.5n\u2009\u2212\u2009o(n) for Boolean Circuits. In: Proc. 33rd STOC, pp. 399\u2013408 (2001)","key":"30_CR9","DOI":"10.1145\/380752.380832"},{"unstructured":"Savick\u00fd, P., Z\u00e1k, S.: A Large Lower Bound for 1-Branching Programs. ECCC TR96-036 Rev.01 (1996)","key":"30_CR10"},{"key":"30_CR11","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1112\/blms\/26.2.140","volume":"26","author":"J.A. Dias da Silva","year":"1994","unstructured":"Dias da Silva, J.A., Hamidoune, Y.O.: Cyclic Spaces for Grassmann Derivatives and Additive Theory. Bull. London. Math. Soc.\u00a026, 140\u2013146 (1994)","journal-title":"Bull. London. Math. Soc."},{"doi-asserted-by":"crossref","unstructured":"Simon, J., Szegedy, M.: A New Lower Bound Theorem for Read Only Once Branching Programs and its Applications. In: Advances in Computational Complexity Theory, DIMACS Series, vol.\u00a013, pp. 183\u2013193 (1993)","key":"30_CR12","DOI":"10.1090\/dimacs\/013\/11"},{"doi-asserted-by":"crossref","unstructured":"Wegener, I.: The Complexity of Boolean Functions, Willey-Teubner (1987)","key":"30_CR13","DOI":"10.1007\/3-540-18170-9_185"},{"key":"30_CR14","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1137\/0220032","volume":"20","author":"U. Zwick","year":"1991","unstructured":"Zwick, U.: A 4n Lower Bound on the Combinatorial Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions. SIAM J. Comput.\u00a020, 499\u2013505 (1991)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79228-4_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:14:18Z","timestamp":1619522058000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79228-4_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540792277","9783540792284"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79228-4_30","relation":{},"subject":[]}}