{"entities":{"Q1125612":{"pageid":1136361,"ns":120,"title":"Item:Q1125612","lastrevid":69700731,"modified":"2026-04-13T08:48:30Z","type":"item","id":"Q1125612","labels":{"en":{"language":"en","value":"Expanders that beat the eigenvalue bound: Explicit construction and applications"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1376200"}},"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":"Q1125612$99C9D62A-9208-4589-A07A-89E003671ED8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0b2c40ea18a9d8cfdb7c7483cd0c555425ed8910","datavalue":{"value":{"text":"Expanders that beat the eigenvalue bound: Explicit construction and applications","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1125612$4E97F642-7115-43FA-AED3-C7702F49D329","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7c8eb51449d291f415210dd946e03d25a38de07e","datavalue":{"value":"0929.05075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125612$F597BC49-7A04-4EA2-BB8F-E55DD70A48A6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3a028a6348dcfc7b43c17e257a75b67ed9a2b7db","datavalue":{"value":{"entity-type":"item","numeric-id":178716,"id":"Q178716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1125612$C5DCBC25-1F18-47B9-AE14-FEF77E2A43E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"11e9247244d7c5a83ff00535a80d8b3489fb0336","datavalue":{"value":{"entity-type":"item","numeric-id":294713,"id":"Q294713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1125612$56912DEB-9D4C-44B3-AFF2-7DCB6427100A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1125612$F7658E8A-9A0B-4FDD-8A87-5248722C3F40","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"01a219b50371d4e88ced51e1d6f1fa2b7760e9ca","datavalue":{"value":{"time":"+1999-12-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1125612$ECDB1E78-8C2B-492F-970F-9FC648A37485","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"93111a1526734f49176f3286bc300991a98fdf88","datavalue":{"value":"Improving the extractor construction of Nisan and Zuckerman a Log-space algorithm is presented that on input \\(n\\) and \\(0<\\delta<1\\) constructs \\(n^\\delta\\)-expanding graphs on \\(n\\) nodes with maximum degree \\(n^{1-\\delta+o(1)}\\). The following applications are given: a \\(k\\)-round sorting algorithm using \\(n^{1+1/k+o(1)}\\) comparisons; a \\(k\\)-round selection algorithm using \\(n^{1+1/(2^k-1)+o(1)}\\) comparisons; a depth 2 superconcentrator of size \\(n^{1+o(1)}\\); and a depth \\(k\\) wide-sense nonblocking generalized connector of size \\(n^{1+1/k+o(1)}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1125612$0E7DC042-5682-4C90-AFE6-39129BBB14BD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"826db22c8ad0fdc537525e95eba03f39da931f90","datavalue":{"value":{"entity-type":"item","numeric-id":178041,"id":"Q178041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1125612$9A738F83-3659-4B3D-B952-9980A889D4AE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125612$E5B491BE-3BD0-4A18-A68C-1CFC47F89D99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125612$55192D56-7908-4175-82F5-F23FA5CD8BC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125612$288DD747-40B1-48A8-8C32-98E79590C166","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"007f7f82691f1d7656215e5be329d57b0bfdf5e7","datavalue":{"value":"94C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125612$5D0870DD-75C1-4A5C-AABD-DD61607DE74A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9e0304e542811d4ed8053eb3583355561b4f49ce","datavalue":{"value":"1376200","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125612$E607043F-5E91-4E2A-AA28-981B1BBB5D78","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"527fd9bb73202f3ccbc2e98a6043eb9ea7b5dd2e","datavalue":{"value":"expander","type":"string"},"datatype":"string"},"type":"statement","id":"Q1125612$0F5C8D7D-D64D-430B-8698-F0F1D5F02CF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3e2c5cdbb9bf737c4fa7ac78971f831677d8a1d","datavalue":{"value":"graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1125612$64239D9B-9436-4E7F-B859-D68CACDA3974","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f081e8f6c5e915db6fc70bf8cbb8e4142a182e17","datavalue":{"value":"sorting algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1125612$6150AFB8-B440-4D92-9ABC-6A744BC60E11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"670fb15959500228d7f2381298d1adf83770e29c","datavalue":{"value":"selection algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1125612$44EC7060-8545-4530-B740-55AE657580C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c40f3db6946ae7379f4ccf7043bafc9be062c265","datavalue":{"value":"connector","type":"string"},"datatype":"string"},"type":"statement","id":"Q1125612$F51A80DF-448E-4656-A8FC-A42FF25EA6E1","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":"Q1125612$9AEDCE6D-53B1-491C-A330-39466BD97460","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5295a29bd50d470ff7f8da561a8fdf30bd136f45","datavalue":{"value":"https://doi.org/10.1007/s004930050049","type":"string"},"datatype":"url"},"type":"statement","id":"Q1125612$467E3340-AE60-4CDD-A149-D393EC32F687","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"95df418fdb2c7175c9e60fd167f490d7920651d8","datavalue":{"value":"W2611055803","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125612$C8285989-E8BB-4E83-AEC1-8CB7E9DBD220","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aedf8328031520654b503f88270542e598d2f8b9","datavalue":{"value":"10.1007/S004930050049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1125612$2BAFADA7-381D-471E-AE65-5B481A7E2990","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3732b558b19a592c0f5b26c35bd47d9c96829faf","datavalue":{"value":{"entity-type":"item","numeric-id":1112844,"id":"Q1112844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22eb5ab2a0b97729f34902e5672515c6acc7e94c","datavalue":{"value":{"amount":"+0.8750305","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125612$286E52F9-EECB-4242-8084-722FFC82FF73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"181a71425a471076d2e3d5821ecd609611854a8c","datavalue":{"value":{"entity-type":"item","numeric-id":343789,"id":"Q343789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"822bd220926af25418fa2b13dd4a2833eb4bbb3f","datavalue":{"value":{"amount":"+0.8697935","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125612$BD110903-0AC8-411E-B91F-173F7A9D7942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a1ecf5bd91c8daee0f2d8d91d22d0ad25336585","datavalue":{"value":{"entity-type":"item","numeric-id":5230365,"id":"Q5230365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66a2290fcebdf9321d56c9ebaae8650c51e8c76c","datavalue":{"value":{"amount":"+0.8479925","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125612$FC5D455A-4FC5-443B-A9F5-9EF0706E936D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c0e2438de7674558eff30d59fdc57073ac2b539","datavalue":{"value":{"entity-type":"item","numeric-id":2469518,"id":"Q2469518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97d43ffac40d31ae0f8aad3128823148361998a9","datavalue":{"value":{"amount":"+0.8455256","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125612$D47C745D-1118-42CD-B778-84916F0A60B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14928bfce6321e2fd5f605f9ff59a3a073282f98","datavalue":{"value":{"entity-type":"item","numeric-id":3700850,"id":"Q3700850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fcd011fca95e46f2ac953e9737e9c5cff06fc3b","datavalue":{"value":{"amount":"+0.8423179","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125612$A6842CD9-BBFF-4F73-A2ED-AACC839E7327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f3748d0ae1036f2b720aad942d012dec511d9ad","datavalue":{"value":{"entity-type":"item","numeric-id":3327198,"id":"Q3327198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dbd642cf9aabf4fb125a9c9527e5e94a49b2e09","datavalue":{"value":{"amount":"+0.8330941","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125612$A23B8C80-52E3-4344-949C-3A933AF166A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0ec183b28952fb640e68e4252cea5029d8c2f51","datavalue":{"value":{"entity-type":"item","numeric-id":2470810,"id":"Q2470810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2f697c70c1efa100def11db8671f25eded5a4bf","datavalue":{"value":{"amount":"+0.8321917","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125612$D939A943-4BA8-4A7B-BFDC-7ECA10A305DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4714decb1b9cfb68adeda09d529faa9140c8913d","datavalue":{"value":{"entity-type":"item","numeric-id":968983,"id":"Q968983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78b6b8ae52a7b1cb1ec59b78003fdfe72866ce9a","datavalue":{"value":{"amount":"+0.8292137","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125612$6EA61016-6DDF-46BB-9B3E-F43E907B227A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df37895a653939a46dfa9a39983d9750734c822d","datavalue":{"value":{"entity-type":"item","numeric-id":3088104,"id":"Q3088104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc44c7d299fc57b514d09f64e6854fce0e932263","datavalue":{"value":{"amount":"+0.8275561","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125612$97C7F05B-78D8-4D53-B2C4-AE88B3E78A30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c14aab9a1f751ee3ecc2e89a71d212d91fb74b1b","datavalue":{"value":{"entity-type":"item","numeric-id":1200388,"id":"Q1200388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fe05db19f7f82fcf809fa3c975c36fb424ccbd0","datavalue":{"value":{"amount":"+0.825825","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1125612$E3B9B2C5-8AF6-46F8-B3C1-E6ECFD8A143C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Expanders that beat the eigenvalue bound: Explicit construction and applications","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Expanders_that_beat_the_eigenvalue_bound:_Explicit_construction_and_applications"}}}}}