{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:57:36Z","timestamp":1787385456864,"version":"build-2736575974"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"We investigate the relationship between circuit bottom fan-in and circuit size when circuit depth is fixed. We show that in order to compute certain functions, a moderate reduction in circuit bottom fan-in will cause significant increase in circuit size. In particular, we prove that there are functions that are computable by circuits of linear size and depth k with bottom fan-in 2 but require exponential size for circuits of depth k with bottom fan-in 1. A general scheme is established to study the trade-off between circuit bottom fan-in and circuit size. Based on this scheme, we are able to prove, for example, that for any integer c, there are functions that are computable by circuits of linear size and depth k with bottom fan-in $O(\\log n)$ but that require exponential size for circuits of depth k with bottom fan-in c, and that for any constant $\\epsilon> 0$, there are functions that are computable by circuits of linear size and depth k with bottom fan-in $\\log n$ but that require superpolynomial size for circuits of depth k with bottom fan-in $O(\\log^{1-\\epsilon} n)$. A consequence of these results is that the three input read-modes of alternating Turing machines proposed in the literature are all distinct.<\/jats:p>","DOI":"10.1137\/s0097539795282432","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"341-355","source":"Crossref","is-referenced-by-count":8,"title":["Circuit Bottom Fan-in and Computational Power"],"prefix":"10.1137","volume":"27","author":[{"given":"Liming","family":"Cai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianer","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johan","family":"H\u00e5stad","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(83)90038-6"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Ravi Boppana, Michael Sipser, The complexity of finite functions, Elsevier, Amsterdam, 1990, 757\u20138041127180","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"S. R. Buss,\n The Boolean formula value problem is in ALOGTIME\n , Proc. 19th Annual ACM Symposium on Theory of Computing, 1987, pp. 123\u2013131.","DOI":"10.1145\/28395.28409"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"L. Cai and J. Chen,\n \n Fixed parameter tractability and approximability of\n NP\n \u2010hard optimization problems\n \n , Proc. 2rd Israel Symposium on Theory of Computing and Systems, 1993, pp. 118\u2013126. Journal version to appear in J. Computer and System Sciences.","DOI":"10.1109\/ISTCS.1993.253478"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00253-F"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793258295"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1156"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90003-Z"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"R. L. Graham, D. E. Knuth, and O. Patashnik,\n Concrete Mathematics: A Foundation for Computer Science\n , Addison\u2010Wesley, Reading, MA, 1989.","DOI":"10.1063\/1.4822863"},{"key":"R14","unstructured":"J. H\u00e5stad,\n Computational Limitations for Small\u2010Depth Circuits\n , The MIT Press, Cambridge, MA, 1986."},{"key":"R15","unstructured":"J. H\u00e5stad,\n Almost optimal lower bounds for small depth circuits\n , in Advances in Computing Research 5, S. Micali, ed., JAI Press Inc., Greenwich, CT, 1989, pp. 143\u2013170."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90038-6"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"M. Sipser,\n Borel sets and circuit complexity\n , Proc. 15th Annual ACM Symposium on Theory of Computing, 1983, pp. 61\u201369.","DOI":"10.1145\/800061.808733"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"A. C. Yao,\n Separating the polynomial\u2010time hierarchy by oracles\n , Proc. 26th Annual IEEE Symposium on Foundations of Computer Science, 1985, pp. 1\u201310.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795282432","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:05Z","timestamp":1787335925000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795282432"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795282432"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795282432","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}