{"entities":{"Q804295":{"pageid":806143,"ns":120,"title":"Item:Q804295","lastrevid":64504632,"modified":"2026-04-11T20:19:58Z","type":"item","id":"Q804295","labels":{"en":{"language":"en","value":"Size-depth trade-offs for monotone arithmetic circuits"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4201624"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804295$7B3CA062-1CCB-4DEE-BE41-4F79161AE538","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9b97d15c1413724c9d59111a4c5c268287327aee","datavalue":{"value":{"text":"Size-depth trade-offs for monotone arithmetic circuits","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q804295$B27A2A89-E305-4CCB-9A2D-102D642F90E7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ded21bdd141be36633a05ae833b6bf0174a1a72a","datavalue":{"value":"0727.68049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804295$FA4B33C2-AC56-478E-ABE5-3AE3A239319A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f3b0c4e2a0bd428bb781720d3fa3d2c695f1f6bc","datavalue":{"value":"10.1016/0304-3975(91)90173-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804295$111FE492-30AF-4786-B8B0-F1B7963D8085","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"74fd6b3a8df291eb0ef14a7442cbd4d786a23aca","datavalue":{"value":{"entity-type":"item","numeric-id":804294,"id":"Q804294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804295$2E4990B2-448A-4CA4-8943-9F0656353E64","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804295$76B7B88F-4853-401F-B10F-3AE116C190C4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q804295$A172D211-74C4-4022-AB90-5566AFDF0069","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e3e76879e1b6b74d8306ad9161eba69175e5ed18","datavalue":{"value":"The paper deals with the size-depth trade-off for monotone arithmetic circuits computing the \\(product!a^ TA_ 1...A_ t\\cdot b\\) where \\(A_ 1,...,A_ t\\) are \\(n\\times n\\) matrics, a and b are vectors. It is proved that if a monotone circuit computes this product in d parallel multiplication steps and with s multiplications, then \\(s+2d(n^ 3-n^ 2)\\geq (t+2)n^ 3-2n^ 2+n\\). This inequality is tight; a matching upper bound can be achieved for any d in the range \\(1+\\log t\\leq d\\leq t/2+1\\). In this range, any decrease of one in d requires an increase of \\(2(n^ 3- n^ 2)\\) in s. It seems extremely hard to obtain similar trade-off for general circuits, i.e. for circuits with the subtraction.","type":"string"},"datatype":"string"},"type":"statement","id":"Q804295$789E0D33-EFEA-43ED-ACBA-854400623A0F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804295$E3F0ACDE-FA73-4427-BB5C-788F67BEBC6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804295$3B113D0D-4549-4AFF-A33C-698C34BD6871","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f81fb039aa781a69305fe928c4c03493e709d7d6","datavalue":{"value":"4201624","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q804295$8B725B85-3F6B-432C-99A0-4E5563188564","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q804295$D500B39F-9E20-4A22-9BC2-7922B6499064","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e83926d96095d603ea00be139d772bffd2cf811e","datavalue":{"value":"size-depth trade-off","type":"string"},"datatype":"string"},"type":"statement","id":"Q804295$FF568D0B-6B67-4325-991D-85ABEF6154ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95537810381bd01fb1070c58b99d1adf9f8d4c48","datavalue":{"value":"monotone arithmetic circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q804295$015D0F9C-6A24-45A7-B947-854023784F2B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1833d190eb6492ca84e0c93a6ff12de5694705d3","datavalue":{"value":{"entity-type":"item","numeric-id":1109753,"id":"Q1109753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804295$5701704D-D049-4C5E-9589-BEDFD666CF1A","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804295$FF1BA36D-BC5D-4C20-B11A-3B4DC28B7F7F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4077de5ad21c6b78a25ec43c56119974484a370","datavalue":{"value":{"entity-type":"item","numeric-id":4401551,"id":"Q4401551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804295$9F372DF6-74F4-4324-AFDF-F97147A83FB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57f812d926f954026c0ce9b093b267b76b40c2cc","datavalue":{"value":{"entity-type":"item","numeric-id":4065034,"id":"Q4065034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804295$6A1C4E7C-CBD3-44D8-BE73-A24C211DFFE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0c6ec7b7473c14d4833d446cd1c80a59d257532","datavalue":{"value":{"entity-type":"item","numeric-id":4133124,"id":"Q4133124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804295$875D2AAB-2050-46E4-92E4-4175E1B269A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"419a21e35746849ad02e24d14bdf207f47768bb5","datavalue":{"value":{"entity-type":"item","numeric-id":4131022,"id":"Q4131022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804295$B424D2CF-E034-4812-B1F4-B6D6EBF378FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04f53a44e60807517a77c3256c6fa193f666dfdb","datavalue":{"value":{"entity-type":"item","numeric-id":3945585,"id":"Q3945585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804295$E037E59D-1340-4438-AE33-9E7E38294D93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ce5b988c7c59061ff4454e580ebfbb56afb00e3","datavalue":{"value":{"entity-type":"item","numeric-id":3796739,"id":"Q3796739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804295$00B846AB-8494-4638-BA56-9E57AEC72F7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2ef3d2a04725300c27226a57d9edc343b950cbd","datavalue":{"value":{"entity-type":"item","numeric-id":3799628,"id":"Q3799628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804295$A270BA68-E2CD-4EDE-8F94-B29D1DDB6B48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a70465901ebce1c7dcd22c21746c8de714cc7b2d","datavalue":{"value":{"entity-type":"item","numeric-id":3745780,"id":"Q3745780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804295$9C16579C-D5A3-4BD3-9E5A-99FB40F42598","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da1e2a210a633c08ab99ee4d2a519f4798177e87","datavalue":{"value":{"entity-type":"item","numeric-id":3036703,"id":"Q3036703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q804295$024DDE3D-93C5-4CCB-8BB0-C112840F330D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"617fc72693574461bda6f5405aba39439263fbc1","datavalue":{"value":{"entity-type":"item","numeric-id":1070999,"id":"Q1070999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc15aa554d6a62e6dfda73e9183ef8afc49228d5","datavalue":{"value":{"amount":"+0.8261105418205261","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q804295$93FA9576-178F-4407-A068-A979C1F75EB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5267f5d897eac7ae79295f7a742d2868779e70a","datavalue":{"value":{"entity-type":"item","numeric-id":4429689,"id":"Q4429689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"913e2ac556243d6200112f0590208cd9f6453b63","datavalue":{"value":{"amount":"+0.8188482522964478","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q804295$0EDB36A6-9145-4F5A-BAAE-DCFEC444E6F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e800bb46edb538a27c4325ce91fe7b84f0d497d","datavalue":{"value":{"entity-type":"item","numeric-id":5175996,"id":"Q5175996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"913e2ac556243d6200112f0590208cd9f6453b63","datavalue":{"value":{"amount":"+0.8188482522964478","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q804295$17625722-6106-47FF-B2E6-EAC834409B90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e71e7148204d2a7999362bf6d4bccadfe805b806","datavalue":{"value":{"entity-type":"item","numeric-id":1318755,"id":"Q1318755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b8064cd3990bd83db4c628a7424370bf3ef3894","datavalue":{"value":{"amount":"+0.7987843751907349","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q804295$4AC85D1D-E1DE-4660-B347-77A7DA128DE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70a788c1ea44fb70d172c826d6d334b66e81e264","datavalue":{"value":{"entity-type":"item","numeric-id":313809,"id":"Q313809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b8064cd3990bd83db4c628a7424370bf3ef3894","datavalue":{"value":{"amount":"+0.7987843751907349","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q804295$4972FCBF-DA4D-4049-9244-DE13D205AF0E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Size-depth trade-offs for monotone arithmetic circuits","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Size-depth_trade-offs_for_monotone_arithmetic_circuits"}}}}}