{"entities":{"Q1346597":{"pageid":1357336,"ns":120,"title":"Item:Q1346597","lastrevid":68661468,"modified":"2026-04-13T01:15:59Z","type":"item","id":"Q1346597","labels":{"en":{"language":"en","value":"On the complexity of approximating extremal determinants in matrices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 740999"}},"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":"Q1346597$090B3A67-850B-4F20-9E04-17F4B98777A9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b05e55c5ec0d02bad49677f77b06f2243a7b88f9","datavalue":{"value":{"text":"On the complexity of approximating extremal determinants in matrices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1346597$E4E664E9-32A6-4526-9DE0-9B6BDDCCDC5A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d4219e1992525231c6b026ad55403484be26e180","datavalue":{"value":"0819.65085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346597$330A27AF-0C47-4BD5-A5FE-7D5AE8040720","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1419842bb8e98ef67f2bea44989c52cd03b97a03","datavalue":{"value":{"entity-type":"item","numeric-id":1315410,"id":"Q1315410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346597$FC517EAB-63A1-40E8-8C94-2576ED810F51","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":"Q1346597$77F05D4D-F7D3-451B-8359-36F26B7171D2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0bc5d1963845e10c2efccbe47fceacea0346b6ee","datavalue":{"value":{"time":"+1995-04-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1346597$E9ACBB94-E9CF-4CDD-842B-81F109AE0190","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"59e16306772e2e9bf49c9ceb3dbd5b214d83b108","datavalue":{"value":"The author shows that for any polynomial \\(p = \\text{poly} (d,n)\\) in the dimension of a \\(d \\times n\\) matrix \\(A\\), the problem of approximating \\(\\delta (A) = \\min \\{| \\text{det} B | : B \\in {\\mathcal B}\\}\\), where \\({\\mathcal B}\\) is the set of all nondegenerate \\(d \\times d\\) submatrices (bases) of \\(A\\), within factor \\(2^ P\\) is NP-hard. Using NP-hard it is shown whether a set of \\(n\\) rational points in \\(d\\) dimensions is affinely or linearly degenerate. Finally, an algorithm for approximating \\(\\Delta (A) = \\max \\{| \\text{det} B | : B \\in {\\mathcal B}\\}\\) within a factor of \\([1 + \\varepsilon d]^{({d-1 \\over 2})}\\) in \\(O(nd^ 2 (\\varepsilon^{-1} + \\log d + \\log \\log n))\\) arithmetic operations and comparison over the reals is given also.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346597$BBA05FEF-9461-4B08-B1AA-06F08919E79C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83fd851d78dc4c8819268c60531c7e9e72c3d7f6","datavalue":{"value":"65F40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346597$BE50952C-8CC4-415A-AAAE-22353BEAC9D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346597$C40A5ED0-8788-4D90-AE18-3703CD16A729","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8961e43da6ebb14f9a6c9a9eaac26713fd79f48a","datavalue":{"value":"740999","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346597$E8F3410C-C9FF-42B4-834D-5E35698151E0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346597$9B8350CA-BF34-416B-8838-5186D935A584","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f125b065712a9502917d313c9078eb84a8d65f7","datavalue":{"value":"extremal determinants in matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346597$B61FB23F-B34A-4A6C-8B42-D92651E8B72A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346597$379753E2-8E8B-467A-A3F7-B3592667DFDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1346597$BE054E9D-9590-4036-AAA3-FB146B5DBE57","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"60a621969070a06a28bf6cc8bc5af46472ca436c","datavalue":{"value":{"entity-type":"item","numeric-id":1434394,"id":"Q1434394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1346597$6FA1598C-E15B-4D22-A845-C33334306845","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":"Q1346597$594FC17A-9D88-49CD-AA39-B95768D90198","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"326d2ff55ed9a1cf630182ba40470fe2678f1b92","datavalue":{"value":"https://doi.org/10.1006/jcom.1995.1005","type":"string"},"datatype":"url"},"type":"statement","id":"Q1346597$4B27A11F-89B6-453C-9B00-3ACFE55D8B17","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e9b10e5c5803538ce84c0e179ee453b74697d556","datavalue":{"value":"W2005482089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346597$49286E08-06B9-4D00-9C59-86EE6A4EF875","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"15802fc3450fe7e8ad60cfcbce8b07c959660252","datavalue":{"value":"10.1006/JCOM.1995.1005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1346597$BBFABFEE-2D83-4C28-8CA9-B05171695827","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01d9b83f07c79c1e8a05a2498582218adc2a20fb","datavalue":{"value":{"entity-type":"item","numeric-id":5362979,"id":"Q5362979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9019e9e8aa8cfc94e4b1afe9e850383bf0a8fc88","datavalue":{"value":{"amount":"+0.7966539859771729","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":"Q1346597$6EEA4BFA-109C-41EA-AC6E-1BF33A607619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5844a9548a68fa741dbecdcc43254050e944165f","datavalue":{"value":{"entity-type":"item","numeric-id":1307698,"id":"Q1307698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cf238675980fb665da6620a2f8ffd145a1d534e","datavalue":{"value":{"amount":"+0.7706606388092041","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":"Q1346597$4C3D56CF-FE1E-4F2E-A98B-485B263AED18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86ed5a4eff84c8c366ff8686c96d7606225850f0","datavalue":{"value":{"entity-type":"item","numeric-id":1405783,"id":"Q1405783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e27cc81171961814d45e5cb1575dd48a7f147b4","datavalue":{"value":{"amount":"+0.7697755098342896","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":"Q1346597$FBC6A7D4-B6DE-4E08-9AAA-BA2EFBDA5EEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5cb2d93b1446575463e805646db8775c4e3fe656","datavalue":{"value":{"entity-type":"item","numeric-id":1806034,"id":"Q1806034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0addb3cad0fa27e384a5bf640c680ffb5b11cffa","datavalue":{"value":{"amount":"+0.7632593512535095","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":"Q1346597$89543F89-46D4-4E7E-8AC0-EB16A082B0AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff0cc7d6061a292691c8ae249953e420d56c5dce","datavalue":{"value":{"entity-type":"item","numeric-id":1034598,"id":"Q1034598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3de3c851746ba07cc148417a99b01fd178676a6","datavalue":{"value":{"amount":"+0.7630015015602112","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":"Q1346597$F0E46D6B-ADF5-4833-8D89-5668A1BE8DD3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of approximating extremal determinants in matrices","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_approximating_extremal_determinants_in_matrices"}}}}}