{"entities":{"Q1087143":{"pageid":1097895,"ns":120,"title":"Item:Q1087143","lastrevid":66897147,"modified":"2026-04-12T13:35:27Z","type":"item","id":"Q1087143","labels":{"en":{"language":"en","value":"A geometric inequality and the complexity of computing volume"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3988130"}},"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":"Q1087143$5972849B-E965-43FF-92CC-6FE7EE28FC61","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2c7daccb81d2ca375998462eb86a4ef1d4577504","datavalue":{"value":{"text":"A geometric inequality and the complexity of computing volume","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1087143$8EAE7022-DA53-4128-96EA-E77F1821936E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"42ec2edf583abec686ec424c5baeb0d972395584","datavalue":{"value":"0611.52010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087143$E7351143-D0D1-4352-9C19-65DD61BE3A4E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aab317361202909dfbaae7eb8f76fc8228a4baa2","datavalue":{"value":"10.1007/BF02187701","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087143$5CBA2D66-F734-4DD4-AAA5-743883B69FEB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087143$F80310DE-A93C-4333-BA6E-1940E05D7697","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":"Q1087143$1BDDC641-AD60-4056-BBE1-27A7F452743B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dd1abd3dbd52bca6488a9afd0090aedeef4212fc","datavalue":{"value":"https://eudml.org/doc/130996","type":"string"},"datatype":"url"},"type":"statement","id":"Q1087143$23A094E7-B956-4915-8E11-74089049CD7D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"32d38e26b468d90d630b40967af5359bcd3d0b18","datavalue":{"value":"A well-guaranteed separation oracle encoding a bounded convex subset K of Euclidean space \\(R^ n\\) does the following: i) For any point P it announces P in K or gives a hyperplane separating P from K. ii) It gives, in advance, a fixed ball S containing K and a fixed ball S' contained in K, by giving the center and radius of each ball. The authors use the fact that the volume of the convex hull of any m points of an n-dimensional ball with volume V is at most \\(V\\cdot m/2^ n\\) to prove that no polynomial time algorithm can compute the volume of a convex set K (given by this separation oracle) with less than relative exponential error. In particular, if for some \\(c=c(n)<1\\) the algorithm can give an estimate \\(v_ 0\\) for vol(K) up to a factor, i.e., \\(c\\cdot v_ 0\\leq vol(K)\\leq v_ 0,\\) then its running time is at least \\(c\\cdot 2^ n-(n+1).\\) A lower bound on the complexity of computing the width of K (using the separation oracle) is also deduced: if for some d(n), \\(<d(n)<1,\\) the algorithm can give an estimate \\(w_ 0\\) of the width of K such that \\(d\\cdot w_ 0\\leq width(K)\\leq w_ 0,\\) then its running time is at least \\((2d)^ n-(n+1).\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087143$37DA22B1-A234-4ECC-8AA2-7ADB3C9ADC35","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"145b3547074abae69f7ea12a847bac9f122cc911","datavalue":{"value":"52A40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087143$F61D8314-623D-47FF-8698-49287C544BD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087143$64A64E18-19C3-4585-82FB-B5EFF1618F46","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eda493537f905b3fa5b8343aeba8f4eec67eb614","datavalue":{"value":"3988130","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087143$0EAC3022-49D1-49BC-96A0-841C8CDB153C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e075788f9600f91f064afce214705683ed83762f","datavalue":{"value":"convex hull of m points in n-dimensional ball","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087143$E652D21E-9A3C-4C76-862F-15E9CFC247DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"636bdf3f525b5fe71fb545e9c56180d79024158e","datavalue":{"value":"volume","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087143$33A320BC-B06E-436B-A9EF-5E862F7BD1DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087143$4D90720E-2AC1-4B5D-B5CD-B9385B15C3C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95ba76843d142c13c11e1cc912c5378ae8a6699b","datavalue":{"value":"complexity of computing the width","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087143$5F164DEB-67E5-439A-82A5-EAA0B837E71C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c49b56e64bd0959800fdbd8e12bc023e5bdf4a65","datavalue":{"value":"separation oracle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1087143$C2455272-988B-4CED-BB2A-C44A2D210E26","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ba1b022bf20c2a3c593032bddfb5b4eeda173779","datavalue":{"value":{"entity-type":"item","numeric-id":168653,"id":"Q168653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087143$698A0543-44F8-4D1B-8C49-137D6B0DC658","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":"Q1087143$1AD4A277-713E-43E5-A16E-0073D01FB0E6","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"fd555c5534c0215a079276cd96ab7c4b671118fc","datavalue":{"value":"Q59410505","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087143$19ED3107-739C-49CA-A2CB-1411BFA1844A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d24725e7f57a3334d86dbcb2fee247207beff0b","datavalue":{"value":{"entity-type":"item","numeric-id":3329225,"id":"Q3329225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087143$F5452F7B-DF58-4059-BA23-DBEDBA3F6CA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92a3e9debcab806c14aff8e499e51be47c884542","datavalue":{"value":{"entity-type":"item","numeric-id":3745276,"id":"Q3745276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1087143$F297CD39-E4D9-4A34-BAA2-3ECA4CA68F1E","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"ab7e98ba47b3637fe55853cc330781371308adc9","datavalue":{"value":"journals/dcg/Elekes86","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1087143$63AD5605-3E66-402E-8408-CBFE54E66008","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3304b3e6328cb3aed49b35ceb69150abe9b40c5f","datavalue":{"value":{"entity-type":"item","numeric-id":1093369,"id":"Q1093369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c254253bf2b138efd8ea0de9713352e81b92cb6","datavalue":{"value":{"amount":"+0.8714720606803894","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":"Q1087143$12D76646-2509-4A41-A978-251E8033C053","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba3be1b76596debe9b9cd61b5d092d87e3fdfc87","datavalue":{"value":{"entity-type":"item","numeric-id":2368127,"id":"Q2368127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1769f668af556fdc9a42f60ed77983431f0c361c","datavalue":{"value":{"amount":"+0.8633304238319397","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":"Q1087143$FDA03FEC-B9B7-4639-9F1B-5602F51EC74E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a567bea845f3c2dde6e1516a09458cc1542201a5","datavalue":{"value":{"entity-type":"item","numeric-id":3361496,"id":"Q3361496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d78a492e1651804e35ea1999b3e3e321ae3b811","datavalue":{"value":{"amount":"+0.8587652444839478","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":"Q1087143$F2D171D4-7257-4733-BB79-A5BD70BD07A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e541347df771ee2268413a18578f93b07af11200","datavalue":{"value":{"entity-type":"item","numeric-id":4309969,"id":"Q4309969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88ecf56892e4526bacea03960e308b70affbbc29","datavalue":{"value":{"amount":"+0.7958716750144958","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":"Q1087143$CBBFED69-6E31-4C7A-A6C1-4F4CEA8A9D83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"061ec65d3a6847ba3b7817f1e9e81715a2173407","datavalue":{"value":{"entity-type":"item","numeric-id":4863381,"id":"Q4863381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c25b4cad234402e40a9acb4a6d3ebe55bed88da3","datavalue":{"value":{"amount":"+0.7956768870353699","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":"Q1087143$609D95F2-74FB-46BA-B7A0-EE231476923B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A geometric inequality and the complexity of computing volume","badges":[]}}}}}