{"entities":{"Q1024659":{"pageid":1026507,"ns":120,"title":"Item:Q1024659","lastrevid":42822732,"modified":"2025-07-14T11:14:55Z","type":"item","id":"Q1024659","labels":{"en":{"language":"en","value":"The strength of multilinear proofs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5565906"}},"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":"Q1024659$E0756823-D4B3-4E62-B8FC-CF71FFD94D09","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a8fa05ebc7499b41e9d91b6ef73555249a4424d3","datavalue":{"value":{"text":"The strength of multilinear proofs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1024659$7DFA476D-446F-4EEB-8149-523A2EF668D1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"247129e7db0784ce839c7a041922a30dd1ace096","datavalue":{"value":"1174.03025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1024659$70343F47-1216-4729-A679-FC3E97CFBB65","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b481d9d1e1fd6339de38d10a65dabc0f21090cc0","datavalue":{"value":{"entity-type":"item","numeric-id":168589,"id":"Q168589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1024659$B548D837-AC91-4DBD-BCC5-7F019C89E93F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4a6664b25304aa809ac73273551b57c46981097","datavalue":{"value":{"entity-type":"item","numeric-id":642519,"id":"Q642519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1024659$E720C963-8649-4BCA-8450-9AA900D25471","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1024659$AF9D3E9E-3C27-4974-A741-97FDD283C434","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b56d9fd9827ead92e1d841b592f7852bcfece777","datavalue":{"value":{"time":"+2009-06-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1024659$0838F028-8F16-4B7E-9C95-2BF2492129FA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"85f3177339707b65ef98a4321da534407ba4a467","datavalue":{"value":"The paper is a contribution to the study of proof complexity of algebraic proof systems. The authors introduce a semantic refutation system fMC (formula multilinear calculus) that is similar to the polynomial calculus (PC) except that lines of the proof are represented by multilinear arithmetic formulas. It is shown in the paper that depth-2 fMC simulates PC and resolution, as well as their common generalization PCR (polynomial calculus with resolution), that there are polynomial-size depth-3 fMC refutations over fields of characteristic 0 of the functional pigeonhole principle, and polynomial-size depth-3 fMC refutations over fields including a primitive \\(p\\)th root of unity of Tseitin mod-\\(p\\) tautologies. The last two results imply exponential speed-up of fMC over PCR and bounded-depth Frege. A general form of the simulation of PCR by fMC also gives an interesting result that certain proof complexity lower bounds imply circuit lower bounds (namely, any explicit super-polynomial separation between proof systems similar to fMC but operating with general arithmetic circuits, or multilinear circuits, respectively, implies a super-polynomial lower bound on multilinear circuit size of an explicit sequence of multilinear polynomials).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1024659$A3A1DED6-B997-4F4C-A12F-E067C90E7E5F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf05c748b19f894b0cb445a65a1da1ca24dbc809","datavalue":{"value":{"entity-type":"item","numeric-id":331053,"id":"Q331053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1024659$1A5CCC89-EBCC-49C0-A19D-A3C87A410AE8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1024659$1F61E0F2-0825-48D2-8053-59663BE623AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1024659$AAE95021-FA5D-44C5-A8AD-46BE6579642D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"173b0c3afec7c4f9f987722665cc7bdb6b8f5813","datavalue":{"value":"13P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1024659$F1279B4E-52E3-4089-98CD-EBBF21E874AC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c612b5b2df18781ddbf1f896412a6176f4f4bf88","datavalue":{"value":"5565906","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1024659$6F61E912-3CBE-43AB-96C2-E9D1C2E727B0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"986e975208b070c5142b42b7967bb38dc4fad0f4","datavalue":{"value":"proof complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1024659$BC2E79C1-D7DC-43B9-83F5-9E347FCF3B5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8549046e1af3a24c281e52588ef2d9732217a45f","datavalue":{"value":"multilinear arithmetical formulas","type":"string"},"datatype":"string"},"type":"statement","id":"Q1024659$F9ABD031-EC77-41ED-9B3E-CD3B07153B0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"211f3c345d1c27387d231726f7e79d65298863cc","datavalue":{"value":"polynomial calculus","type":"string"},"datatype":"string"},"type":"statement","id":"Q1024659$165A6987-1945-492A-AD17-D8704BEF7056","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b8e7d033342c99b72c744e65e5d3e8084428c65","datavalue":{"value":"pigeonhole principle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1024659$64E75D69-877E-473E-AA34-C74BFA262E1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7bcdadd08b463e1c3ebbef64e54e15cb174a5706","datavalue":{"value":"Tseitin tautologies","type":"string"},"datatype":"string"},"type":"statement","id":"Q1024659$E2A1A120-0F28-40C0-B520-57947D59D2E4","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":"Q1024659$813C752C-A178-42B9-AD62-DF5E5595E728","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"92cfd26d961955efcdafe97a96733043c5b7202f","datavalue":{"value":"https://doi.org/10.1007/s00037-008-0246-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1024659$E7857127-381C-4B1E-ACA8-0F57FC26B249","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f3f2e14bc70b5e708833d1892a505df77ddc29ca","datavalue":{"value":"W2074020517","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1024659$EC859581-0A9F-43E2-883D-0F4A4AAD024E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6b70fc3c6aa0f29b3abef84b33112f8209f3f9ab","datavalue":{"value":"10.1007/S00037-008-0246-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1024659$372B6380-5B8F-4081-97A8-E8FD55D5C73B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69e8b96e9b34a3808f72ead488ca3b7947fa6bcf","datavalue":{"value":{"entity-type":"item","numeric-id":1886325,"id":"Q1886325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a228f45257c71df2f88b409b98f9cd96148b0ebc","datavalue":{"value":{"amount":"+0.8695457","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1024659$47C2DA59-5687-4884-9134-DC8EA8077DDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64ecd93f90415636cab5e8e4efae8887280789ef","datavalue":{"value":{"entity-type":"item","numeric-id":3726014,"id":"Q3726014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7136e4199cf0f156754c442cb5179e98e826e1f","datavalue":{"value":{"amount":"+0.86322474","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1024659$46BED999-A4CE-45FC-BCF5-AA6E9A5A6DA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49879705ba5ae7bcd5eec17ead2d328a0adc00d6","datavalue":{"value":{"entity-type":"item","numeric-id":2110233,"id":"Q2110233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d250cabaae296ce9b914602be917ec88a251a617","datavalue":{"value":{"amount":"+0.86197805","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1024659$9EFD4F1F-9988-4C89-9C80-8641A5D69D11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28e2ce5af33dc165d9887836c40a254d4cb8025c","datavalue":{"value":{"entity-type":"item","numeric-id":5175988,"id":"Q5175988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc94e22d43d874ec9135206f319a4c6310271c61","datavalue":{"value":{"amount":"+0.85934055","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1024659$FEA9A63F-8067-4938-B367-9898B16DBF00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"614e0625461ba0ce6dd12019630b9e50b7a8631d","datavalue":{"value":{"entity-type":"item","numeric-id":580175,"id":"Q580175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1577d2378eb72dcb5240573cabf0c3d7bfd59362","datavalue":{"value":{"amount":"+0.85638434","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1024659$C420660E-0ED5-4ECF-84A1-9470D0F22401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c518395aa246f622d0c2ee99208bae427a398f65","datavalue":{"value":{"entity-type":"item","numeric-id":952492,"id":"Q952492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d09620e000f13d7c79c5de0c757b83000b06c22","datavalue":{"value":{"amount":"+0.8484444","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1024659$4E803F9C-3B08-4A86-B59E-EC509FDF4D47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8c004b08a566e18e292e3af58cbc17bb167929b","datavalue":{"value":{"entity-type":"item","numeric-id":5957910,"id":"Q5957910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0cef17e989f552273010f2bd31a322cd2552843","datavalue":{"value":{"amount":"+0.84520006","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1024659$995BD542-7BCB-4EB1-9580-5727E615FE67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"636acef347bb82b74a05847a68dfdf49a2cccb1f","datavalue":{"value":{"entity-type":"item","numeric-id":2300038,"id":"Q2300038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"249be20ced53b43469a1755eb32775dbf0771de2","datavalue":{"value":{"amount":"+0.844343","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1024659$BD6BF8F3-9A6E-4DE7-9E9F-647C7BA35D36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c27be3f5917f74ee96082d5f94e29995e15e94b","datavalue":{"value":{"entity-type":"item","numeric-id":4988917,"id":"Q4988917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"249be20ced53b43469a1755eb32775dbf0771de2","datavalue":{"value":{"amount":"+0.844343","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1024659$3BBCBB9A-42E3-4527-B278-DA6C8A96B31B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afe227919db66e25e02c2c9191bde7e2a1fcb02c","datavalue":{"value":{"entity-type":"item","numeric-id":3192060,"id":"Q3192060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53e1dc7d1fc0e3a6d8623d44aaa432e2c8f4c1e3","datavalue":{"value":{"amount":"+0.8432452","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1024659$2CA2496C-FC33-46AD-BB47-DCDBC31332E4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1024659","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1024659"}}}}}