{"entities":{"Q2826080":{"pageid":2836818,"ns":120,"title":"Item:Q2826080","lastrevid":52642055,"modified":"2026-01-23T04:22:05Z","type":"item","id":"Q2826080","labels":{"en":{"language":"en","value":"Marginal hitting sets imply super-polynomial lower bounds for permanent"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6636367"}},"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":"Q2826080$19553153-E5E8-4E3F-B043-756BED020A3C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f13765539ee76c1b1fab1cf042982dd9f5490f82","datavalue":{"value":{"text":"Marginal hitting sets imply super-polynomial lower bounds for permanent","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2826080$08390F2B-0A3B-45D5-9547-8DF9F88E19F3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b39ee19eccd6d029aa2a8994e6d0db69e752272f","datavalue":{"value":"1347.68161","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2826080$70D1CB6F-5C82-4073-88EF-60EB946C56B0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"25fb24aa69e10d76a257baf19c9e94049cfb9ca9","datavalue":{"value":"10.1145/2090236.2090275","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2826080$A378ABC1-0A07-4A79-B698-1F66D8D7664A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"237f56d778239336558bfb14c864a3b857c523c1","datavalue":{"value":{"entity-type":"item","numeric-id":371191,"id":"Q371191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2826080$4739B2B9-6C32-446D-AA5C-2DB9948326D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b23adbfc18cdc63b7e63348213f20b490e75c5f0","datavalue":{"value":{"entity-type":"item","numeric-id":488048,"id":"Q488048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2826080$B3C9CAE8-CAC5-4D4A-AB16-A7EA5E9EBC53","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"32451d89b592afc9fed78c66786d58c23ffab6de","datavalue":{"value":{"entity-type":"item","numeric-id":2826038,"id":"Q2826038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2826080$EEA90477-1763-4D90-A1E9-0998251BA761","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"75c97569af4c6b39def7afa4b7124bea406ac5e7","datavalue":{"value":{"time":"+2016-10-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2826080$75FC9B35-CBFF-4E0C-94E6-6714BE6F1544","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2826080$D7A1BDD6-49A0-42FB-89CF-7801E83405D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2826080$8850E7E1-80F4-4C6F-B0E8-32585407992F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2826080$87CF0B82-4C56-4C17-91B1-56D73D77943E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e7412b1d04372654997235a3afc0c111999233cc","datavalue":{"value":"6636367","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2826080$FD36E3B0-1D14-4F1D-8D6B-CFCD3273C34D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"916f2a5439f7e4b36d4fe8bc533c45ce2dc6fc9f","datavalue":{"value":"arithmetic circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q2826080$AE596389-2817-4544-8EBF-44D663534D68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5f88a9c110a2ced0a0816bfa14fe61a8737c9e7","datavalue":{"value":"computational complexity theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q2826080$9928F320-B57D-432D-95EF-520CDC818BCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6b780876d6cd571fe1e41341c135a10b0acf751","datavalue":{"value":"derandomization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2826080$99E28CCD-82A0-45F8-AECD-F3C08BFD2891","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q2826080$E1B2FE72-6AD2-4871-BF16-D8567989C509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ecde75e20fea1230a086243cffda8342cc569a15","datavalue":{"value":"permanent","type":"string"},"datatype":"string"},"type":"statement","id":"Q2826080$ACBE24ED-3AAD-4AC3-8B9B-1A1708669D46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71df315845aed3ea96e6de75c6806537745705a4","datavalue":{"value":"polynomial identity testing","type":"string"},"datatype":"string"},"type":"statement","id":"Q2826080$81F3477E-F22F-4323-961C-B8EF67A5A7DA","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":"Q2826080$57CB1459-3BF9-4826-B377-3D2F46BA0406","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"457571084389ba654e76732ae70ecf944615652c","datavalue":{"value":"https://doi.org/10.1145/2090236.2090275","type":"string"},"datatype":"url"},"type":"statement","id":"Q2826080$BB2FAAF0-ECC7-440D-B0EC-50EAFBD70316","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5fbf12439b9d6ff6b26376d24b579cc6e24c1d98","datavalue":{"value":"W2072311401","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2826080$3EF1FAB8-44C8-4BC8-9CAD-9A84A72EC8A1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"19a1c9bafc893c75050dcd9b0f02433ff06fea3c","datavalue":{"value":{"entity-type":"item","numeric-id":3507516,"id":"Q3507516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2826080$FDD82EE1-2E20-41D9-98C7-CC1D372CDB7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8460d6f6bfcbf655916fd132c0033a7bf6137588","datavalue":{"value":{"entity-type":"item","numeric-id":5515914,"id":"Q5515914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2826080$CD9B1B04-BCC8-4DFC-A70B-B0D9800D4A91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18caa966d42a5021993ed69fadfc9c942c99ad02","datavalue":{"value":{"entity-type":"item","numeric-id":3959251,"id":"Q3959251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2826080$B845DA37-EC92-4547-B041-99CE291ACFA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fc8ce2527b3ea4f2925c1441476f44e789865b8","datavalue":{"value":{"entity-type":"item","numeric-id":5787788,"id":"Q5787788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2826080$A7F46F06-1F18-41AF-94C0-EC1F4EAEF19E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1725e39570121dc9056870e8c882d6e4c15d6d2a","datavalue":{"value":{"entity-type":"item","numeric-id":3627277,"id":"Q3627277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2826080$C609F166-A095-4A13-9B8B-DB1113D8E6FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94c7632f0e9afcbcbae6f503999f65611315cd5c","datavalue":{"value":{"entity-type":"item","numeric-id":4212770,"id":"Q4212770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2826080$4574CA0B-DDF9-4DF7-8EDB-234B4C3888F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"795bab1ee13e73ea624f513fe56ebff1ce1cd950","datavalue":{"value":{"entity-type":"item","numeric-id":4429684,"id":"Q4429684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2826080$FFED3EF7-38D3-436C-82AF-88D9E9ED6555","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e7049d19adb619fb9302e55ada60a2c32233d20","datavalue":{"value":{"entity-type":"item","numeric-id":1887139,"id":"Q1887139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2826080$80D5D921-279F-4DB5-BB5E-CF5419545B4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12cf9693e5e0d3a6ffb9450461a9b74076f797ac","datavalue":{"value":{"entity-type":"item","numeric-id":4701188,"id":"Q4701188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2826080$72ACED80-0D4B-40C1-AC5D-7E56C04DB06C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fea5c6cd1f5c4fb2ed274471fc8aa9ba9478590","datavalue":{"value":{"entity-type":"item","numeric-id":1434485,"id":"Q1434485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2826080$6019CBFA-DD99-4087-AF40-619A670283AB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2093046ae21a12095b67258b3644e13e746b4fbc","datavalue":{"value":{"entity-type":"item","numeric-id":1951581,"id":"Q1951581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"896e6bbbf3693e003034d921d4cd535463726f65","datavalue":{"value":{"amount":"+0.8450793027877808","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":"Q2826080$BC63A9DF-65C7-4EEE-9140-CBEFE60A9359","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7abed8a3fa11156e2caf97996a12fa92c2941d6","datavalue":{"value":{"entity-type":"item","numeric-id":3012845,"id":"Q3012845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a71762288d72cfd3334364d3062f1776105a415a","datavalue":{"value":{"amount":"+0.8381390571594238","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":"Q2826080$2E38139E-010A-45C2-B846-2F421104716D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5b3488c5921a3e7dac130d7ea67f2a9102829d7e","datavalue":{"value":{"entity-type":"item","numeric-id":1941704,"id":"Q1941704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8f6b4ec4ba8266ee07cf18d1b69ba3e7386ff58","datavalue":{"value":{"amount":"+0.8170551657676697","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":"Q2826080$1BFDE5C7-09A9-4AEC-A447-A7F02FC742AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4e0c0227aac0fa36d89d27fdc0b740a6e56b9c1","datavalue":{"value":{"entity-type":"item","numeric-id":2914346,"id":"Q2914346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c21cc0cd14b3cc2e14d079f03ca17c7037d4c82e","datavalue":{"value":{"amount":"+0.7961361408233643","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":"Q2826080$5111605E-2737-4F46-A619-3C883EFCB9F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"649eac039940f92b5a17a4deafb654193d06c975","datavalue":{"value":{"entity-type":"item","numeric-id":2911618,"id":"Q2911618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ff4292fe06aa82ed7c29390a2a4d462a5192f7d","datavalue":{"value":{"amount":"+0.792582094669342","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":"Q2826080$60066868-E3B5-41F2-9C10-C7DC3E098CFD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2826080","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2826080"}}}}}