{"entities":{"Q1180407":{"pageid":1191156,"ns":120,"title":"Item:Q1180407","lastrevid":42301775,"modified":"2025-06-04T14:47:59Z","type":"item","id":"Q1180407","labels":{"en":{"language":"en","value":"An \\(\\Omega{} (n^{5/4})\\) lower bound on the randomized complexity of graph properties"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 25757"}},"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":"Q1180407$E098687C-D08B-42F2-B3E9-401AB055F84F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1fee14cab510b29571aebe6dbb247ab8dd91e7a6","datavalue":{"value":{"text":"An \\(\\Omega{} (n^{5/4})\\) lower bound on the randomized complexity of graph properties","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1180407$AA169661-39DF-4D9F-AE80-37694DDDD1BE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"38ffec51fac74ebda4a824d451826fc52c478168","datavalue":{"value":"0743.68077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180407$D81E2797-7576-4EF0-9E17-75F0DDE3D148","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6afe0fb91a0e5ae54efd085dbf8132061b1179a6","datavalue":{"value":"10.1007/BF01375470","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180407$6F107253-AECD-4C2C-8498-DE61F0A63841","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a0a57cd83a690b4e7a99576fe9a7af57a0de1c1","datavalue":{"value":{"entity-type":"item","numeric-id":290235,"id":"Q290235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180407$AE20B8CC-E081-48F5-945F-341CF6196749","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180407$EAB7C366-DAC1-4B4E-9640-A3DA8E55E73E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70844ffc4666eabac4e20376c648613dbe8620f7","datavalue":{"value":{"time":"+1992-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1180407$3C5AA7D5-0FD8-49AB-9A48-C3117E9B7FF9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2560989f40ab38794d56d20faf1a6b8c6864e3f8","datavalue":{"value":"Let \\({\\mathcal G}_ n\\) be the set of labeled graphs on the vertex set \\(V=\\{1,2,\\dots,n\\}\\). A graph property \\(P\\) is a subset of \\({\\mathcal G}_ n\\) closed under isomorphism. A graph property \\(P\\) is monotone (increasing) if \\(H\\subset G\\) and \\(H\\in P\\) imply that \\(G\\in P\\). A graph property \\(P\\) is nontrivial if \\(P\\neq \\phi\\) and \\(P\\neq {\\mathcal G}_ n\\).   A decision tree algorithm \\(A\\) computes a graph property \\(P\\) for any input \\(G\\) by asking questions of the form ``Is the edge \\((i,j)\\) in \\(G\\)?'' The choice of questions depends only on the information gained so far. Let \\({\\mathcal A}_ P\\) be the set of all decision tree algorithms for \\(P\\). Let \\(\\hbox{cost}(A,G)\\) be the number of queries asked by \\(A\\) when \\(G\\) is the input.   The randomized decision tree algorithm is a probability distribution \\(\\alpha\\) over \\({\\mathcal A}_ P\\). The expected number of queries asked by \\(\\alpha\\) for input \\(G\\) is,  \\[ \\hbox{cost}^ R(\\alpha,G)=\\sum_{A\\in{\\mathcal A}_ P}\\alpha(A)\\hbox{cost}(A,G). \\]  (Here we adopt the notation of \\textit{P. Hajnal}: An \\(\\Omega(n^{4/3})\\) lower bound on the randomized complexity of graph properties (see the review above). The randomized decision tree complexity \\(R(P)\\) of \\(P\\) is, by definition,  \\[ \\min_{\\alpha}\\max_{G\\in{\\mathcal G}_ n}\\hbox{cost}^ R(\\alpha,G). \\]  It is proved that \\(\\Omega(n^{5/4})\\) is a lower bound for the randomized decision tree complexity of any nontrivial monotone graph property \\(P\\). This result improves an earlier result obtained by \\textit{A. Yao} in 1987. At the end of this paper the author remarks that \\textit{P. Hajnal} has further reduced the lower bound for \\(R(P)\\) to \\(\\Omega(n^{4/3})\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180407$7ABE0E57-57BA-466D-843D-67882AD96CB0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0dfbdb0929ddc22bcd5bd1c182b95d3875d4d630","datavalue":{"value":{"entity-type":"item","numeric-id":1164054,"id":"Q1164054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180407$640203FC-AB5B-4E08-815F-925DB78DAA91","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180407$81B306AF-8546-4ECC-82F6-AD26739EE78B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180407$2743275B-CD34-4C1A-B97C-ECF841211687","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180407$A5F3DB9F-0F66-442E-9035-BF1607A48D1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180407$268994BB-D5A6-456D-897B-30D975274203","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"68508f056b8cdeada479a4ba072fc9b790bd07cb","datavalue":{"value":"25757","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180407$2C45A9AA-4234-4AB4-859D-35470E9751EC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0506c4d8e8a7c5739e313ad56b251064235747b3","datavalue":{"value":"complexity of graph properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180407$F3C5B938-644E-45A3-919C-B63C8B61B2AD","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":"Q1180407$93EB0FA3-124A-4048-B416-0A3D2AFFE5DB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c28903e6085f325f83f6c2f8674c9e4abb77407","datavalue":{"value":{"entity-type":"item","numeric-id":1065831,"id":"Q1065831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180407$6B60F4FE-B6C5-431D-B625-79B2AE8A737C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7be7ec776afc6ad8ad178675a434e62027116713","datavalue":{"value":{"entity-type":"item","numeric-id":1238421,"id":"Q1238421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180407$80285653-C3DC-458F-9E66-F8EE7A4A3DD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb6635157d46ee699421ac79239513d8a4715c8c","datavalue":{"value":{"entity-type":"item","numeric-id":754889,"id":"Q754889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180407$80B8E457-D767-4B55-A1C8-021D34DC900D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"981fb1dfba9b687ce8a681c968494af465263b0c","datavalue":{"value":{"entity-type":"item","numeric-id":5826301,"id":"Q5826301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180407$BD0EAC67-4573-4F13-8E21-21BD9C2B2682","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a51b3eb76b2a026b9e159123580e163f67a114a2","datavalue":{"value":{"entity-type":"item","numeric-id":1180414,"id":"Q1180414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2a1f102fb4ea74b777a2dfceafbb7a94b3b420f","datavalue":{"value":{"amount":"+0.965333","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180407$9ADCE410-69B9-4A99-82D9-4654A6FB7A4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bdf914576a80621e0ffd8e9606941c200a1cfe19","datavalue":{"value":{"entity-type":"item","numeric-id":808708,"id":"Q808708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af1384a5af817a008ac4d25af7fc57e46d2527ea","datavalue":{"value":{"amount":"+0.9300901","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180407$69D3207C-0521-489F-98CB-FB9B3768B93B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bddb409e089fc29803fa8d21a6fe66be9ce95a9","datavalue":{"value":{"entity-type":"item","numeric-id":4535024,"id":"Q4535024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"449e8dc54f3af097187f88b2ccecb8525711735b","datavalue":{"value":{"amount":"+0.920673","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180407$57DC4FB2-53FC-40B1-94E4-4B28096A2E20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84eba3ed70d5bc0a633eb8f01050a7cd734bbe6c","datavalue":{"value":{"entity-type":"item","numeric-id":3437025,"id":"Q3437025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"449e8dc54f3af097187f88b2ccecb8525711735b","datavalue":{"value":{"amount":"+0.920673","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180407$FC5B012C-E9A7-4F5E-86CA-51E10AD3BA7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a6df118282f91cc29ba8355f38ee940839bd4e4","datavalue":{"value":{"entity-type":"item","numeric-id":4036171,"id":"Q4036171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36e0923815e6c1b8f58f2dac44bbff97334cae1e","datavalue":{"value":{"amount":"+0.88184685","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180407$FF5AA7DE-E2E7-4C2A-9279-AC02754365CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc7bd9fec132f3c2db8882fb469029638aad1e1e","datavalue":{"value":{"entity-type":"item","numeric-id":1010905,"id":"Q1010905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f53b62258b99cbebe87943afaa3f67710f624e6","datavalue":{"value":{"amount":"+0.86592174","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180407$B150E23F-4A50-446B-B276-793719AA2E18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"452006fb27b19c9cb59c6708b212a54d1c8944b5","datavalue":{"value":{"entity-type":"item","numeric-id":5300493,"id":"Q5300493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72486f2179cb5b5e76739e61b558ea85d4ec6df0","datavalue":{"value":{"amount":"+0.8653352","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180407$BF47E919-9964-44BC-B5CC-21FCF80C4797","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf66596a3de637d425dcebfa060509869c7142ac","datavalue":{"value":{"entity-type":"item","numeric-id":4542540,"id":"Q4542540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3566f58ceb28b89c103cd3386525388efe6c8cc8","datavalue":{"value":{"amount":"+0.86271656","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180407$9E7723B2-621F-425A-AC13-1B4B31BC18E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7643027ac245a0e31431571fc7df9646fb69c4d7","datavalue":{"value":{"entity-type":"item","numeric-id":653841,"id":"Q653841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67f9879b926a6687890fceba3dcf4e5aec88850d","datavalue":{"value":{"amount":"+0.8617897","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180407$4D59C411-EF8E-4175-B7BD-6CEAB88B4D41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5b81d8aebcacd275ebdbd98d8c1d7a1d9e00359","datavalue":{"value":{"entity-type":"item","numeric-id":1358054,"id":"Q1358054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f4390a66c9d6cd73277209777bdc1e9b65ee7de","datavalue":{"value":{"amount":"+0.85867083","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180407$8A0EBD7B-F746-49A5-AAE4-9E0315682A03","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1180407","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1180407"}}}}}