{"entities":{"Q1888372":{"pageid":1899114,"ns":120,"title":"Item:Q1888372","lastrevid":73053855,"modified":"2026-04-14T09:58:02Z","type":"item","id":"Q1888372","labels":{"en":{"language":"en","value":"On polynomial-time property for a class of randomized quadratures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2117864"}},"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":"Q1888372$94547E58-B4F7-4F06-8CB6-2FF448B32CCC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b9d442b805ac1ce88a87d637a82b6ef2160d6faa","datavalue":{"value":{"text":"On polynomial-time property for a class of randomized quadratures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1888372$41466E78-F119-4132-B300-E1AEB91B2F2C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bd97ed0d0cc0481e9118d6a4261e1d84fb9a1ddf","datavalue":{"value":"1067.65007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1888372$3C3B1315-41CE-48C2-ADEA-B302015595E8","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":"Q1888372$31B62905-496D-4F79-8BDE-89431D7EE351","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f9270318d08aee06ff5ad0dd5710c08e39d64ffc","datavalue":{"value":{"time":"+2004-11-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1888372$E5AE8C64-8C7B-4C5E-9C8C-715A73D8CD03","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e18cb643cca5f47d2011f624c7c571185e60b9ba","datavalue":{"value":"A class of randomized methods for the evaluation of multivariate integrals over the unit cube \\([0,1]^s\\) is considered. In distinction to the classical Monte Carlo method, the proposed methods use a special importance sampling, which allows to achieve remarkably smaller errors. Besides, for periodic functions these methods require less restrictive assumptions to enjoy polynomial-time and/or strong polynomial-time properties. The polynomial-time property means, roughly, that the errors are bounded from above by a polynomial in \\(s\\) and in \\(1/n\\), whereas for the strong polynomial-time property this bound is polynomial in \\(1/n\\) and independent of \\(s\\). Integrals of the form  \\[  I_s(f) = \\int\\limits_{[0,1]^s} f({\\mathbf x}) d {\\mathbf x}  \\]  are considered, where \\(f\\) is a function of \\(s\\) variables, which belongs to reproducing kernel Hilbert space. Two types of kernels of a multiplicative form \\({\\mathcal K}_s({\\mathbf x},{\\mathbf y}) = \\prod_{k=1}^s K_{{\\gamma}_k,s}(x_k,y_k)\\) are considered with \\(K_{\\gamma}(x,y)=1+ \\gamma \\, \\min (x,y)\\) and \\(K_{\\gamma}(x,y)=1+ \\gamma \\, ( \\min (x,y) -xy)\\). In the classical Monte Carlo method, the integral is approximated by a sum \\(\\frac{1}{n} \\sum_{i=1}^n f \\left( {\\mathbf x}^i \\right)\\) with the sampling points \\({\\mathbf x}^i\\) independently and randomly generated according to the uniform distribution on \\([0,1]^s\\). The actually proposed methods use the weighted sum \\( \\frac{1}{n} \\sum_{i=1}^n f \\left( {\\mathbf x}^i \\right) / \\rho_s^{[\\alpha]} \\left( {\\mathbf x}^i \\right) \\) instead with the sampling points \\({\\mathbf x}^i\\) distributed independently, each with the probability corresponding to the probability distribution function \\( \\rho_s^{[\\alpha]}({\\mathbf x}) = { ({\\mathcal K}_s({\\mathbf x},{\\mathbf y})) ^{\\alpha}} / { \\int_{[0,1]^s} ({\\mathcal K}_s({\\mathbf t},{\\mathbf t}))^{\\alpha} d {\\mathbf t} } \\;. \\) The main result of the paper is the proof of certain error bounds for this approximation with the two kernels considered.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1888372$1CB1AAE6-64BC-4B49-8372-C5D02053C990","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"63aec181f5f25f527f4a50518ef030353abadcda","datavalue":{"value":"65C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1888372$38F81213-E92D-4952-AEAA-DE5AA5E927D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1888372$02288BA4-BACB-48D7-B8B0-36E0FD5F5C5C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"99da7626e8520c4a98cac66922e5452025d9cd20","datavalue":{"value":"2117864","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1888372$FC42398B-E9E7-4340-94A2-85C3B99ACE0C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5ede986e96679727264364b4abf6f19c420b80a","datavalue":{"value":"multivariate integration","type":"string"},"datatype":"string"},"type":"statement","id":"Q1888372$F6AACB3C-D2FF-4D9F-AAA8-A7AA0D8397C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"731b2d90aa6af12c2bb6fec69da63747d84012a9","datavalue":{"value":"Monte Carlo methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1888372$AF3F1B7C-2DC9-4F8D-94FC-923D7089254C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e3b9a2c122dd89be72ecbd4dd046019cd3c25be","datavalue":{"value":"importance sampling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1888372$2475EF15-19DA-4217-B02E-5A9C83F824FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3195016279ab1d9a9e1d68e3882bca32a61a40e3","datavalue":{"value":"randomized methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1888372$387FF36F-1426-41BB-A84C-9CE994EF89F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88ffd2ca9452a95455f19f35bfb3f100bed2aeb1","datavalue":{"value":"tractability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1888372$2B906C7B-B383-46B6-9D0E-14EF261A497D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d931c2e0be47b08f9286d195e541fddfd0662ba","datavalue":{"value":"error bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1888372$4076B4AB-8E98-443A-B5FF-7FBC7CD68634","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f519b505027c5198ad545e06a55293fbd1db884","datavalue":{"value":"reproducing kernel Hilbert space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1888372$9357E13C-FE0F-4C44-AD9C-05011E0813D1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c113d9074d7e915a6c50287c595a62d90d0b14da","datavalue":{"value":{"entity-type":"item","numeric-id":586769,"id":"Q586769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1888372$E6C9F29A-7CFF-432A-9304-6092A5C6B301","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ac0e823158ffeaec524ff1b93fae337337918ae4","datavalue":{"value":{"entity-type":"item","numeric-id":593265,"id":"Q593265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1888372$BDA44CEF-25FE-4C72-8580-718C293D0A2C","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":"Q1888372$D21D39AA-A3B5-400C-9498-48FC48B00188","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"957df7fd21ea8e600ebc58b42bee4b6c970fbc26","datavalue":{"value":"https://doi.org/10.1016/j.jco.2003.06.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q1888372$C99A05DE-A935-4FD5-8DF4-22F177189347","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"76b6e4aacf32ab705d20f31e2c14fffce8982e75","datavalue":{"value":"W1983684402","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1888372$CEDE86F6-D01E-4544-8E18-86AABA54C7F2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ba1c75679d69908da6ddfbbc81074b3c5cc154","datavalue":{"value":{"entity-type":"item","numeric-id":5795678,"id":"Q5795678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1888372$C12925F5-CB1F-47A5-B205-213A020F4E2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"780a562b3b42ebf2100395f27b9958e6b1410000","datavalue":{"value":{"entity-type":"item","numeric-id":4453500,"id":"Q4453500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1888372$FB707169-EE27-4172-B81E-5015469B2C47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af2fb2239c7beb6b13cc927188f9623a670ed5b3","datavalue":{"value":{"entity-type":"item","numeric-id":5946396,"id":"Q5946396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1888372$DAB2E442-3483-4723-AA4B-740D6262C7F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4f6689e96f07bbbcc4a00b139245b99bdd05734","datavalue":{"value":{"entity-type":"item","numeric-id":3311717,"id":"Q3311717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1888372$B611C8ED-20C0-49C7-832D-6A05C65F3E9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a9e2bb904b2f050d779b2de371d7fe83f4f50c6","datavalue":{"value":{"entity-type":"item","numeric-id":1265135,"id":"Q1265135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1888372$C469CB12-7146-4310-8EF0-FD8FEE7462FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"014fea9ddd7295deed909d721b56b308c677cec5","datavalue":{"value":{"entity-type":"item","numeric-id":3996207,"id":"Q3996207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1888372$919BEF9F-C8AB-46D8-9CB0-BA5A7B6379BF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"15a7a8a55a0ec73bb3d3bd5e6f7e26f8c4893cba","datavalue":{"value":"10.1016/J.JCO.2003.06.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1888372$1A5E05EA-ABFC-43D4-8193-9E4E351CBE35","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d873a94234db76907558783c17412da54f8b2a5","datavalue":{"value":{"entity-type":"item","numeric-id":4453524,"id":"Q4453524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"475594682c5782651e95976a6586ab77eef199b6","datavalue":{"value":{"amount":"+0.7994168996810913","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":"Q1888372$3C174519-21BA-4A94-8BD9-E1A47128D59C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a97656c9f68169673bb96a320d1be33bf5470177","datavalue":{"value":{"entity-type":"item","numeric-id":2407672,"id":"Q2407672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aea7530bc80bec7db152ada42895e537151a13e7","datavalue":{"value":{"amount":"+0.7809869050979614","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":"Q1888372$C2EE2DDE-8118-4E05-87B1-5DBE2509A857","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f481cb7fb72f39481c8b73ac775c11508920268e","datavalue":{"value":{"entity-type":"item","numeric-id":4442135,"id":"Q4442135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dd42d2b68be00cae3cdf1402eb4109a986bc33a","datavalue":{"value":{"amount":"+0.778762698173523","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":"Q1888372$4ED4EA8C-315C-4D65-B88F-2E0AA13E0696","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be6f483e8157076e648cc802c88bedd6a92311bc","datavalue":{"value":{"entity-type":"item","numeric-id":1109519,"id":"Q1109519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f74f30c2d76d8a7e56118d5dd230c74cfabd54de","datavalue":{"value":{"amount":"+0.7737348079681396","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":"Q1888372$8143F1C7-1D22-4CE7-8BE5-BACB4DD10429","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a03f7791fe60a1bd4b3e2e5b7809e4f2177e96ac","datavalue":{"value":{"entity-type":"item","numeric-id":4717946,"id":"Q4717946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfe73f4bd422009ae388f9a2dd5b6da1400b6de9","datavalue":{"value":{"amount":"+0.7714443802833557","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":"Q1888372$32075871-6A73-45EF-A1EF-656EA1FAAB94","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On polynomial-time property for a class of randomized quadratures","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_polynomial-time_property_for_a_class_of_randomized_quadratures"}}}}}