{"entities":{"Q1088970":{"pageid":1099722,"ns":120,"title":"Item:Q1088970","lastrevid":66911931,"modified":"2026-04-12T13:41:28Z","type":"item","id":"Q1088970","labels":{"en":{"language":"en","value":"Threshold functions and bounded depth monotone circuits"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4002033"}},"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":"Q1088970$F3AA32F2-1CBE-453A-90D4-949F0CAA311E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eac1932c041249253ea3b12ada6f5e383882432c","datavalue":{"value":{"text":"Threshold functions and bounded depth monotone circuits","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1088970$E700F13A-1AB1-4AAC-A983-11F06D371912","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a6a18fd24fa5546110e4278d8d06dfdfa4a9a83a","datavalue":{"value":"0617.94012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088970$A31A5C67-2B23-4A8B-AA56-75599DC9CD26","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"21a4b3d2f1c45551da73a0e98b5c8e3992011193","datavalue":{"value":"10.1016/0022-0000(86)90027-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088970$080559FB-FFF5-4256-85DB-298DB91FD1DB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5bf5a07a70c009b9407b5ef2db9026ca798e998f","datavalue":{"value":{"entity-type":"item","numeric-id":290254,"id":"Q290254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088970$3BB3120F-CEFC-496F-B5AB-0CD14D185AEB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088970$180B2AE2-53F4-4AA6-83B7-98F3F16A15E9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1088970$41ADEBAB-34FF-4580-AAEF-74FC6FF1E947","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a9585b1d7065c37f05a65f5b5d8ad25a5f0404fa","datavalue":{"value":"It is shown that the n-variable majority function can be implemented on a d-level monotone circuit (with alternating levels of AND gates and OR gates, and no negated variables as inputs) requiring EXP(\\(\\Omega\\) \\(n^{1/(d-1)})\\) gates, where \\(\\Omega\\) depends on the circuit depth d. This lower bound for the size of the monotone circuit implementing the majority function establishes a size-depth trade-off and implies exponential lower bounds for many graph problems such as testing connectivity and detecting cliques and Hamiltonian cycles.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088970$1F075B0D-78F5-4025-80CE-0255101E529D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088970$C0384896-6123-4C94-A4B9-A9BB8CDCA27E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088970$F40EA9C5-D9AA-47EB-9075-614CAA92066A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088970$D85E5B77-F447-4271-9C23-BF926AC758A0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"767291aef2cd1abea2d2f7ecde7242e1feefded8","datavalue":{"value":"4002033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088970$98BE2461-96C1-47AE-AD9E-C57BA5147FE0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5af1cbc22fefde0b6643f68f8e3c87eff73b8cac","datavalue":{"value":"lower bounds for graph problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088970$81398F35-8FF9-4F80-87F9-90D4FCED2D87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99af6ddbd8a52d77fd46256a869635f8d32fadf5","datavalue":{"value":"majority function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088970$F1FABA20-DA40-4D33-8AA3-299AFCFA16E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39f150a72303d4ae2ad42695b88c39a171c6669e","datavalue":{"value":"monotone circuit","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088970$EA443022-8737-4BFE-A131-D5C0D6FFAA62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"907953b75cd389130f909b45e354ba5d97a9d3b9","datavalue":{"value":"lower bound for the size","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088970$886D8685-2B81-4FDA-8A67-2D2CB1B870D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e83926d96095d603ea00be139d772bffd2cf811e","datavalue":{"value":"size-depth trade-off","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088970$EE38838E-25F0-407F-B56D-5C6D58231B9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088970$3455660D-76DE-44E8-AA02-AD5DC3F9FCCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a153084f07a75cc56b26c617236589c3c4eb947","datavalue":{"value":"cliques","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088970$BA605CB4-0BF4-4909-9619-DF54FC072E64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"862b3f9bd3562fb19afcb46cb40fc8fc3f64ed24","datavalue":{"value":"Hamiltonian cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1088970$4D13C32A-3EB4-42F2-8877-222A23CEA08B","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":"Q1088970$CFF8E6D8-5893-4637-AACC-3FB6A2BBFA0C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5821261951795f34bec1e92801279661bf1300e4","datavalue":{"value":"https://doi.org/10.1016/0022-0000(86)90027-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1088970$8EA478E1-1E71-455C-93C5-A895254F60D6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7b35b103ea6c4143e6a3d616ddc3b812c36e559d","datavalue":{"value":"W2062196111","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1088970$11AC12F9-B5E2-429F-B089-E0ECA3014D6C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"957892286a77298fd7faca30f1f60dbb53f94696","datavalue":{"value":{"entity-type":"item","numeric-id":1054720,"id":"Q1054720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088970$A3870083-614A-47BC-8ACE-0411EA9CB19B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8e73c4b1eb952ce21189627f2e0b84dd36494db","datavalue":{"value":{"entity-type":"item","numeric-id":3771612,"id":"Q3771612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088970$0C750C15-9D91-4024-B86A-A938A8D6EC05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b8ab76ca2a98c2ec7fbf989d43fdf31a692debb","datavalue":{"value":{"entity-type":"item","numeric-id":3218066,"id":"Q3218066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1088970$3D9DEAF1-B9DA-4106-B29B-7D13233DEAD4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d14150a40d56272f516b5824af2ec39ae648f867","datavalue":{"value":{"entity-type":"item","numeric-id":1094870,"id":"Q1094870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e187eb36d0c2673d9976466a4e20095b7ba0a2f0","datavalue":{"value":{"amount":"+0.8497998714447021","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":"Q1088970$F3F636B5-338A-47AF-917C-E8EB1495A7AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"083eb078940518f9c5dbe49572ee5e1295d6690a","datavalue":{"value":{"entity-type":"item","numeric-id":1122560,"id":"Q1122560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33ec60af59ec984a743847b71ec1f01587b22e00","datavalue":{"value":{"amount":"+0.847599983215332","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":"Q1088970$DE1BD6EC-8895-45A5-AAF0-8B7323457517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"700e5880c9aa72afd454fcfda175ae29331ebd95","datavalue":{"value":{"entity-type":"item","numeric-id":3595404,"id":"Q3595404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cd6c93c58a37b390037b8db98a08081ef83e659","datavalue":{"value":{"amount":"+0.8467826843261719","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":"Q1088970$C251C1D8-3611-4284-84B9-AA450493259F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99357944111500338246e46af3ecadede747626e","datavalue":{"value":{"entity-type":"item","numeric-id":4978062,"id":"Q4978062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bef44fa86961c00027e530b6464df31ada3154e9","datavalue":{"value":{"amount":"+0.8443979620933533","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":"Q1088970$1121D44F-930C-4A26-AF05-1772009EEE69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac452768a72546b43f7550d5e2fe55ccf7eda9e0","datavalue":{"value":{"entity-type":"item","numeric-id":3684036,"id":"Q3684036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb728987a082a8b3bab1f89afaf44e21d3d539a1","datavalue":{"value":{"amount":"+0.8378023505210876","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":"Q1088970$62BDDE74-A5B8-4C05-92A9-910DAEE0CEEB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Threshold functions and bounded depth monotone circuits","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Threshold_functions_and_bounded_depth_monotone_circuits"}}}}}