{"entities":{"Q649096":{"pageid":650945,"ns":120,"title":"Item:Q649096","lastrevid":51376676,"modified":"2026-01-18T00:04:58Z","type":"item","id":"Q649096","labels":{"en":{"language":"en","value":"Homogeneous formulas and symmetric polynomials"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5982631"}},"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":"Q649096$90CAFE61-7457-4FC5-B8EC-376A060257B5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b585bf3f450a6453bdc90f48d975aba1d96d156a","datavalue":{"value":{"text":"Homogeneous formulas and symmetric polynomials","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q649096$8E7C239D-2974-4238-9DCA-FFE5D8E03436","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ca3cf2e91172c5940863e8cd752bdffe5fb35348","datavalue":{"value":"1233.68230","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649096$0D3A0C58-9E7F-4AFC-945C-F6EC38C62AFE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5e7ea3ca54733938686f141270931e22fee1769f","datavalue":{"value":{"entity-type":"item","numeric-id":436565,"id":"Q436565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649096$B8A593F1-C7EB-4634-B039-CAC05CC7FEF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5eafd83cd329c89e55ccb7791a949edc6adee55d","datavalue":{"value":{"entity-type":"item","numeric-id":251887,"id":"Q251887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649096$E7845317-45BA-456E-B624-B6851372B52E","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":"Q649096$D03CB2FC-3422-4A23-958E-400005A9036C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1819a172538b9934d4c5de27188f75c7b63afe97","datavalue":{"value":{"time":"+2011-11-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q649096$37C8FC9A-95C1-43FA-8205-124DD51BA226","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"825e4fe709f3c08bf271abf31e8bfcebb06360ef","datavalue":{"value":"The authors investigate the arithmetical complexity of the elementary polynomials \\(S_n^k\\), questions which were studied in particular by V. Strassen (1973), and E. Shamir and M. Snir (1979). Their main result is that every multilinear homogeneous formula computing \\(S_n^k\\) has size at least \\(k^{\\Omega (\\log k)}n\\), and the product-depth \\(d\\) multinear homogeneous formulas for \\(S_n^k\\) has size at least \\(2^{\\Omega(k^{1/d})}n\\). This implies a ``superpolynomial separation'' between multilinear and multinear homogeneous formulas.  The paper also answers questions of Nisan and Wigderson. The methods of proofs are algebraic and combinatorial.","type":"string"},"datatype":"string"},"type":"statement","id":"Q649096$1BD4C3AC-BDE3-4836-8CCC-B23C8937A516","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7b37a6de3a76a2f46603d2a1e14f19e4a44922ce","datavalue":{"value":{"entity-type":"item","numeric-id":168882,"id":"Q168882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649096$09A971BF-79DB-4507-AD88-B3CF4F3C2F10","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649096$E46EF41F-BDEF-4A1C-8D37-A52379181FE5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f5f9baf90de8d51e4ece0310b9cd46a1cb27899a","datavalue":{"value":"5982631","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649096$A0C7C19A-129D-4189-9414-FEF806AAADF5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"618469c390f3eb8a321c96d5432c7fd0f036bab5","datavalue":{"value":"symmetric polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q649096$27CF2128-FBC1-4514-BEF8-867EB7D76787","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"010c7d2ed2de24e1d8a535188cc19c40627ba1be","datavalue":{"value":"algebraic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q649096$C5051319-27D7-4C35-A5FD-B41159C31613","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":"Q649096$BD60D188-138D-4861-9500-9B6CF3053305","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d37e6ecc71bbf11e038b078f36aeeb70f91959e7","datavalue":{"value":"https://doi.org/10.1007/s00037-011-0007-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q649096$E1E4B77C-8F52-4C32-9702-533B8D5F9F86","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"946ae944476e8c25b92879a3f97103bb7c597794","datavalue":{"value":"W2049156754","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649096$4AD4F0A4-999D-45A8-A901-4B25180C4910","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3be357b4668768ccc0879b2547f5e037a4a4c3e","datavalue":{"value":{"entity-type":"item","numeric-id":5547602,"id":"Q5547602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649096$14667998-3EC6-4DD9-91F5-7D6911F7F054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57c0053965de559b0d0e8fc7727a00eef380819a","datavalue":{"value":{"entity-type":"item","numeric-id":4195943,"id":"Q4195943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649096$526CC2C6-CF07-44CF-927C-9A844DA9AF17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ed42a67ea4a489bc2843c16fc36181e4361fce2","datavalue":{"value":{"entity-type":"item","numeric-id":5606602,"id":"Q5606602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649096$CA2322CF-43BF-4DBD-866E-8F86CFE12879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40a661070eac50e350c3590de4635807200c625e","datavalue":{"value":{"entity-type":"item","numeric-id":1377574,"id":"Q1377574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649096$3D5BEB07-FB16-4A49-BC33-CDFC22661AA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a0327a4b861ac0c1d1b5f1943ede8b2eac4ac81","datavalue":{"value":{"entity-type":"item","numeric-id":5901079,"id":"Q5901079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649096$70DCEFC1-9994-4A5C-A84F-20C436C952BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42de6c4984bd46152b93fb05bfee9a7230abeec8","datavalue":{"value":{"entity-type":"item","numeric-id":3890111,"id":"Q3890111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649096$64BB62F1-29DF-4A86-B99B-671FB88C23C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42ecb7441e265815fa687cced1085cf99d8751fd","datavalue":{"value":{"entity-type":"item","numeric-id":5957088,"id":"Q5957088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649096$6689BC68-C579-4CD3-A8E6-ECB3144BEBEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"522e89673cb3122fd0bec879f19808cb3513e83f","datavalue":{"value":{"entity-type":"item","numeric-id":4047029,"id":"Q4047029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q649096$17AE6C12-2922-4ACD-94F4-E67C9D4FC9CF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a4ea475444ddefdd32e30c79cdd92104cdd9b1da","datavalue":{"value":"10.1007/S00037-011-0007-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q649096$D7B874C1-3369-4849-BBBC-646001465E45","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"291df9e3e3e84ca50eea038bb628f9bd90c28aaa","datavalue":{"value":{"entity-type":"item","numeric-id":990088,"id":"Q990088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b39a96a47e30e11368c1187589ba59d1cf2b01d","datavalue":{"value":{"amount":"+0.7917765974998474","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":"Q649096$B1177375-037F-456E-B44E-B3338FF72103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de7e522002bb86747298d212b5d190aeb8dcb496","datavalue":{"value":{"entity-type":"item","numeric-id":5395735,"id":"Q5395735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e86f3ecf9529a17839050045e836b78e6c5bbede","datavalue":{"value":{"amount":"+0.7864159941673279","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":"Q649096$ADC823FF-318B-4FD0-A356-9C1B66C492B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"379f79e1475911d5a91ff260f7cd538c8e33e980","datavalue":{"value":{"entity-type":"item","numeric-id":2875193,"id":"Q2875193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e473ce6c96d6897b0035d8b73a5660ec469dc48c","datavalue":{"value":{"amount":"+0.7838272452354431","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":"Q649096$EE48DF72-937A-4BE2-8299-56E2B2D729BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3bbf46a40e6ee996cb26d67c57dcc19c1bf4f84a","datavalue":{"value":{"entity-type":"item","numeric-id":5259545,"id":"Q5259545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8733ddd5bc23bad7ec0bb4e0b40015444798a9f","datavalue":{"value":{"amount":"+0.782386064529419","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":"Q649096$F20DFF81-D335-4555-87DC-84DC85D61CE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e62e9379c80d8e4d8e03d44783db174cba8e11c","datavalue":{"value":{"entity-type":"item","numeric-id":1872730,"id":"Q1872730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ad4800aae9680863af907727a6a10f83bf788ad","datavalue":{"value":{"amount":"+0.7814377546310425","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":"Q649096$9A54AF29-01AD-46A9-BBCB-E9E353C02037","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:649096","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:649096"}}}}}