{"entities":{"Q3002782":{"pageid":3013506,"ns":120,"title":"Item:Q3002782","lastrevid":79765802,"modified":"2026-05-06T14:39:43Z","type":"item","id":"Q3002782","labels":{"en":{"language":"en","value":"Linear degree extractors and the inapproximability of max clique and chromatic number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5899258"}},"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":"Q3002782$14D1FA1E-DDDF-4C87-B000-2208F7B09334","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4b1486b30b63d16ffd5dcf05f632041cae4549f8","datavalue":{"value":"1213.68322","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002782$4A083E13-2644-414B-B207-67C5DCA75225","rank":"normal"}],"P16":[{"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":"Q3002782$BAF0A0EC-D12A-43F0-8D0C-6902910F13BF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"11632bef515b8b0af0e8d65098d262d28b5f8c42","datavalue":{"value":{"entity-type":"item","numeric-id":2816408,"id":"Q2816408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3002782$D9B57901-9289-4ADF-9FEE-08FB93BFDF60","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"06770005a3ff7536cedbafe2a793f3c0760af601","datavalue":{"value":{"time":"+2011-05-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3002782$9EB6C559-58B6-437E-9907-22F0FFC265E2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002782$EB45FDCE-5BAD-47B8-A569-B32C2ECFD1C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c6dc32161cfbbc0543faafed5e6c564351d5db2f","datavalue":{"value":"65C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002782$3A748348-A7D2-4811-9944-D985D37A6994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002782$08203BC5-BB64-4CD8-8B2A-5CAF32317E95","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fdccaa43baabd7311e3d400a1bf67188000fc821","datavalue":{"value":"5899258","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002782$65B36D10-17E3-4F09-BE7C-38D3A3CB0419","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c011d2c06f8952f6e94e6ef026746e90647f36f2","datavalue":{"value":"extractor","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002782$271709CF-7DD2-44E1-B76D-418438A722C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d06ce36e382a1222c0d25591134f593d41cb28c5","datavalue":{"value":"disperser","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002782$DB0E738A-ED56-442F-B8AF-A6C2E3681859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002782$ECF85DA4-E3E6-44C6-B494-85B80B73648C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002782$07A84174-6D17-4E88-80D2-347DD9EFBE19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002782$C516082B-B5A1-438C-9642-592FC45183BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b44d3f732cb50abf873f800603732c6d83137fb","datavalue":{"value":"pseudorandom","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002782$DECB89D3-5884-489B-8CC9-E7DB732DDBCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7557a7948f6fd7a15949a6211d80d29e3293181c","datavalue":{"value":"explicit construction","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002782$13CB6154-0C3C-4FA5-8808-FB326A72CCE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q3002782$5D6E420E-1FD6-4714-B8C9-F89E9BC6CB91","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":"Q3002782$6A85E3D1-2912-4C7E-B8CD-CBEF1EE04CA6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"56858e8f3607ffd9c364e2e8ffb5137259518be0","datavalue":{"value":"https://doi.org/10.4086/toc.2007.v003a006","type":"string"},"datatype":"url"},"type":"statement","id":"Q3002782$55D84612-84CD-47B6-AF61-2F0B330B5E8E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e9546cd7922bb69935066cd709ff83bbe8cbacd9","datavalue":{"value":"W2610183793","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002782$EB55CD06-1356-459F-B8A3-3E7BBA6B51F7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"abe157176fe18a03d5662edf6936858e76a3b209","datavalue":{"value":"10.4086/TOC.2007.V003A006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3002782$93196720-3CF2-4F94-B8F9-81602276B9D5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc64b634e0188ed9e56d4eff0aba355bd4473bae","datavalue":{"value":{"entity-type":"item","numeric-id":2931428,"id":"Q2931428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe4314e06b18397e709c3b8dfb2c74cdb978f49e","datavalue":{"value":{"amount":"+0.998555064201355","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":"Q3002782$05E4C68F-5929-43B6-BF4E-D20CA380C4DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44ce2863dc482b3ef043a872532eab5672c8a2f2","datavalue":{"value":{"entity-type":"item","numeric-id":2817610,"id":"Q2817610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8552b2ead3f1c432b5e159f28fb34075e814f093","datavalue":{"value":{"amount":"+0.7987130284309387","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":"Q3002782$28EF0CD3-CF12-4EA1-A856-ADEE24B872D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff935d6ede7add5c348432a5c83c3a7ef30fd75d","datavalue":{"value":{"entity-type":"item","numeric-id":5901033,"id":"Q5901033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4242cc91e6408733f621c51b7b3649ed45de4cfa","datavalue":{"value":{"amount":"+0.7839738130569458","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":"Q3002782$85A008BF-4F5C-4846-A8BA-EB254A206B24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4306d641f18a6b07be4b83975ce1b53814b33fb","datavalue":{"value":{"entity-type":"item","numeric-id":4234096,"id":"Q4234096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de85e8b89980d77f61baeedffee246dc2c419456","datavalue":{"value":{"amount":"+0.7770425081253052","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":"Q3002782$B52CEBDE-3BE7-43CE-A6BF-831CF7E15436","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abff7155f277691234460bb6c08c44232bb10456","datavalue":{"value":{"entity-type":"item","numeric-id":1874411,"id":"Q1874411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8dd653e0ba82da2e6ec3e16dcddbb419b3c8d992","datavalue":{"value":{"amount":"+0.7750803232192993","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":"Q3002782$5F888122-38DF-4793-8DA0-56C1B27383B0","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"6a554977dfac80e46d734f83d88900a7dc80a6ee","datavalue":{"value":{"entity-type":"item","numeric-id":6830589,"id":"Q6830589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3002782$8A130C9C-8B38-49BF-83A4-10B859B525CB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Linear degree extractors and the inapproximability of max clique and chromatic number","badges":[]}}}}}