{"entities":{"Q2113266":{"pageid":2124009,"ns":120,"title":"Item:Q2113266","lastrevid":55969384,"modified":"2026-02-21T15:09:43Z","type":"item","id":"Q2113266","labels":{"en":{"language":"en","value":"Optimal low-degree hardness of maximum independent set"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7488304"}},"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":"Q2113266$A80DE392-A6FC-49C3-9B2E-ED1EE78AB47F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6498eca4d82a6e7a669865b1e267371e9e98df39","datavalue":{"value":{"text":"Optimal low-degree hardness of maximum independent set","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2113266$E49F7CDE-32DD-4D1E-8DD4-55E676EE3C01","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0bf76b030debd8962f3443f9968d76e4d382f72b","datavalue":{"value":"10.4171/MSL/25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2113266$241C6636-6ADB-47CB-A737-012B946F1CB1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"01552ab65a2df5ac0833f2e137d07ad19345b177","datavalue":{"value":{"entity-type":"item","numeric-id":1729829,"id":"Q1729829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$F7FCED65-AEF4-4979-988F-E447333C0199","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dc21fa656a72c5bd4c84cbb6daa1826bf1ab50a3","datavalue":{"value":{"entity-type":"item","numeric-id":778886,"id":"Q778886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$0DC20B2F-9B12-4855-9904-53E2FE0D3CC3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"932a926f48f1a99d5c676a3e09211363b2f1c4d4","datavalue":{"value":{"time":"+2022-03-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2113266$68C4DE9A-E83B-49CE-B2F7-05D9EEAAF1AD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9b157ba3d62c52d50f648b923fe8041b0c8129d8","datavalue":{"value":"https://arxiv.org/abs/2010.06563","type":"string"},"datatype":"url"},"type":"statement","id":"Q2113266$5FC0C62C-A2FD-4B01-A095-E001BB3401CD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"75d74e9f062bd256f7667ec0b9f56a7650debb75","datavalue":{"value":"Summary: We study the algorithmic task of finding a large independent set in a sparse Erd\u0151s-R\u00e9nyi random graph with \\(n\\) vertices and average degree \\(d\\). The maximum independent set is known to have size \\((2 \\log d/d)n\\) in the double limit \\(n \\to \\infty\\) followed by \\(d \\to \\infty\\), but the best known polynomial-time algorithms can only find an independent set of half-optimal size \\((\\log d/d)n\\). We show that the class of \\textit{low-degree polynomial algorithms} can find independent sets of half-optimal size but no larger, improving upon a result of Gamarnik, Jagannath, and the author. This generalizes earlier work by Rahman and Vir\u00e1g, which proved the analogous result for the weaker class of \\textit{local algorithms}.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2113266$AF79355B-C55A-418C-83DE-7F521BB05482","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0dd26fa594336927a7a04e8147a405d69e5da239","datavalue":{"value":"68Q87","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2113266$3F2CC810-EAD0-42FE-8173-D192D4ACD81F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3c6a7ce6f5dffb8a4737c2fb60ffe5a55e5cdbdf","datavalue":{"value":"7488304","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2113266$1C2B76FF-9BBE-429C-B8E2-71B79B1F2EFE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5eda8bd7023928bbb11390a97ed8d88bcaca24c","datavalue":{"value":"low-degree polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q2113266$CBF032C3-FFFF-43B5-9C7C-B48D2210884D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2113266$33465F32-963F-4D9D-945B-56BDF3AE2F50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2113266$9E8F9833-329C-4F68-8D80-5E733C7E00A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aeb813de4de15a4d8a0347a12a8be12bae0b3a60","datavalue":{"value":"overlap gap property","type":"string"},"datatype":"string"},"type":"statement","id":"Q2113266$0353BBA1-D8BA-448D-AA01-67753FC578C2","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":"Q2113266$449E09B6-E82C-45AF-8EFF-8C672E68AEBB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4be1d8d85d05db9af784938a75a5177e4aa148d3","datavalue":{"value":{"entity-type":"item","numeric-id":2176074,"id":"Q2176074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$49414DFE-32A6-46F1-BB53-DE1CAD51A9DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79d039c03da44fbfce259446b3470e49df6d2e66","datavalue":{"value":{"entity-type":"item","numeric-id":5875785,"id":"Q5875785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$93CD846B-BF3A-4BDC-846C-A3A45EE295A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ea3f678d9feeb7b77f7f80fc4d3f9ae32a5165f","datavalue":{"value":{"entity-type":"item","numeric-id":4634034,"id":"Q4634034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$D0FB7B0C-58D1-4FFE-8F1F-A09A65D033AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51afd70b2a64cb11f657685991cd03c198d3269f","datavalue":{"value":{"entity-type":"item","numeric-id":5281076,"id":"Q5281076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$9F8B9CF2-B630-4025-8A41-2CE954E881A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d763103701655c7e851227546827f005e6037db3","datavalue":{"value":{"entity-type":"item","numeric-id":782415,"id":"Q782415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$47C3EC03-51BB-4141-951B-28C1D6CAACB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72cbe71d777fcac06036a4f46d586bd573e46413","datavalue":{"value":{"entity-type":"item","numeric-id":748442,"id":"Q748442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$A83AF721-BA94-4ACD-B3FA-B88D79CE735A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"211c534ba023c1999f5c01c2c8e698bebbfc4c46","datavalue":{"value":{"entity-type":"item","numeric-id":2421823,"id":"Q2421823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$AD1911E3-FADF-42E9-8418-7EE3428ED745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ddb40f2b4939dcc93448e9acab0c32591d28ab0","datavalue":{"value":{"entity-type":"item","numeric-id":5144947,"id":"Q5144947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$39E86EBC-26EC-4CD6-AD0C-BC91F3A56AD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee8dd7793f654e7d1f1e0e3be2351cb5079d9712","datavalue":{"value":{"entity-type":"item","numeric-id":5267998,"id":"Q5267998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$7C987F59-F43F-448A-A413-D484E484BCE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf0be8e64771976b9dfea83eb354f7e0c18e42fe","datavalue":{"value":{"entity-type":"item","numeric-id":2072085,"id":"Q2072085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$F4A826DB-C21F-41D2-B89D-85A223A46E71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95d31d569f0092e34aba63ab212c6f82ed91ba93","datavalue":{"value":{"entity-type":"item","numeric-id":923109,"id":"Q923109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$DBA42B64-0ACE-4922-860E-0C6C549AB36E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae1b45eac58e9b9f9fde658777d81b96d8ed7bf1","datavalue":{"value":{"entity-type":"item","numeric-id":2227713,"id":"Q2227713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$724C71FE-3FB7-4562-B066-6EA4E962BEDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adeaf1ee34c63b0da3b5b1726ba745e4beed0e5a","datavalue":{"value":{"entity-type":"item","numeric-id":5920116,"id":"Q5920116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$B319CBE9-AC8A-43D3-8899-C4C333657235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"442edd8e7e7af7007b999e94530105534e734354","datavalue":{"value":{"entity-type":"item","numeric-id":2453451,"id":"Q2453451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$F0D1E5E9-3A10-46C1-B29D-FF07B5A68B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8038b46c8c058d70085e18218513e794f2e48fc7","datavalue":{"value":{"entity-type":"item","numeric-id":5175645,"id":"Q5175645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$E594C8DE-DAA2-41C5-AE54-015235E7CBFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51565f8d5646366dc4c193a47e0e10ac1359e805","datavalue":{"value":{"entity-type":"item","numeric-id":2113266,"id":"Q2113266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$A0CA5380-05DE-4E72-A940-DA098B2FA4C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"295a70c178855625d44b3d929ce0d3758a1bb37f","datavalue":{"value":{"entity-type":"item","numeric-id":4144785,"id":"Q4144785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$243864BF-9693-4B17-A075-E4602907594F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d90692a3362ec05413a87162001696eb2689338","datavalue":{"value":{"entity-type":"item","numeric-id":2384807,"id":"Q2384807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$0DED5970-F2F3-4C9F-B472-EA45A23D1586","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8efe512e4769f733d0b0618cb0d2cc96e9e9661c","datavalue":{"value":{"entity-type":"item","numeric-id":2976981,"id":"Q2976981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$4E1EBCCD-07FB-409B-9771-33168AE51DD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"692f4f0ab28770fb6b56029f129e36a04279d6d3","datavalue":{"value":{"entity-type":"item","numeric-id":2012245,"id":"Q2012245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$4A71AB9E-443C-4735-A25F-B6E8A4D0E037","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bb6c76a0be253e100e8e5ac8397a4ffe778eb92","datavalue":{"value":{"entity-type":"item","numeric-id":4995560,"id":"Q4995560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113266$3089E1AB-7668-4F19-A844-08838680CDAD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed250fce22304dd3a430019c2df65efae7a2eb19","datavalue":{"value":{"entity-type":"item","numeric-id":3452727,"id":"Q3452727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a1354160990800df2fb0b4550cc7826d5ae4356","datavalue":{"value":{"amount":"+0.8208795785903931","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":"Q2113266$6CA9C12D-E321-4C83-B517-C2DC24170647","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd610933496719984f185af3331dc67a9f9a2d64","datavalue":{"value":{"entity-type":"item","numeric-id":5479377,"id":"Q5479377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fac4cdd0569bc6d5a84190de2b707813878f73b","datavalue":{"value":{"amount":"+0.8207207918167114","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":"Q2113266$F91D6FFD-108C-437C-BD78-E57B422994AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57324bbfebd60477c711b45d912a50b5fc7723d5","datavalue":{"value":{"entity-type":"item","numeric-id":3629470,"id":"Q3629470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1c155ebb5882e10523cb62eb5805ed2d9754638","datavalue":{"value":{"amount":"+0.818634033203125","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":"Q2113266$69704B19-77C0-4674-8CF7-0ACC2E6842C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ca050cb2d1ce3b50293226a54f15e4a64202f7b","datavalue":{"value":{"entity-type":"item","numeric-id":3525555,"id":"Q3525555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38f5d1a999f25c1e0699be19e8a9958184e4b4b2","datavalue":{"value":{"amount":"+0.8119843006134033","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":"Q2113266$38C50F68-B251-4240-A97E-95D611783577","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed250fce22304dd3a430019c2df65efae7a2eb19","datavalue":{"value":{"entity-type":"item","numeric-id":3452727,"id":"Q3452727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4392dc59047dd633c16ce1092904daf424c1b616","datavalue":{"value":{"amount":"+0.8094794750213623","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":"Q2113266$1B3306D5-CD54-4D34-A16B-C08E852FD378","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2113266","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2113266"}}}}}