{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:21Z","timestamp":1787337501339,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>A theorem of Markov precisely determines the number r of NEGATION gates necessary and sufficient to compute a system of boolean functions F. For a system of boolean functions on n variables, $r\\leq b(n)=\\lceil\\log_2(n+1)\\rceil$. We call a circuit using b(n) NEGATION gates negation-limited. We continue recent investigations into negation-limited circuit complexity, giving both upper and lower bounds.<\/jats:p>\n                  <jats:p>\n                    A circuit with inputs x\n                    <jats:sub>1<\/jats:sub>\n                    ,..., x\n                    <jats:sub>n<\/jats:sub>\n                    and outputs $\\neg x_1, \\ldots, \\neg x_n$ is called an inverter, for which $r=\\lceil\\log_2(n+1)\\rceil$. Fischer has constructed negation-limited inverters of size O(n\n                    <jats:sup>2<\/jats:sup>\n                    log n) and depth O(log n). Recently, Tanaka and Nishino have reduced the circuit size to O(n log\n                    <jats:sup>2<\/jats:sup>\n                    n) at the expense of increasing the depth to log\n                    <jats:sup>2<\/jats:sup>\n                    n. We construct negation-limited inverters of size O(n log n), with depth only O(log n), and we conjecture that this is optimal. We also improve a technique of Valiant for constructing monotone circuits for slice functions (introduced by Berkowitz).\n                  <\/jats:p>\n                  <jats:p>Next, we introduce some lower bound techniques for negation-limited circuits. We provide a 5n+3 log(n+1)-c lower bound for the size of a negation-limited inverter. In addition, we show that for two different restricted classes of circuit, negation-limited inverters require superlinear size.<\/jats:p>","DOI":"10.1137\/s0097539794275136","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1334-1347","source":"Crossref","is-referenced-by-count":21,"title":["On the Complexity of Negation-Limited Boolean Networks"],"prefix":"10.1137","volume":"27","author":[{"given":"Robert","family":"Beals","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tetsuro","family":"Nishino","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Keisuke","family":"Tanaka","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di,\n                      An O(nlogn) sorting network\n                      , in Proc. 15th Annual ACM Symposium on the Theory of Computing, ACM, New York, 1983, pp. 1\u20139.","DOI":"10.1145\/800061.808726"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1968.227401"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579196"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"K. E. Batcher,\n                      Sorting networks and their applications\n                      , in Proc. 32nd Annual AFIPS Spring Joint Computer Conference, 1968, pp. 307\u2013314.","DOI":"10.1145\/1468075.1468121"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"R. Beals, T. Nishino, and K. Tanaka,\n                      More on the complexity of negation\u2010limited circuits\n                      , in Proc. 27th Annual ACM Symposium on the Theory of Computing, ACM, New York, 1995, pp. 585\u2013595.","DOI":"10.1145\/225058.225276"},{"key":"R6","unstructured":"S. J. Berkowitz,\n                      On Some Relationships between Monotone and Non\u2010Monotone Circuit Complexity\n                      , Technical Report, University of Toronto, Ontario, Canada, 1982."},{"key":"R7","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":"R8","doi-asserted-by":"crossref","unstructured":"Michael Fischer, The complexity of negation\u2010limited networks\u2013a brief survey, Springer, Berlin, 1975, 0\u20130, 71\u201382. Lecture Notes in Comput. Sci., Vol. 3353:4614","DOI":"10.1007\/3-540-07407-4_9"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Edmund Lamagna, John Savage, Combinational complexity of some monotone functions, IEEE Comput. Soc., Long Beach, Calif., 1974, 140\u201314454:4842","DOI":"10.1109\/SWAT.1974.9"},{"key":"R10","unstructured":"D. Long,\n                      The Monotone Circuit Complexity of Threshold Functions\n                      , unpublished manuscript, Oxford University, Oxford, UK, 1986."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/320941.320945"},{"key":"R12","unstructured":"S. Muroga,\n                      Threshold Logic and Its Applications\n                      , Wiley, New York, 1971."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Nicholas Pippenger, Communication networks, Elsevier, Amsterdam, 1990, 805\u20138331127181","DOI":"10.1016\/B978-0-444-88071-0.50020-5"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146684"},{"key":"R15","first-page":"354","volume":"31","author":"Razborov A. A.","year":"1985","journal-title":"Soviet Math. Dokl.","ISSN":"https:\/\/id.crossref.org\/issn\/0197-6788","issn-type":"print"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0222022"},{"key":"R17","unstructured":"J. E. Savage,\n                      The Complexity of Computing\n                      , Wiley, New York, 1976."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"K. Tanaka and T. Nishino,\n                      On the complexity of negation\u2010limited Boolean networks\n                      , in Proc. 26th Annual ACM Symposium on the Theory of Computing, ACM, New York, 1994, pp. 38\u201347.","DOI":"10.1145\/195058.195099"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122563"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0215037"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90209-9"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1109\/12.376165"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794275136","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:16Z","timestamp":1787336056000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794275136"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":22,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794275136"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794275136","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}