{"entities":{"Q1260656":{"pageid":1271406,"ns":120,"title":"Item:Q1260656","lastrevid":67385376,"modified":"2026-04-12T17:16:16Z","type":"item","id":"Q1260656","labels":{"en":{"language":"en","value":"On randomized semi-algebraic test complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 370452"}},"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":"Q1260656$B4CB17A5-398B-4B6C-91DC-8C116945DEB4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c6f71ea19ba43007776765ccec9a2356f302f411","datavalue":{"value":{"text":"On randomized semi-algebraic test complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1260656$5DE02203-2A44-460F-BF8C-348AC5D48365","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9e5c3fb93b8d372eeed26d3e352f18398f3aba87","datavalue":{"value":"0806.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260656$5E24D8AA-94AD-4F7E-B522-0B849D6566B3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e924ed081f4605dc26607b8aca3d4232bbd94111","datavalue":{"value":{"entity-type":"item","numeric-id":254894,"id":"Q254894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260656$FEE4432D-538E-4D23-B503-4E3648B66B1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"572a13162b6df712d7941005f95a34b361dad87b","datavalue":{"value":{"entity-type":"item","numeric-id":396628,"id":"Q396628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260656$23F82DA7-A7E5-42E4-AF50-E26888ECFC5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2f331c21509cfe7fc36b0dc5b7088115dc31b95d","datavalue":{"value":{"entity-type":"item","numeric-id":171408,"id":"Q171408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260656$B3C02EFF-14D8-40F7-A46B-A0E9144D3A38","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f728e963338f0590fef2609026707340c65ee9d2","datavalue":{"value":{"entity-type":"item","numeric-id":162057,"id":"Q162057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260656$54A3B31B-9875-4BA8-9703-AE442A9605C1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63a2a2109a0646bfe8e8a3130f00ca3f280d500e","datavalue":{"value":{"time":"+1993-08-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1260656$84EC3BDD-D4DC-47B2-830F-DB8A63434A32","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"302402c2c1eab105d8688db30d61cc2ebf7dcd1e","datavalue":{"value":"The influence of randomization on the complexity of deciding the membership to semi-algebraic set is discussed. In some cases when a probability error in the answer is allowed, the complexity decreases. A general lower bound on the randomized decision complexity is obtained in the case of an irreducible algebraic set and extended to the case of generic complete intersections of polynomials with the same degree. Some applications to non generic cases (in particular to symmetric functions) are also given. In the introduction various examples are discussed, the next section is devoted to a precise definition of randomized decision trees, then a general lower bound is given and various applications are presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260656$2693109C-C3F6-48AA-B856-9543CD89E253","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260656$AA4D7E82-F7ED-47DF-B0FB-FE48992F3622","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"94a258fd6e09d2d582bb6c52c7992ac55d0da749","datavalue":{"value":"14P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260656$ADE1ED32-2985-44EE-9127-2015E41949A2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5cee606799eb34d7d518bfa986ef6275690dd169","datavalue":{"value":"370452","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260656$0CEFFC75-2DAE-4EE3-AC6B-900C6D069C2A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7957861eca4632af05aee5badf4e9c2ad34f6c80","datavalue":{"value":"randomized decision complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260656$42CF360D-33FA-4606-B2B8-E99761C03629","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"255f1bdf81346bd3c813b26aa2aec4f42f95c796","datavalue":{"value":"randomized decision trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260656$5222CA71-9E1F-4991-9D7A-D41F3F8A38EC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8af24bfd10b7ac3f1c1257cd8a47ae6c360b3ad5","datavalue":{"value":{"entity-type":"item","numeric-id":171409,"id":"Q171409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260656$01CE25EF-F422-4DF0-8C6F-CFD185035C05","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":"Q1260656$0AA48052-6DD9-467F-B2D3-26C332D102C5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c237974d652b7260e7f1e9d35e22bcd4cf8fc9c9","datavalue":{"value":"https://doi.org/10.1006/jcom.1993.1016","type":"string"},"datatype":"url"},"type":"statement","id":"Q1260656$246BCAAA-0488-44FE-BA0F-42C7D2866644","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a69debdb26e1a4514bf300eba2efb99349eaab83","datavalue":{"value":"W2032022602","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260656$349A471E-F5E3-4E0D-97B6-7F65CD2879BB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d885be813a7824618dd748276de1fb0f97ceed4d","datavalue":{"value":"10.1006/JCOM.1993.1016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260656$A726EDDE-0DB1-4657-A488-9F52C33FEF5F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a4c245cba9161418b46d14d25cd158307335d51","datavalue":{"value":{"entity-type":"item","numeric-id":1916424,"id":"Q1916424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13a2b76c8d5ae1e74ba9062386082c05109daf19","datavalue":{"value":{"amount":"+0.7853887677192688","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":"Q1260656$77C72035-D3DC-43E3-AF25-1996D725EF83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12d37f4d41a9254de3d653a9c8ca3493f86ce8f7","datavalue":{"value":{"entity-type":"item","numeric-id":1386178,"id":"Q1386178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67b09a6a101bd87667fcfbd8e342f91651863a24","datavalue":{"value":{"amount":"+0.7829546928405762","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":"Q1260656$AA3DA5A6-10DD-4B71-8B07-D9913552E570","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e1230218bada5144000c9a9e91537fc64ed3dc8","datavalue":{"value":{"entity-type":"item","numeric-id":4428715,"id":"Q4428715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"537dc3dbdb85b4039ce5a7dee5248519ba11dca9","datavalue":{"value":{"amount":"+0.7809256315231323","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":"Q1260656$0318F83A-684F-4495-A3C9-DFF8A204EA9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15440e4ea5a379d41e4e395d66b14d08ae9d775b","datavalue":{"value":{"entity-type":"item","numeric-id":4228517,"id":"Q4228517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76d26c45ea226a8452a2702bf49a7d65685e0bd8","datavalue":{"value":{"amount":"+0.7775116562843323","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":"Q1260656$7B9639A8-E099-4DD7-9008-5DC0085BA0F0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On randomized semi-algebraic test complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_randomized_semi-algebraic_test_complexity"}}}}}