{"entities":{"Q1109754":{"pageid":1120503,"ns":120,"title":"Item:Q1109754","lastrevid":49211317,"modified":"2026-01-06T18:49:41Z","type":"item","id":"Q1109754","labels":{"en":{"language":"en","value":"Entropy of contact circuits and lower bounds on their complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4070810"}},"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":"Q1109754$8E571BB7-70D0-43FA-8C86-C38A78D67967","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"469e547109690b1cc1a7d5da0551abcff819cce6","datavalue":{"value":{"text":"Entropy of contact circuits and lower bounds on their complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1109754$E78E317C-20E6-44EE-A03F-39D9DAC85A23","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2a3b3bf3a435a0508f7d0e0d29342cf1932b34f5","datavalue":{"value":"0655.94020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109754$81777EBD-7A60-4B7B-A610-911C5F2E60CA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a2e79d2aa037f20eafc80a81886c1c55698dae05","datavalue":{"value":"10.1016/0304-3975(88)90166-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109754$D5D754E6-5443-47B9-A996-F638FA822EAB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b70e9e77e4f1b064cc378d54dc586dac5f1d3270","datavalue":{"value":{"entity-type":"item","numeric-id":1109753,"id":"Q1109753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$6819C59C-8008-485C-8A55-23FA1D74F25E","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":"Q1109754$803B5F19-7D9E-4E87-B086-8D0F0CF52261","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1109754$E4ABB09B-35F6-47C3-B03E-5EC25299D506","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5e29adb296e1ae10d33d383507a9e3087272e081","datavalue":{"value":"A new concept of entropy H(A) of a discrete object A (circuit, Boolean function, etc.) is used to obtain lower bounds on contact circuit complexity of Boolean functions. Intuitively, an entropy must ensure two constraints: (i) \\(size(S)\\geq \\delta^{-1}H(S)\\) for any circuit S and some small \\(\\delta >0\\) (independent of S), i.e. no step of computation makes more than \\(\\delta\\) information; and (ii) if S computes f then H(S)\\(\\geq H(f)\\), i.e. any circuit contains not less information than its function. Then \\(\\delta^{-1}H(f)\\) is the lower bound for L(f), the circuit size complexity of f. In well-known Andreev-Razborov's approach the entropy H(A) is defined as the distance \\(\\rho\\) (A,\\({\\mathfrak A})\\) of A from a special class of objects \\({\\mathfrak A}\\). Then (ii) is trivial, and (i) is the main step of this approach. In the paper under review the entropy \\(H^{\\phi}(A)\\) is defined to be the maximum number of ``unsimilar'' subobjects of A with respect to an appropriate relation of ``similarity'' \\(\\phi\\). Then, for some \\(\\phi\\), (i) becomes trivial with \\(H(S)=H^{\\phi}(S)\\). To prove (ii), special relations \\(\\psi\\) are found such that \\(H^{\\phi}(S)\\geq H^{\\psi}(f)\\). (This is done via an entropy- preserving embedding of circuits into the more restricted ones). Hence, \\(L(f)\\geq \\delta^{-1}H(f)\\). In particular, this new argument allows to prove in a uniform and easy way that contact circuits (as well as branching programs) with bounded number of null-chains require \\(\\exp_ 2(\\Omega (\\sqrt{n}))\\) size to compute some explicitly defined n-argument Boolean functions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109754$8B6F5966-3D00-446A-A45E-FC867F26E180","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109754$CF4019EB-58FE-4CF9-B307-BC67F103479B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109754$49A9863C-CA88-4C33-AE5E-1940B157F721","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e30d62051793251cdb7305d492b252b2239dfb5e","datavalue":{"value":"94A17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109754$51890CB1-2340-41D6-9CA2-DE8CEE045DB4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5c5129234c738fe1cf06f7c236a02b2ff3171cf9","datavalue":{"value":"4070810","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109754$64FDDA95-B586-4D15-8625-45C874ACE505","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c2e069b1a2184cd3b0f52ffa83b5fcb89125e86","datavalue":{"value":"entropy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109754$9C4AE197-3C9D-4AA7-94E1-434682F19FAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcaef8b48097d50a08be2219f6311c65284708bf","datavalue":{"value":"circuit","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109754$24E96E99-A5B9-4B54-AECA-FC17DD2D97FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0062bff246f10874c360cb4d691bf5c2195f236c","datavalue":{"value":"Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109754$593AEF11-5E41-4B76-9908-31DE816D20E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109754$2C42D4A1-E3F5-425D-867F-298F66493108","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddf32c59a20ef404a25c50fc3c4e2d5b5ad42d75","datavalue":{"value":"circuit complexity of Boolean functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109754$14A0620A-940C-452F-96AB-FE5C7134AB5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1923655a1836d134408442da5b53966da7d3ad5e","datavalue":{"value":"contact circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109754$DDEB9088-F14E-4F2A-83D6-95AFA52F49D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec24897927a0742784fae89aed9a922bc2a81fec","datavalue":{"value":"branching programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109754$4EFE8B1B-8811-480D-B292-0D9A5255A792","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":"Q1109754$94996588-CD87-4A90-8FA3-44E58352391F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4d98190f6aabe541bc7e680d4b6e448337c8acef","datavalue":{"value":"https://doi.org/10.1016/0304-3975(88)90166-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1109754$2CC31CBA-0F01-430E-B05D-D8366468AB80","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"63ffed0fe2cb59b73f38ff443c92fa3a7ea44755","datavalue":{"value":"W1991547553","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109754$3547A00E-85ED-4A03-933B-E2274423A757","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2ca04c59b1468ff9eb03a30febcf55d98359908","datavalue":{"value":{"entity-type":"item","numeric-id":1094870,"id":"Q1094870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$83AEF8D1-FE06-4ACF-8FF4-DA21BD7B7058","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce25b6e3a78e9a3f320205259f9976f9eabd886a","datavalue":{"value":{"entity-type":"item","numeric-id":4726174,"id":"Q4726174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$32C0EC80-78EE-439C-ADBD-B1060979FBBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c30026bc0ad7d70772dcc0ef875d17d2ddfd5310","datavalue":{"value":{"entity-type":"item","numeric-id":3718153,"id":"Q3718153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$7E461D23-AB80-45C5-90C1-0AD24CB8CD6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d23d482bb4eeb3cb784fe68510e3d484e171fb1","datavalue":{"value":{"entity-type":"item","numeric-id":1107989,"id":"Q1107989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$D563877E-6CDB-40C3-BD5C-2CA984903CB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f79e196504a8abce7f5d12820a1bf92cd3de6085","datavalue":{"value":{"entity-type":"item","numeric-id":3694708,"id":"Q3694708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$F650B7DD-79AD-4D1F-9AD5-62EE1E536B24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"081e0c9825dbdd8581963c69e8f20370b5610465","datavalue":{"value":{"entity-type":"item","numeric-id":3735698,"id":"Q3735698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$45F83E8C-24C8-4549-8FEC-B254219BAFC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d07c96bc30218ff50ded7a0a5e1dbcfedf272db1","datavalue":{"value":{"entity-type":"item","numeric-id":3751515,"id":"Q3751515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$6CAD97BC-93ED-4213-ACBE-58201722EB60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"514b291bcc18717499c847de12de372fe9e5cca0","datavalue":{"value":{"entity-type":"item","numeric-id":5545524,"id":"Q5545524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$E7D32684-3D34-41B9-BE07-B1FA2345B142","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5f4d447f65bfc71d38aaff97bfbb5c0156be618","datavalue":{"value":{"entity-type":"item","numeric-id":3690219,"id":"Q3690219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$BFFA98A7-457A-40C7-BD33-1D686FCE468F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14e822d0f6871d5df9de9fd97a15be05d850e629","datavalue":{"value":{"entity-type":"item","numeric-id":1071001,"id":"Q1071001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$CBF9BA9D-3589-4CB2-8FB9-0310A3322940","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82f0958994907d9d0238749004a52b6fb840c4b8","datavalue":{"value":{"entity-type":"item","numeric-id":4724549,"id":"Q4724549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$B9B28790-960E-42DE-8908-D101061FCD1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c43b242e8d2a6febe28b4e1a41898561ecb7a1a8","datavalue":{"value":{"entity-type":"item","numeric-id":4138141,"id":"Q4138141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$192006B5-8988-481B-9E56-900A3A8924C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"859cd1e9678e8c4688bdc0a62ce982aa9eecdfeb","datavalue":{"value":{"entity-type":"item","numeric-id":3663188,"id":"Q3663188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$3FEF15AC-0C12-4C40-9C04-4A40F7E03F08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f570b901946254e7e256906c632b0bf64e27f322","datavalue":{"value":{"entity-type":"item","numeric-id":1166489,"id":"Q1166489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$1EC1DD09-8094-4FAE-9AB8-6FB008605F1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b89b6cc4d2fc2f4c2248e49535c640466a6eaaeb","datavalue":{"value":{"entity-type":"item","numeric-id":3757396,"id":"Q3757396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$83AB3F1B-3A67-48B1-AD59-1639254054C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21bc7c146c515de56380f9786cb8389fb225ca92","datavalue":{"value":{"entity-type":"item","numeric-id":3347300,"id":"Q3347300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109754$B8F1D259-BA41-4699-A5B9-7E516FC0A936","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1361cae4ccd4329885fcfeb14267d3e8b3e2af4","datavalue":{"value":{"entity-type":"item","numeric-id":3751515,"id":"Q3751515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cb7bdf91da09b00560f78fd99bac9c03f216d89","datavalue":{"value":{"amount":"+0.9028084874153136","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":"Q1109754$77B4A5B7-C90B-445A-A9A9-BAB3994D5100","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8260d02ce0d4d6c7f30cee2ab4a39643f1ec565","datavalue":{"value":{"entity-type":"item","numeric-id":3033329,"id":"Q3033329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc8e2b1f1817b568dbd28a0cd70818d5b9cac899","datavalue":{"value":{"amount":"+0.863771378993988","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":"Q1109754$E9D68A1D-0EF5-49F5-8D9A-D07F2CA58F47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ed83a47ecc665f63730666912f17a8dfc0221fc","datavalue":{"value":{"entity-type":"item","numeric-id":3801064,"id":"Q3801064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da49ebdfc5e24303f1228d526c064b7506ef4631","datavalue":{"value":{"amount":"+0.8151544332504272","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":"Q1109754$0C8BAC83-3C36-47EC-9149-4D2B0DDE7571","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44aa507f5b3578617a20b0be6c6ab2e2daf814dc","datavalue":{"value":{"entity-type":"item","numeric-id":5753894,"id":"Q5753894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cff7958ef0fde6a773a14e6f7b951da7b1f47f4e","datavalue":{"value":{"amount":"+0.7940016984939575","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":"Q1109754$A946AADA-0FF7-417D-A292-A8C0FAB46E61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"694dbcd29efdbfbc930700c6b96b39afc631f559","datavalue":{"value":{"entity-type":"item","numeric-id":4503366,"id":"Q4503366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b39e994cc5874365dd1e69fefdb25ab5449bce3","datavalue":{"value":{"amount":"+0.7904031872749329","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":"Q1109754$22A34D4C-AEFB-4303-AA13-B0D753B60E07","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1109754","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1109754"}}}}}