{"entities":{"Q3608306":{"pageid":5638212,"ns":120,"title":"Item:Q3608306","lastrevid":50590370,"modified":"2026-01-14T12:11:23Z","type":"item","id":"Q3608306","labels":{"en":{"language":"en","value":"More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5523060"}},"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":"Q3608306$3C850C51-2FE1-4652-83E5-D1F1B5CE778E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f5d6cbb97cc668faceb5341cd81b8b7c2314e0c7","datavalue":{"value":{"text":"More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3608306$492CD968-D1D3-4CDE-861F-B9CDD00CA229","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d0fad4a264b37c08e6f74041a6e3f71e9a7a6520","datavalue":{"value":"1159.68033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3608306$003110E9-9494-4D07-A23C-4C038F28133A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"84aa5ae388efa21613b45f9e666d214bc80076d2","datavalue":{"value":{"entity-type":"item","numeric-id":293271,"id":"Q293271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$28CFC8F1-E55F-41B0-B794-763C0F9865A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"08544295ce8be5f57d74368f4568c8f65dd8cd0b","datavalue":{"value":{"entity-type":"item","numeric-id":1874410,"id":"Q1874410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$C87A849C-75FC-4352-82DD-6B0160D30B1F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3434863a4c3842a9ef45eb54b7cfeda15cdee482","datavalue":{"value":{"time":"+2009-03-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3608306$3DA56556-6F10-4A0D-82EE-AE63B7B57D71","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3608306$9A980755-51F0-4056-B627-3CAE119DE2DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3608306$C929D496-32DF-4282-805A-B953160A756B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3608306$2FCA789C-BC16-4156-AF12-5A0B15D52CBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3608306$F430AADE-9814-45BF-8FE1-8A3519983882","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"40f4d072710030b4f3216f94ed52df889af7f8ab","datavalue":{"value":"5523060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3608306$1DF7BEA1-2D7B-40D0-9234-C7A63DBF479C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38ba5be85d75ef609e89c69759dd72605d61c619","datavalue":{"value":"probabilistic proof systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q3608306$1DB89082-068D-402E-9369-7164207C93EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"198526b3e16365d088b0d8e8cb1a48a9c3937632","datavalue":{"value":"probabilistically checkable proofs","type":"string"},"datatype":"string"},"type":"statement","id":"Q3608306$ADEADA68-2E83-40FC-999D-EF57CA35D506","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e6f2842ba16618da57de12b4c27b4274e41c364","datavalue":{"value":"approximation hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q3608306$7EAB3C4D-9977-4716-827A-77452F40F4EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0a11245e1fd646a6f1c526fac2a24da7e062337","datavalue":{"value":"query efficiency","type":"string"},"datatype":"string"},"type":"statement","id":"Q3608306$7AE2B73C-E171-4767-BC83-209C5D1CD217","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":"Q3608306$975E013E-2390-4878-8336-5ED328A6CF5E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b045f6ec66992daccd656bcbec790cfb0c69f672","datavalue":{"value":"https://doi.org/10.1002/rsa.20226","type":"string"},"datatype":"url"},"type":"statement","id":"Q3608306$76679952-2B12-4A0F-914D-410635ACD1DC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0cd6a84976e25c226822264098ff5fa1bb46dfbb","datavalue":{"value":"W4244547255","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3608306$C23A612A-8FC9-480F-8346-BAA8835929B7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed97d9cb381fa44bbd6ac9207fd7e4aa47354791","datavalue":{"value":{"entity-type":"item","numeric-id":3158513,"id":"Q3158513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$617CD7FF-A8AD-434E-8882-25CD84AB484D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11f3a5a6ef5b4dad2d6e7e841bea784191d0a73c","datavalue":{"value":{"entity-type":"item","numeric-id":3841041,"id":"Q3841041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$17C78688-1F3A-4F85-9671-F498F6F1232D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d83a00e805cb41e3f8ce716054d3b105e6a3db97","datavalue":{"value":{"entity-type":"item","numeric-id":626619,"id":"Q626619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$9B86D78B-C33B-458E-AA64-87A30397371D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6609aec37d3d301d34b253dc3f2a45a96b88e1d8","datavalue":{"value":{"entity-type":"item","numeric-id":1317490,"id":"Q1317490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$5EDE22A0-4780-4895-A5A8-C60E367F3458","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"732183f38719a5ffc0fae37c8e2ad20d7e91a145","datavalue":{"value":{"entity-type":"item","numeric-id":3581279,"id":"Q3581279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$FF33ACD9-87FD-4D25-8F81-D8563CDBFEA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2944680d9be1bbf82be438feb52f904d24769775","datavalue":{"value":{"entity-type":"item","numeric-id":4652625,"id":"Q4652625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$DCBF9FB5-65E7-4AE8-938E-C1FF8FC2E00A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca708f28bbf2af09e2d75d4fef17071cf823ad14","datavalue":{"value":{"entity-type":"item","numeric-id":1874411,"id":"Q1874411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$A14F24A0-2C97-4FB1-B2C5-7FA99F949A65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5eb556867ce03860e03d3995da051739781de0a3","datavalue":{"value":{"entity-type":"item","numeric-id":5710674,"id":"Q5710674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$4E254C2F-1205-4A08-9A50-A08C7D25211E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e153cf4f2dba4daff4d299a67edef7a4550aebb","datavalue":{"value":{"entity-type":"item","numeric-id":5311912,"id":"Q5311912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$5D2420A0-7BD8-4894-A1CC-532A15C5D836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"783f5b77f65178466163307ca17329fb72140e4a","datavalue":{"value":{"entity-type":"item","numeric-id":3158517,"id":"Q3158517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$C1CD2391-1AAE-4784-B562-956C7184FD9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7e4ec3391671959471e0dda3a6f5f980abca5fa","datavalue":{"value":{"entity-type":"item","numeric-id":4371671,"id":"Q4371671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$E8EC9296-604F-43EF-A089-266A8633CDDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a37862a96579439e34a623b2ac69d0460ee3cf5c","datavalue":{"value":{"entity-type":"item","numeric-id":3541788,"id":"Q3541788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$D43C0756-F3C6-441B-8C73-80DD08669598","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63223a2b10e799e0a620d9698b0286ebd9668db5","datavalue":{"value":{"entity-type":"item","numeric-id":5441360,"id":"Q5441360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$AE7F6815-4BA3-4316-897A-4FB08CCEADE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d294477451b4e4cf6da04717af8db29433f60eb1","datavalue":{"value":{"entity-type":"item","numeric-id":3002760,"id":"Q3002760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$7EF1C8FC-C069-42F1-81DE-D20D840CB88D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afda2e6fa57564a6ed691366eb6a9b9b66e0dd60","datavalue":{"value":{"entity-type":"item","numeric-id":4800393,"id":"Q4800393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$E7B3826A-E4DD-4A00-BD11-A6319AFE4AC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e1a59b9106a5dd5105f2bc476300c4cdae45ec3","datavalue":{"value":{"entity-type":"item","numeric-id":3579218,"id":"Q3579218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$E9466408-E909-4207-BF44-1F0D1D07BCC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc7c1b8cc24016a7c6b464cd2135f72b919e9781","datavalue":{"value":{"entity-type":"item","numeric-id":4388898,"id":"Q4388898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$21353E33-E79B-4549-9A1F-4ADE999DCC4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c838b9c29403a30009bc371ef6955e3141c412f","datavalue":{"value":{"entity-type":"item","numeric-id":3191985,"id":"Q3191985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$2B2EBE25-E811-4B73-8832-A82A24687A07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4eec5084aafd58cdbf5fa05cf5a3768036067f0a","datavalue":{"value":{"entity-type":"item","numeric-id":2931365,"id":"Q2931365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$76D13823-4244-4FD8-A4E9-751B1CBD4DC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76ded31745aedd0459b4ec8b3d21e229c79d6850","datavalue":{"value":{"entity-type":"item","numeric-id":4542548,"id":"Q4542548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$8CF10D2E-21C9-4DA8-A30F-19B318A2DD5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71c0cb7a161ad919041f584212aa203008053bea","datavalue":{"value":{"entity-type":"item","numeric-id":5691296,"id":"Q5691296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$7465FF79-094B-4A48-9A57-F95D93EFFF6A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d7d98279fb3f97fe714e272bcbfe8c37353a75bf","datavalue":{"value":"10.1002/RSA.20226","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3608306$F3095162-96EF-41CC-88C0-F428C97B8C49","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"607ae7f7d11ced7a8909533172911c64cec6dcc4","datavalue":{"value":{"entity-type":"item","numeric-id":6486797,"id":"Q6486797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3608306$DBB18B01-026D-42CD-BFA4-9E70E8095DE8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01d850795872c7a85048e40a18f76e87f980fca9","datavalue":{"value":{"entity-type":"item","numeric-id":5710674,"id":"Q5710674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9bb7c7eaf11af8c99d5bd1446225ba8f8bb0eda","datavalue":{"value":{"amount":"+0.9736002683639526","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":"Q3608306$6C681477-3070-4E60-8322-5929C312B9F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"096c7b05a032d49884bb09e5e61169650cb9476f","datavalue":{"value":{"entity-type":"item","numeric-id":3191985,"id":"Q3191985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b61761cdd7663614d7cc69c27ad59e388f70c57","datavalue":{"value":{"amount":"+0.8914579153060913","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":"Q3608306$25E50C07-CC1A-48F7-B681-2C2E5390828B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d022f375a7ee6b5c8c45656ce13c785de4152194","datavalue":{"value":{"entity-type":"item","numeric-id":3002760,"id":"Q3002760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5b4c8e7854efc64b45f55758b7f552d78756fb4","datavalue":{"value":{"amount":"+0.8634834289550781","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":"Q3608306$345EFC34-22DA-4035-9876-B071A36048D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cbb823a511c958f606d7afc3b1bb63fe154dcc1","datavalue":{"value":{"entity-type":"item","numeric-id":2986868,"id":"Q2986868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c6716be9049ace17f3253b7d23a479418e0f88b","datavalue":{"value":{"amount":"+0.8536006808280945","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":"Q3608306$B3B06312-ED8F-4B29-ADE6-A9092B6ACFA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b2f5d2ceb1ea193a21af8d748bfa696cc0b256e","datavalue":{"value":{"entity-type":"item","numeric-id":3579632,"id":"Q3579632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3409db6900916a8c7e110b3a3bd7d77cb1d8ecd","datavalue":{"value":{"amount":"+0.8379569053649902","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":"Q3608306$1EA1164F-9D2B-460C-BD70-125A311B143E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3608306","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3608306"}}}}}