{"entities":{"Q452855":{"pageid":454622,"ns":120,"title":"Item:Q452855","lastrevid":51555656,"modified":"2026-01-18T18:42:04Z","type":"item","id":"Q452855","labels":{"en":{"language":"en","value":"Monotonicity testing and shortest-path routing on the cube"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6083374"}},"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":"Q452855$CB5341F2-E143-428C-B5CF-908A68E9ACF3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cd844291e7e030e6ec54c33c5088527b156e6cf9","datavalue":{"value":{"text":"Monotonicity testing and shortest-path routing on the cube","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q452855$6AF9B2E5-8EA2-43CD-92A7-B785D05080E0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7c23440609cab0948995d6b94f3767bd50685961","datavalue":{"value":"1265.68079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452855$4ABE98F8-722C-4965-B406-2F25A76C2BD2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"76ab291516bc896e52c51bff48b3d06f03fb53b3","datavalue":{"value":{"entity-type":"item","numeric-id":356690,"id":"Q356690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$CFF52318-3E39-4CF4-BDA4-EA19A5523E23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d164d3ccb0148e85d3b7692b8e99bedbd1d5ab02","datavalue":{"value":{"entity-type":"item","numeric-id":269726,"id":"Q269726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$8C026A13-435C-4758-B713-1F4F90C31F8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"df6937dd9735e0bcc0e9f666bf511c19710ef4bf","datavalue":{"value":{"entity-type":"item","numeric-id":452853,"id":"Q452853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$C92673B7-3A49-4B80-A3C8-AA8F13E2840F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"620163ecf8792b9063bead5c6c1cf247f60b97ea","datavalue":{"value":{"entity-type":"item","numeric-id":452854,"id":"Q452854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$2B069F9D-76C2-42C4-988C-D7995A072E4C","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":"Q452855$BB2F1D42-DD3F-4F38-ACDE-3E9AA34DFEA6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8116af7574c2cac3c55da1a071af8f6c18a63659","datavalue":{"value":{"time":"+2012-09-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q452855$DC16A44E-FBAB-4853-94B0-FCD7E5696AAE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"efa7677f6804dd1a6c9f423eddc2f5da44f135e5","datavalue":{"value":"This paper studies the complexity issue related to the problem of testing function monotonicity. In particular, the authors obtain tighter bounds for the associated complexities. Call a function \\(f: {\\{0, 1\\}}^n \\rightarrow {\\mathcal R}\\) disk-\\(k\\) monotone if \\(f(y)>f(x)\\) for every \\(y>x,\\) where \\(| y| >| x| +k\\). (Thus, ``disk-\\(0\\) monotone'' means ``monotone''.) The authors show in the Theorem\\,4 that a disk-3 monotone function \\(f\\) can be tested for monotonicity with \\(O(n^{3/2}/\\epsilon)\\) queries, where \\(\\epsilon>0.\\) It is claimed that this bound is tighter than the best bound known prior to the publication of this paper, which depends on \\({\\mathcal R}\\). The authors also further strengthen the lower bound of this problem from \\(\\Omega(\\sqrt{n}/\\epsilon)\\) to \\(\\Omega(n/\\epsilon)\\) when \\(| {\\mathcal R}| >2\\sqrt{n}.\\)  It is worth pointing out that the above upper bound was obtained by constructing a collection of source/target pairs in the \\(n\\)-dimension hypercube, commonly denoted as \\(Q_n,\\) such that no more than a \\(1/\\sqrt{n}\\) fraction of these pairs can be simultaneously connected with edge-disjoint paths. Indeed, most of the results found in this paper are derived based on a known connection between this monotonicity testing problem and some routing problems associated with \\(Q_n:\\) if at least a \\(\\mu(n)\\) fraction of any set of distinct source/target pairs on the directed version of \\(Q_n\\) can be connected with edge-disjoint paths, then the monotonicity of functions \\(f: {\\{0,1\\}}^n \\rightarrow \\mathcal{R}\\) can be tested with \\(O(n/(\\epsilon \\mu(n)))\\) queries for any totally ordered range \\(\\mathcal{R}.\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q452855$080C7004-4B40-4210-96F6-D830D38761E4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7abfc75f139cda8f4c0237cc0cc535fa3298616e","datavalue":{"value":{"entity-type":"item","numeric-id":300260,"id":"Q300260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$19A38538-2985-4873-8DD3-48C5A094BD21","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452855$3B3C5770-E2D4-40F7-BD9B-C4E1C6C1E1D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452855$EB2D385F-DF2B-474A-8DBB-04CE72FB96DB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8b93eeddae5351063ae1ebb3d040bbf2134f4642","datavalue":{"value":"6083374","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452855$E4C7C44B-5EE9-4F11-B7D9-3AFF508C03A6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ef9b23d905b32aabf11e9437fc148cdd5fa9420","datavalue":{"value":"testing function monotonicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q452855$83AAE9C2-F3EA-48FA-BBD6-FEE6191EB5F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ff80eac249d04deb3017e72ab29bd1d9d12a7e9","datavalue":{"value":"disk-\\(k\\)-monotone function","type":"string"},"datatype":"string"},"type":"statement","id":"Q452855$0D964F86-AB32-48EE-AD70-1C1AA7B7503D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d89aa712bc8d77542163f6e123cca726cd5b4837","datavalue":{"value":"lower and upper bounds for complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q452855$B412D8ED-9C91-409A-8E06-7EDD106E7DAF","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":"Q452855$5F94EEBE-824B-4AA8-B9DA-9E6DCB544894","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bb2c51517f15f871cf3293cac4454c4e5f826538","datavalue":{"value":"https://doi.org/10.1007/s00493-012-2765-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q452855$344024D0-7AFA-4CD8-BD82-82099863796D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d43a35277f71ab743c1b271f0243358c35f2c76b","datavalue":{"value":"W2400386569","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452855$03D8FD43-8CDD-4CB1-A3C2-3636A5583549","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5037c745bd661a6db873b5672ccead9ca5761f79","datavalue":{"value":{"entity-type":"item","numeric-id":5901124,"id":"Q5901124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$5C828C5B-C86E-429B-A3D9-C2FB8DEAECC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75271e2ab590b8b3960c4f3afb381e6ea552db39","datavalue":{"value":{"entity-type":"item","numeric-id":859828,"id":"Q859828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$208BE6CC-9921-43CD-84BD-1C74961330C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08b9b58e9a088e5bb4904fc706a9c3de57ae0b84","datavalue":{"value":{"entity-type":"item","numeric-id":4910569,"id":"Q4910569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$8472E1B0-CB70-4D7A-9722-856CB4E4EDFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b080421c1bb60d94d438a0ef37f8d5bbf3c3e910","datavalue":{"value":{"entity-type":"item","numeric-id":4941829,"id":"Q4941829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$47D6DB0D-03BF-49B1-8F05-3ADB3B848058","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ab61ce3d863a44242c09ccd335a8a05f0ff7118","datavalue":{"value":{"entity-type":"item","numeric-id":1577018,"id":"Q1577018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$10978D6C-312E-4CD8-AC82-357864359C59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4a8816ad2bb0d820d7b9a0fd415db11398acfbe","datavalue":{"value":{"entity-type":"item","numeric-id":693004,"id":"Q693004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$B77D836F-A83B-4A0A-A533-54696F1098BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1be02df6f073acf00477fa67b038335e871ff4b1","datavalue":{"value":{"entity-type":"item","numeric-id":1887149,"id":"Q1887149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$6D199B02-1EE4-4D00-93BB-2976157F556A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34fa6b03a44f660dbc795fe59e562dddcb13a611","datavalue":{"value":{"entity-type":"item","numeric-id":3579209,"id":"Q3579209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$11F4DE54-F28D-47B2-80A3-8690DEE28BE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4dd8e6b39a9c57a40d5ec7b3e1872397957b3b2","datavalue":{"value":{"entity-type":"item","numeric-id":5932642,"id":"Q5932642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$AD111CB9-0136-4192-B525-EF5D6712D90E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc9a77303b11ec4f4a410126e11714179dc1348c","datavalue":{"value":{"entity-type":"item","numeric-id":3522829,"id":"Q3522829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$03AB2DF0-F25C-489B-B673-0C472B82A84C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4f1d45377bb286a05b1aec82e35cf2713f01a67","datavalue":{"value":{"entity-type":"item","numeric-id":5937251,"id":"Q5937251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$65C6BC41-69B4-4120-B42D-B094B7B3402B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f258e9ca5edd81da0a8fb8448d0219bca52f218","datavalue":{"value":{"entity-type":"item","numeric-id":911780,"id":"Q911780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$153FC975-F6C8-4A99-A37B-D31414B6D6FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"041021aaa39a346751f3fd11b845ca072e26bdb5","datavalue":{"value":{"entity-type":"item","numeric-id":2921706,"id":"Q2921706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q452855$BA97E409-3B8A-4995-A2C6-7F2AC5AABB3A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aedd619ec34a2611e9bfb37d3c7901d4a0245bd8","datavalue":{"value":"10.1007/S00493-012-2765-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q452855$60D937B6-6E0D-4E27-8883-B9E26CC024BB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6a7e36ae2d0440ac9f0fe73083917658a552e0c","datavalue":{"value":{"entity-type":"item","numeric-id":3588427,"id":"Q3588427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01734b6ce989298dbebd2a75471dadd6f6ff56f1","datavalue":{"value":{"amount":"+0.9081919193267822","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":"Q452855$49E772DF-28EE-461A-B29D-95AA0E07F050","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26c34fb65e9aa101c8178d4d41b73c4c24825c2c","datavalue":{"value":{"entity-type":"item","numeric-id":4941829,"id":"Q4941829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f635d75888600a069341ff482cf6c739ec5eae8","datavalue":{"value":{"amount":"+0.8065144419670105","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":"Q452855$4FB17E22-749C-48C7-A31F-398EF6D03071","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64f71bd69c52867a5ce4003629e9a8bff865fca6","datavalue":{"value":{"entity-type":"item","numeric-id":5009526,"id":"Q5009526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e8984a330bed9f06191cfd885dd046e28af7c80","datavalue":{"value":{"amount":"+0.8065141439437866","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":"Q452855$0672F51B-06EA-47D4-9976-1E179A3182F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"200e671375108bd49c7435129e98e3faa2a6c41a","datavalue":{"value":{"entity-type":"item","numeric-id":2851875,"id":"Q2851875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dbdce5a27c315d577ab29cb7712085e52b95e31f","datavalue":{"value":{"amount":"+0.7941616773605347","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":"Q452855$76600B86-CF73-4C06-BCF3-D5935177354D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"489dde72d9d239fffc3c7ecb9aab87567707210d","datavalue":{"value":{"entity-type":"item","numeric-id":5497118,"id":"Q5497118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c2428add83adbab97b7b18909594d2a35787e03","datavalue":{"value":{"amount":"+0.7913004755973816","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":"Q452855$70B6F706-9478-4C09-9A3A-C3FBC29B0665","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:452855","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:452855"}}}}}