{"entities":{"Q2941488":{"pageid":2952208,"ns":120,"title":"Item:Q2941488","lastrevid":58074435,"modified":"2026-04-03T17:07:11Z","type":"item","id":"Q2941488","labels":{"en":{"language":"en","value":"Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6474706"}},"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":"Q2941488$2864D04D-A773-4F3B-9818-4EEBA6EB6C4F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"90e269fdd3ea441d02189f74c43c447884a90aa0","datavalue":{"value":{"text":"Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2941488$4798D205-8B0E-4396-868E-877700B17B70","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f9e58a17530a6e3685f8dcc5061edcb103cc71d6","datavalue":{"value":"1321.68548","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2941488$7732E490-8C8C-4AD3-8B70-EC7D6FE59E97","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d02cb31af1d1b87b1a849573dd992571c815a7b6","datavalue":{"value":"10.1145/2746539.2746612","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2941488$19E46704-CC66-49F6-87D6-25DED3C74CBD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"619b3da40ce89470588c7f95a71532372f9ba3e6","datavalue":{"value":{"entity-type":"item","numeric-id":2843228,"id":"Q2843228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$6B125532-0DB3-4101-A592-36204BB0C7CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b7931955f1f617c7544e605edee3db1fe0846e3b","datavalue":{"value":{"entity-type":"item","numeric-id":732030,"id":"Q732030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$87C05B44-F953-4A55-8D32-23A8589A7FEF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85d346cdde70d3a1042609087e79b3009a8ef097","datavalue":{"value":{"entity-type":"item","numeric-id":2941480,"id":"Q2941480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$BDBC7B0D-E184-4073-85AF-2754D14A6B18","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e463a3f76b72914d69100f109f02e2f624263f82","datavalue":{"value":{"time":"+2015-08-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":"Q2941488$1D8A7990-5BBD-4653-BA19-51ADC0862801","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0698a9a93465d76f792fd076e6950d5c86caf7ec","datavalue":{"value":"https://arxiv.org/abs/1412.0348","type":"string"},"datatype":"url"},"type":"statement","id":"Q2941488$2BF0AC20-7681-4BBF-8881-1B0E68210439","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2941488$A9B40560-3214-4CB6-8380-7BBEF03C8938","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2941488$6324745F-CB00-4F03-B9CC-8FCF0BAC9E7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2941488$7A923CBE-35DB-40FF-B625-A01D4AB2C4CA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"12d7a7458ef200bcd729bc737aa785494147a148","datavalue":{"value":"6474706","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2941488$18644FE1-F0F4-47FD-9048-FC8DC16C48EE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78ac3261b77ce4fd3d632b98526dba4bf52e02f4","datavalue":{"value":"SETH","type":"string"},"datatype":"string"},"type":"statement","id":"Q2941488$E09F614F-F901-4A4D-9D39-7E1C66DD4BD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5a00923d0874cc52aeafb1476290f3a4a293a2db","datavalue":{"value":"conditional lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q2941488$10E2D58B-35AA-42ED-9747-16B15D9EECE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91c92c699214b9d1be7a56f31bd929aa164bb428","datavalue":{"value":"edit distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q2941488$693DCFF5-35A9-4364-9EAE-1FD60EB7756F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2450e02f50939b46b52c3140c8d1d485cebe36e5","datavalue":{"value":"pattern matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2941488$8093F3B1-4D12-4F9A-8F1F-B30DDEC91020","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"e3fb2701f07c7d6225b81753f8f4b7652ad5f931","datavalue":{"value":{"entity-type":"item","numeric-id":24208,"id":"Q24208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$967FE411-91BE-4445-921A-FEEE496DA99F","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":"Q2941488$BEB69E6E-D156-4597-B399-FFAC3CDBF677","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"15f96e928ef4839417db80247eeb3e03534205a4","datavalue":{"value":"W2055693471","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2941488$9625584B-B9CC-4203-984E-8A5D82279165","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b27d66af9a0812139ba919a8c2a94ba55f8c162","datavalue":{"value":{"entity-type":"item","numeric-id":3095345,"id":"Q3095345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$6178CD36-1C83-4BCA-AA30-FD8395C8D3CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"611d3e7c9668bce11095cc625704a0b304d94a87","datavalue":{"value":{"entity-type":"item","numeric-id":1196368,"id":"Q1196368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$4A27D4BE-C459-4574-9432-82DEE6ECB28B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54e0a6be99733eaeb2e2c0607e2cc442871e0104","datavalue":{"value":{"entity-type":"item","numeric-id":4210147,"id":"Q4210147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$BCB033C1-A93A-4497-BECB-EE7F8054EB57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8a6beef93c888a085e6e00d4dbfd4d6cb983614","datavalue":{"value":{"entity-type":"item","numeric-id":3521953,"id":"Q3521953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$26FF443D-3D15-4ED0-A88B-55423ED67B37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"715bece255906491939b4eb3fb90455d4770b609","datavalue":{"value":{"entity-type":"item","numeric-id":5259601,"id":"Q5259601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$1ED1272E-A8CD-41FF-A7DF-A32669BB8515","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9562975b659ee36323bc10f44914f734dbe22ea7","datavalue":{"value":{"entity-type":"item","numeric-id":4210144,"id":"Q4210144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$46EFE610-4365-4C72-AEF4-94BA461CADCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"897d6e7a261b274ddf28d766aaa4d79037054563","datavalue":{"value":{"entity-type":"item","numeric-id":997827,"id":"Q997827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$BE96E186-4AF9-4A10-9B57-A124551FB199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a647361e67809cabf8c312a0c65f24b224909505","datavalue":{"value":{"entity-type":"item","numeric-id":5414573,"id":"Q5414573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$F1EF2C94-386D-4A32-A78C-B6B48E36B641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7aa71cdf7b0f97a10b270ae9809b93535a3326aa","datavalue":{"value":{"entity-type":"item","numeric-id":1932671,"id":"Q1932671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$B5EB17EB-B3DF-40E5-8E29-579DC4DA1AB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b5c2a2555a6adb5115824b34a87580b6889dc09","datavalue":{"value":{"entity-type":"item","numeric-id":5716780,"id":"Q5716780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$5380E9AB-9718-4E29-891D-D55946DC78CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8ca31f8e4756b924f4d0f5010622dac45acfd75","datavalue":{"value":{"entity-type":"item","numeric-id":5176178,"id":"Q5176178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$45DD7E10-0FA7-4BA8-858E-F15A4B2F6361","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6f8a5087e5adfec5e35350c9dc4814ad45a304d","datavalue":{"value":{"entity-type":"item","numeric-id":3546311,"id":"Q3546311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2941488$A7D56507-3D5F-4A2E-AE7B-3F9A3186F1BF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"866712338005314a1e00e3e316801d3da5ce2275","datavalue":{"value":{"entity-type":"item","numeric-id":4571928,"id":"Q4571928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3089b63f699084d2116806a91c8bee2730b2b46c","datavalue":{"value":{"amount":"+0.9885501861572266","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":"Q2941488$4C07A3C9-AA62-4513-AA84-578D4212DBDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f6bc7195b07cc0ee5bcb4aba8185d7bdb6274ce","datavalue":{"value":{"entity-type":"item","numeric-id":5361845,"id":"Q5361845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e85c0029efda3c2e867b82adc328913d66bc3126","datavalue":{"value":{"amount":"+0.8470316529273987","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":"Q2941488$FBA83818-2FE5-4FDC-A0AF-6762C94F6B07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7513c844a4dc1c0d53b49357a70abf67bdbbd9c","datavalue":{"value":{"entity-type":"item","numeric-id":5056449,"id":"Q5056449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a2b06c0cd85ee3eae6ea93057416409ec61cbdd","datavalue":{"value":{"amount":"+0.8328109979629517","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":"Q2941488$3586A907-A5D6-4ECA-B524-F19317096739","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c139153c3053980e8e0a6d476fa66ef309d1afe1","datavalue":{"value":{"entity-type":"item","numeric-id":4910578,"id":"Q4910578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"989a2aa2d90cecd69b6f150c55aee7cf31cecd14","datavalue":{"value":{"amount":"+0.8284811973571777","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":"Q2941488$6F7380FF-CFE1-4081-B3EC-6FB691684017","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"977f40b0ff6ba05d045f3ac21de33c5ca8169574","datavalue":{"value":{"entity-type":"item","numeric-id":5172713,"id":"Q5172713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2dc9998c3d650d191670131a3a8ad43da0d357a1","datavalue":{"value":{"amount":"+0.8284655809402466","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":"Q2941488$80DC34B4-E23C-44F9-B3C5-0FAB38B790FB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2941488","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2941488"}}}}}