{"entities":{"Q1964592":{"pageid":1975334,"ns":120,"title":"Item:Q1964592","lastrevid":47445277,"modified":"2026-01-01T18:47:23Z","type":"item","id":"Q1964592","labels":{"en":{"language":"en","value":"A sublinear bipartiteness tester for bounded degree graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1404391"}},"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":"Q1964592$76A99BCC-BE30-47E1-ABCC-D337E2863D82","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"494b86d85626e439f4bea03d54339c0a4e5d41a2","datavalue":{"value":{"text":"A sublinear bipartiteness tester for bounded degree graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1964592$22AC4E92-5FBE-4191-A5AC-EB511A072802","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"57d6ffd786e14d4e5d00e35322a87524531e9c8a","datavalue":{"value":"0932.68053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964592$E8F2DAD0-096B-41B3-9C2F-37797F355AEF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cecf1ef8f97c75d3f636331253c64cfc37610336","datavalue":{"value":{"entity-type":"item","numeric-id":178474,"id":"Q178474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1964592$3CCFDEB3-D364-41FC-BC97-C8CBAB1893D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e10480e046eb228ee7883bfe3d51ac4b35b07ad9","datavalue":{"value":{"entity-type":"item","numeric-id":171921,"id":"Q171921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1964592$F46CC425-B3C3-45A8-9354-BE165EE01ECD","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":"Q1964592$E047C40B-B0DD-4ED9-BCED-C0550BF17B5E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b17fbfec200bcf11c37dd1a72a5e177de6557760","datavalue":{"value":{"time":"+2000-02-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1964592$B89AAC1E-EFAA-49BB-9771-51B49B0CCC30","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5509fdfc8026de2386034350b530ea355c56fcbd","datavalue":{"value":"We present a sublinear-time algorithm for testing whether a bounded degree graph is bipartite or far from being bipartite. Graphs are represented by incidence lists of bounded length and the testing algorithm can perform queries of the form ``who is the \\(i\\)th neighbour of vertex \\(v\\)''. The tester should determine with high probability whether the graph is bipartite or \\(\\varepsilon\\)-far from bipartite for any given distance parameter \\(\\varepsilon\\). Distance between graphs is defined to be the fraction of entries on which the graphs differ in their incidence-lists representation.'' Their algorithm uses random walk technique and its performance is tight (in a sense explained in the paper).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1964592$6577A117-4F52-417E-A481-707812C0A790","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a2423d4080d6028a3a8be7e0d0098fe6e3cd478","datavalue":{"value":{"entity-type":"item","numeric-id":226827,"id":"Q226827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1964592$D0B4770C-045E-456B-A81F-B2CB7782D0E8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964592$A40B78BE-D26D-45FC-B72D-5DABC5343513","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964592$ED93F3E6-FCD5-4C72-AE41-4332A8C28BA0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c477bd81e640e2efbfbde88c5b8cfffcb1d26af8","datavalue":{"value":"1404391","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964592$03A12399-521F-4024-9983-B37B81FAE0FB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91a22ec8a56ffe659d3f842ecf7f1e0c02ba5ff9","datavalue":{"value":"bipartiteness tester","type":"string"},"datatype":"string"},"type":"statement","id":"Q1964592$158E5BF7-4654-4893-B9EB-CE68D23E858E","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":"Q1964592$BC047E7F-48F3-4D85-ADC6-4D5CBF533FC7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"881f1f39efdec57dd6bd46c9e409c7e71604d8b2","datavalue":{"value":"https://doi.org/10.1007/s004930050060","type":"string"},"datatype":"url"},"type":"statement","id":"Q1964592$B458E28D-90FB-4919-8E13-C74DEDE39081","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c769f99b0d025ba77594247ee5d29e668d61a5f6","datavalue":{"value":"W2611773579","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964592$8EA6F170-331F-48E2-9DF9-7333F6195C53","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"88fb619a0e8bbc7ef994ae1179719fef8b9a0c56","datavalue":{"value":"10.1007/S004930050060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964592$2D8E5CFB-6B66-4468-8FF7-8814D3106450","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd6606ae18f5ca92e56ffb543eea039d076227d8","datavalue":{"value":{"entity-type":"item","numeric-id":4542547,"id":"Q4542547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7162b5a943808d947b2d8c5ac5abda53f35d30cc","datavalue":{"value":{"amount":"+0.970350742340088","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":"Q1964592$20082724-3DDC-4871-B415-4D56D4ED5FC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35132aa1ed18336eafeac370266c844c58921024","datavalue":{"value":{"entity-type":"item","numeric-id":4798173,"id":"Q4798173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7162b5a943808d947b2d8c5ac5abda53f35d30cc","datavalue":{"value":{"amount":"+0.970350742340088","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":"Q1964592$147D6216-5184-4317-9356-957A43A14C1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c2bdca9599937d421dde6d24f281b7ee148b0ff","datavalue":{"value":{"entity-type":"item","numeric-id":5900945,"id":"Q5900945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4591eba7d0defddf37ada4be7dde4b9b4f38daa4","datavalue":{"value":{"amount":"+0.8746461868286133","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":"Q1964592$0E60C953-9B75-4830-8DC2-08FCBB78B907","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d45713ff33eed1d52ad468217403591d1832cc4","datavalue":{"value":{"entity-type":"item","numeric-id":4651520,"id":"Q4651520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89f4b8b2d9ee8ba27fb739cac4cc5cc42d20d684","datavalue":{"value":{"amount":"+0.8734474182128906","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":"Q1964592$6B697239-807A-42A5-A3D0-C785F138E68E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6219c8f02ae8517503611abc88e827db755986f5","datavalue":{"value":{"entity-type":"item","numeric-id":5957578,"id":"Q5957578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14a846753c00598ad633b0ac357120b49111812c","datavalue":{"value":{"amount":"+0.8666893243789673","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":"Q1964592$3A2B5863-A917-449E-9F88-52DC533058AE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1964592","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1964592"}}}}}