{"entities":{"Q1017913":{"pageid":1019761,"ns":120,"title":"Item:Q1017913","lastrevid":69426786,"modified":"2026-04-13T06:55:23Z","type":"item","id":"Q1017913","labels":{"en":{"language":"en","value":"Lower bounds for local versions of dimension reductions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5553467"}},"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":"Q1017913$93C4999D-5D50-4E8C-9142-FD98ECDAFEC9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"19217b8960bbdee7d11f3f3e927f941ece73475f","datavalue":{"value":{"text":"Lower bounds for local versions of dimension reductions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1017913$EA35F3FF-4E77-4A6D-9BC4-266449271674","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2f503e386034920df86e2eddbe87b8f20554dde1","datavalue":{"value":"1171.46008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1017913$6C0D66EA-C957-46B1-A8B0-6006F49E712E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1ed22a01186aa8963d7a247e014c8e94e93219e","datavalue":{"value":{"entity-type":"item","numeric-id":281488,"id":"Q281488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1017913$B9A53E83-59E5-4A4E-B62E-30DD949E3B53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1e3625d8a7bc166a763f5261368249a556bac7de","datavalue":{"value":{"entity-type":"item","numeric-id":626626,"id":"Q626626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1017913$C0818680-146A-4CE1-9DCC-2F71787ABF5A","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":"Q1017913$37EC7513-11C2-40EB-A404-30168A812FF2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1fe241d3411c1f9d99ab0d39725dc84e6dd1a548","datavalue":{"value":{"time":"+2009-05-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1017913$5D31C834-9B56-40F8-8D77-395D991F5A63","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4bc94ecb047df7072fdacff3b7e2c1d8584a5334","datavalue":{"value":"The paper is devoted to the following problem: given a graph \\(G = (V ,E)\\) on \\(V = [n] = {1, 2, \\dots, n}\\), \\(\\varepsilon > 0\\) and vectors \\(x_1,\\dots , x_n\\in\\mathbb{R}^n\\), what is the minimal \\(k\\in \\mathbb{N}\\) such that there are vectors \\(y_1,\\dots, y_n\\in \\mathbb{R}^k\\) satisfying \\((1-\\varepsilon)\\| x_i -x_j\\| \\leq \\| y_i -y_j\\| \\leq (1+\\varepsilon)\\| x_i-x_j\\| \\) for every \\((i,j)\\in E\\)?  In the case when \\(G\\) is the complete graph \\(K_n\\) on \\(n\\) vertices, this problem is addressed by the well-known result of \\textit{W.\\,B.\\thinspace Johnson} and \\textit{J.\\,Lindenstrauss} [Contemp.\\ Math.\\ 26, 189--206 (1984; Zbl 0539.46017)] which asserts that in this case \\(k\\) can be taken to be \\(O(\\log n/(\\varepsilon^2))\\) and an example due to \\textit{N.\\,Alon} [Combin.\\ Probab.\\ Comput.\\ 18, No.\\,1--2, 3--15 (2009; doi:10.1017/S0963548307008917)] which shows that, for \\(K_n\\), this is basically the best possible; in this example, \\(k\\) must be \\(\\Omega(\\log n/(\\varepsilon^2 \\log(1/\\varepsilon)))\\).  The authors are mostly interested in the case when \\(G\\) is the graph induced by the \\(m\\) nearest neighbors of \\(x_1,\\dots , x_n\\). That is, \\((i,j)\\in E\\) if and only if \\(x_j\\) is among the \\(m\\) nearest neighbors to \\(x_i\\) or \\(x_i\\) is among the \\(m\\) nearest neighbors to \\(x_j\\). The problem in this case was suggested by [\\textit{I.\\,Abraham, Y.\\,Batal} and \\textit{O.\\,Neiman}, in: Proceedings of the 39th annual ACM symposium on theory of computing (STOC'07), San Diego, June 11--13, 2007, 631--640 (2007; Zbl 1232.68160)], it is motivated by several applications discussed in their paper.  The authors find an example (with \\(m = 3\\)) such that for each sufficiently small \\(\\varepsilon > 0\\), \\(k\\) still needs to be \\(\\Omega(\\log n)\\). The authors do not obtain good dependence on \\(\\varepsilon\\).  More precise results are obtained in the case when we additionally require that the mapping \\(x_i\\mapsto y_i\\) preserves the set of nearest neighbors.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1017913$51651935-4371-4F60-BCD8-45D651D81BD6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"79f8d64a9a918483c4e5229e22c3ea6d9711b362","datavalue":{"value":"46B07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1017913$29DA7795-C001-4064-81BF-85883540D662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1017913$A9BF5764-6790-4B5F-9488-2AD3BB68A821","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ba5f7486cfb64f062d1b1d8e48f356198d5bc8e7","datavalue":{"value":"15A03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1017913$BA853C94-E27E-4766-A112-79C6823CF551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"486e712aa0e58a7d88cad0afe626adea8bd0f027","datavalue":{"value":"54E40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1017913$3E0A558F-D153-4966-ABBE-B0465F092AAF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5fc99f42cc5a7d95fabecec140e1acb2b6354ba2","datavalue":{"value":"5553467","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1017913$BBC20448-7554-4896-B986-CFAAD2026C7C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"46170bee4b418ff2c2aeeebee3f703c7751ebe8e","datavalue":{"value":"Johnson-Lindenstrauss lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q1017913$E5D06AA3-E994-4915-A53C-7CDFA236A228","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ff9bb9ec5c186d802cd6cd54507e19f78f80787","datavalue":{"value":"dimension reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1017913$EAD27F87-1BFD-4364-8763-645BF8E09B6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8cf5808bbd1c5a01dcf7a4fc5d3596263e14345a","datavalue":{"value":"nearest neighbors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1017913$1AD69707-467D-401A-975E-C33417602821","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"14ba19fd9284d2cf0d8decec72dc0f5317181977","datavalue":{"value":{"entity-type":"item","numeric-id":394136,"id":"Q394136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1017913$E401C6B7-95F6-4CD8-90CD-28A7C2A3E6A8","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":"Q1017913$CFB00A85-49A1-4256-943D-5443F63E5AF4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"441c55851c8b0382c035ae5ab7fcc1ccaf1a4071","datavalue":{"value":"https://doi.org/10.1007/s00454-008-9068-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1017913$6B52B1DD-9892-487E-A708-F58469FEAA3D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"066e27fae23ec240d26e22df0b982892442a74d1","datavalue":{"value":"W2080339044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1017913$DD4D0AD4-C894-45A6-9AAB-0E999933B10D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f000705dbbddb4ab00eba4dcad9b17fa7546caa9","datavalue":{"value":{"entity-type":"item","numeric-id":5900541,"id":"Q5900541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1017913$BECDE0FB-C97C-4A3C-866D-E33CB7E1BB55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54f59301ba98ec3bb27385090337a77250bd504c","datavalue":{"value":{"entity-type":"item","numeric-id":3557502,"id":"Q3557502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1017913$2D4ACD0A-0A2C-4830-8EF4-85416E5D73E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08f7c961880f85b343b68aee76728ffb96b3b355","datavalue":{"value":{"entity-type":"item","numeric-id":4219187,"id":"Q4219187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1017913$D5F281B7-E0BA-4DD5-B4D5-DEACF81A441F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90b6fe1e6ca9f0f96e89b69032dd74b5fee6b7a3","datavalue":{"value":{"entity-type":"item","numeric-id":3326256,"id":"Q3326256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1017913$38C1E90A-6B4E-4086-A6FA-C6EFCCBAAC16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca4be033dc1e037b43c1538205386964bc6ef38a","datavalue":{"value":{"entity-type":"item","numeric-id":3514498,"id":"Q3514498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1017913$94304619-4E31-4E3B-9BCA-F7DE10C2DF7D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c84b0ce666236274e5b97148ee7e8dfc82cdc1f3","datavalue":{"value":"10.1007/S00454-008-9068-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1017913$FBC23AB7-49A9-41DE-99B2-76E07EB0B905","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"405c83b121ec3618c0944070d5e8b6ed37faf387","datavalue":{"value":{"entity-type":"item","numeric-id":5365087,"id":"Q5365087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"586cfbcf76045c7f67f09e12e0532057da0c2c18","datavalue":{"value":{"amount":"+0.8340629935264587","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":"Q1017913$55C6DFDA-E74B-4E28-A764-F521D243E032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bbdce4eeafe2dbd4b2bbf11e25e9b0c373e6570","datavalue":{"value":{"entity-type":"item","numeric-id":4633900,"id":"Q4633900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65affdf6fecc711a2e9093d1ac55af694cfa4301","datavalue":{"value":{"amount":"+0.8059594631195068","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":"Q1017913$7C5CE067-7A46-43E9-AE42-806144758751","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cddc0ed79def5e357f813ff3e9c8f39507e5ce28","datavalue":{"value":{"entity-type":"item","numeric-id":2385151,"id":"Q2385151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec2681ecf143f256f3f31a3d0787290de5649982","datavalue":{"value":{"amount":"+0.7997777462005615","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":"Q1017913$7B432E62-968D-41AF-A3B6-42335152BD1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db624c043fe980a8ac1689101d2281e4ae0e54bb","datavalue":{"value":{"entity-type":"item","numeric-id":4440441,"id":"Q4440441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39f0de007b2fa3dacf16811c798bbe6c67245e0d","datavalue":{"value":{"amount":"+0.7975493669509888","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":"Q1017913$DE074B6B-4B05-4A60-AB36-AA08B5729327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a836d5b7120bcd8d25206ddeaac3bbd18b4edd6c","datavalue":{"value":{"entity-type":"item","numeric-id":375695,"id":"Q375695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39f0de007b2fa3dacf16811c798bbe6c67245e0d","datavalue":{"value":{"amount":"+0.7975493669509888","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":"Q1017913$0F748F70-628D-4C73-96C5-D17A8D1D48F7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bounds for local versions of dimension reductions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lower_bounds_for_local_versions_of_dimension_reductions"}}}}}