{"entities":{"Q1781113":{"pageid":1791855,"ns":120,"title":"Item:Q1781113","lastrevid":69051615,"modified":"2026-04-13T04:06:53Z","type":"item","id":"Q1781113","labels":{"en":{"language":"en","value":"Deterministic polynomial identity testing in non-commutative models"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2176382"}},"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":"Q1781113$E18465CB-A01F-46CE-BFDC-07C4B7AB874A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b22635969cd2a2823069a6cc32c2c685e5868c5e","datavalue":{"value":{"text":"Deterministic polynomial identity testing in non-commutative models","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1781113$DF957F3A-1729-423F-8157-13C17C0CF0CE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9915d0dd2f766b3f2759d25bde80aec4fafa6e16","datavalue":{"value":"1096.68070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1781113$D1DFA865-9A72-4C6A-A510-178403B1F3FD","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":"Q1781113$3063125C-DB5F-42C8-8022-49B75EDF1D6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"df2818b2e5985ee3ec3527ee35ad6a4603a9b58d","datavalue":{"value":{"entity-type":"item","numeric-id":232998,"id":"Q232998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1781113$BBB46072-4EEE-412C-8B1E-93A50E1B40DD","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":"Q1781113$168EE82C-AF7A-412D-8CFC-B43394796499","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"eafe75bd1c5dbdfb5bb9f91bc6b16760cad7672a","datavalue":{"value":{"time":"+2005-06-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1781113$599513E5-03DA-4C4A-8819-A98115297B28","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7bd8b3204605304169027f35143794a7ca586f71","datavalue":{"value":"The authors give a deterministic polynomial time algorithm for zero testing of polynomials in non-commutative variables given by arithmetic formulae. A similar deterministic algorithm determines in polynomial time whether or not the output of a pure set-multilinear arithmetic circuit is identically 0. It is also proved that any pure circuit computing the permanent or the determinant of an \\(n\\times n\\)-matrix has size \\(2^{\\Omega (n)}\\).  The proofs are based on the partial derivative method introduced by \\textit{N. Nisan} and \\textit{A. Wigderson} [Comput. Complexity 6, 217--234 (1997; Zbl 0890.68074)]. The idea is that the space spanned by all partial derivatives of a non-commutative polynomial \\(f\\) is of small dimension, provided that \\(f\\) is computed by a small arithmetic formula. A procedure to recursively check whether or not the relevant partial derivatives are identically 0 is also needed. Similar techniques have been already used by \\textit{S. Waack} [``On the descriptive and algorithmic power of parity ordered binary decision diagrams'', Lect. Notes Comput. Sci. 1200, 201--212 (1997)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1781113$63043C9A-04F7-4AEF-B60E-F720BD5ADB98","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e399d6aefd0456742c9468269315b44887e7fe50","datavalue":{"value":{"entity-type":"item","numeric-id":429755,"id":"Q429755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1781113$30975367-2C7F-4898-A5D3-C1D8333E918B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1781113$A81E8560-53E9-4AAB-8D94-0F9838900E36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1781113$365EBDF1-FFCD-40DB-B88E-4A77C16C9141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"661c831991cdebd51f9465b74d929024bd00f373","datavalue":{"value":"12Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1781113$7F0A010F-E6F1-4D06-99DB-74D6153F4A0D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"372a3b949dffeafb0e495befb622581fa29ba20c","datavalue":{"value":"2176382","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1781113$FBEB3AB1-4F09-4E5E-8305-815D8BB7971F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71df315845aed3ea96e6de75c6806537745705a4","datavalue":{"value":"polynomial identity testing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1781113$0BF212C1-5D9D-4066-B306-D42D17883585","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e957752335e4785fb5264f46ca1f3486062e224","datavalue":{"value":"non-commutative formulae","type":"string"},"datatype":"string"},"type":"statement","id":"Q1781113$FEB326CD-DDE2-4E3D-A955-C3748822EB3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"30806ee7ca780395482fd94541617d789c07cedc","datavalue":{"value":"arithmetic branching programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1781113$C64908E7-1F33-4DB7-B701-B90B960E6ECA","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":"Q1781113$DF4B3DF7-4A28-4B79-81C7-355B5A5B9A57","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2874c16c27687007c507ed84650d046d14bf7b60","datavalue":{"value":"https://doi.org/10.1007/s00037-005-0188-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1781113$0348A5DE-4F0A-4F17-B7C1-7DE001FBE35C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8ac9134cb88679e8684f17398524c2eae52d0841","datavalue":{"value":"W2121894367","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1781113$6651632D-B795-4BC5-B6A3-EBB938AC107C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"14c4e947864377557cd757ae460989f0740a9af0","datavalue":{"value":"10.1007/S00037-005-0188-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1781113$5AB35636-F58A-4F3D-8956-17EB6938B551","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9707471749492ac7fdd60c9de7554108cd2666a9","datavalue":{"value":{"entity-type":"item","numeric-id":4636636,"id":"Q4636636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f20ffdf049a78a7f8c8962d93eab1568ab28571","datavalue":{"value":{"amount":"+0.80936646","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1781113$214D3037-F5A6-4898-9AE9-1F14EBC66041","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c03e779de48d8fec7f58c70811109cb00fab0bb","datavalue":{"value":{"entity-type":"item","numeric-id":1377574,"id":"Q1377574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea49945a795bf698c013cc241d19e1e53e7f2795","datavalue":{"value":{"amount":"+0.77957296","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1781113$4661AC2C-3336-4FA5-9A1C-B4A3AC91AD7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55c75a5c2590616600e9a6ef9493f886ad8effed","datavalue":{"value":{"entity-type":"item","numeric-id":1407293,"id":"Q1407293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8584586be83c5e781c6f91014e995a5f84fad6f","datavalue":{"value":{"amount":"+0.7478449","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1781113$AEC72C22-731B-4C2C-8945-1AB696263255","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"608f39757fb6bdc7ea7755cc97fa717136368f15","datavalue":{"value":{"entity-type":"item","numeric-id":5916037,"id":"Q5916037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11eb4501425c0167ed8f1cea15670475bd00e354","datavalue":{"value":{"amount":"+0.7392253","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1781113$F9753EB5-F8CA-41DF-B9F9-4011293656CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9fa901e0aa1fe065f85dff1974761829e1c8601d","datavalue":{"value":{"entity-type":"item","numeric-id":5891430,"id":"Q5891430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32e10ca50a0b398e2e3e0174af0fe3464705dd04","datavalue":{"value":{"amount":"+0.73905134","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1781113$A53F67E9-3C8F-4867-BD18-BB51AD9AE8CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"967e93f74dbefbde900f848299a3d1f21d2f1762","datavalue":{"value":{"entity-type":"item","numeric-id":2351391,"id":"Q2351391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bfc4628375edad04ce19009bdd59e82b884c40d","datavalue":{"value":{"amount":"+0.73102057","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1781113$1358CA29-C330-4DDA-9C72-E78234446EA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e03c03ae6b93fd2dbc49ea769a2caa3a22bd5f00","datavalue":{"value":{"entity-type":"item","numeric-id":2872492,"id":"Q2872492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c6cda6ead9373cb76163018abae5070b5662228","datavalue":{"value":{"amount":"+0.7304603","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1781113$BEF67AF8-8E62-4D72-B0E2-AD7785FDB6B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c31ebb4cc817f7d4c0127d18a83f5989af8a9cad","datavalue":{"value":{"entity-type":"item","numeric-id":3587395,"id":"Q3587395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"314b1d5acfc3ef25848d6273a88f7f0e2c178bff","datavalue":{"value":{"amount":"+0.727788","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1781113$53D699C5-B6EE-4CDF-91CE-DD7AF0CF3C7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"956cbc6d486398c94f5d3482af62810c751e92eb","datavalue":{"value":{"entity-type":"item","numeric-id":287054,"id":"Q287054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a4a57fcc2642a0b2e0d999968cd80b8b6cc8b56","datavalue":{"value":{"amount":"+0.72421116","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1781113$D0714D74-03DB-4F2F-A4D0-E18B9DC74418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ad316b4d43f002884f406867fb9a74e77d03392","datavalue":{"value":{"entity-type":"item","numeric-id":794429,"id":"Q794429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"575f92f1c9041981ea365e4584fb3cb2a7de2a15","datavalue":{"value":{"amount":"+0.72345424","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1781113$01BF340D-4B8F-41E3-AE34-5D0ED655FA89","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Deterministic polynomial identity testing in non-commutative models","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Deterministic_polynomial_identity_testing_in_non-commutative_models"}}}}}