{"entities":{"Q2783464":{"pageid":2794202,"ns":120,"title":"Item:Q2783464","lastrevid":83266904,"modified":"2026-05-07T06:55:49Z","type":"item","id":"Q2783464","labels":{"en":{"language":"en","value":"Berkowitz's algorithm and clow sequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1730388"}},"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":"Q2783464$3AC0AB60-937F-4A6C-8677-999443E0873B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a0e05e5e4dcb346beaa4609d75189efbf3465476","datavalue":{"value":{"text":"Berkowitz's algorithm and clow sequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2783464$247CAAD1-396D-4712-AA41-FC3BCDD0426A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"79c788897a54f6671384133e833d522602ebdf51","datavalue":{"value":"0998.65047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783464$F16EBE6B-BC16-4791-A745-092DD292C23C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"440035a0d0eb4f2031818de60c0f8b9cf79e8358","datavalue":{"value":"10.13001/1081-3810.1072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783464$5428BB80-DEC7-4B25-9C5F-0B09221C54C6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"06644c28854d4134a09144ca7d53b7f0310fd152","datavalue":{"value":{"entity-type":"item","numeric-id":453197,"id":"Q453197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2783464$4F97C8BE-29D8-4194-80D8-51E04467E102","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"22e17fffa644ae9f618754e26357d6dbd53b7382","datavalue":{"value":{"time":"+2002-04-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2783464$A0BACB0A-00FB-4050-9BED-BBEE304BB493","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9327274f68f40b9385eacf22805686d0fcaec57c","datavalue":{"value":"https://arxiv.org/abs/math/0201315","type":"string"},"datatype":"url"},"type":"statement","id":"Q2783464$37CA491F-3B9B-4217-9C7A-AF33363CEA32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"ab7e00e0d4063e93b173399f133210b5c5ad2cc6","datavalue":{"value":"https://eudml.org/doc/122179","type":"string"},"datatype":"url"},"type":"statement","id":"Q2783464$81C279F8-E07D-4966-B8AD-22A72AA40053","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"a0bf337807406cbd033240b89c30c26c91461857","datavalue":{"value":"http://www.emis.de/journals/ELA/ela-articles/9.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2783464$1F4F59D2-BB28-4CF6-9DFC-DAC73A27768E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"72309745094959b676ca20810c7af21a33fe24b5","datavalue":{"value":"65F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783464$1AB3C535-E54A-4715-BB03-2D6CFE502432","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"86467c42076cd02d03efdb91299b004ea1185418","datavalue":{"value":"15A21","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783464$2AB59EE0-F2EF-4A1D-BE77-0D2C73D6C124","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783464$1FF3C1DD-0C99-44DE-A125-BBAAB4F52454","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783464$9617994D-029D-41D1-9F34-EA6E177559FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783464$551F7C26-FA24-4561-AFC5-B78CA5962304","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5a034659b5122739bfb2373826d271e3937104ec","datavalue":{"value":"1730388","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783464$191C8BD6-DBEF-41CB-BE93-A4EBB528A7FE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c48483ac543fac39d7d0fe5a588d4709a18ed869","datavalue":{"value":"Berkowitz's algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2783464$04059429-AF46-48AF-B141-2BD574CFC246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56f3d90c9404f11b54d7aeb6f45ad0bb984d43af","datavalue":{"value":"clow sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q2783464$D6F00931-894F-4197-A66C-74DBD474A18E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc573c91a1c6d83ace780404954ab51908f47390","datavalue":{"value":"computational and proof complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2783464$F9E5D173-E94B-4EC2-97E4-A670206621AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2783464$B98D2D28-2AE8-47C7-9D69-977E5C1F5495","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64287d55cb2f38dd0f11da246e78f83648de9a8a","datavalue":{"value":"characteristic polynomial","type":"string"},"datatype":"string"},"type":"statement","id":"Q2783464$62079577-8256-47AF-ACAC-AA918CB8FF61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d6e1fca7ef54b848c3f9b1d701e27f213aa32c4","datavalue":{"value":"closed walk sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q2783464$5F75D116-B801-4ED9-A5FB-A4DCB7DC611B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d463b247e815798d799459507ebd3bcfc87bfad","datavalue":{"value":"Boolean circuits","type":"string"},"datatype":"string"},"type":"statement","id":"Q2783464$B4BDF103-E105-4F1A-AFCD-BFA799B042B7","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":"Q2783464$4757CC13-3B53-44EF-95B0-256822100AC5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f9a19de35d8edf967291533da67027d6ba8ae745","datavalue":{"value":"W2110783597","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783464$CFF4E37B-8739-47D3-A881-35262EEA4779","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"c72c324e4a8a3ee88f96fa5d5599e83dd8935c62","datavalue":{"value":"bafkreibin4wejx4ehjeeummat5u4v6uwb52do5l3fwijlieeachj5qthoe","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2783464$ACE05646-C56C-4C02-B9B3-947E6CC33A22","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"436a87ef223c8adc4608bed01c6ecfdd948db29c","datavalue":{"value":{"entity-type":"item","numeric-id":6628839,"id":"Q6628839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2783464$087C56C5-8D5C-4AEB-82F6-0AB5B55FA6FA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c5f03a4ce69cc44a15cf8e5c82f08d62bf6452f8","datavalue":{"value":"The author gives a detailed inductive proof of correctness for \\textit{S. J. Berkowitz}'s algorithm (BA) [Inf. Process. Lett. 18, 147-150 (1984; Zbl 0541.68019)] in terms of clow (closed walk) sequences defined by \\textit{M. Mahajan} and \\textit{V. Vinay} [Chic. J. Theor. Comput. Sci. 1997, Article No. 5 (1997; Zbl 0924.68088)], that is, BA computes the coefficients of the characteristic polynomial of a matrix \\(A\\), \\(p_A(x)=\\det(xI-A)\\), by computing iterated matrix products, and hence it can be formalized in the complexity class NC\\(^2\\). This class is the class of problems (parametrized by the input size parameter \\(n\\)) that can be computed with uniform Boolean circuits (with gates AND, OR, and NOT), of polynomial size in \\(n\\) (i.e. polynomially many gates in the input size), and \\(O(\\log^2 n\\)) depth (i.e. the longest path from an input gate to the circuit to the output gate is in the order of \\(\\log^2 n\\)). It is to be noted that BA is field independent, since there are no divisions in the computation of \\(p_A\\), and the results of the paper are field independent. BA is the fastest known algorithm for computing \\(p_A\\). The combinatorial interpretation of BA is based on ``loop covers'' introduced by \\textit{L. G. Valiant} [Why is Boolean compelxity theory difficult? (1992; Zbl 0769.68050)] and clow sequences.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2783464$E4989CA7-3BB0-4B08-AD31-C60F3F94AC2A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"dc96a1185c6ca67e17a98fbcdeda0f9aa229d3da","datavalue":{"value":{"entity-type":"item","numeric-id":402309,"id":"Q402309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2783464$790E6D82-01DA-4202-A4C0-C962F18D77D5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7c7b2aea5e1c60d9a0643856c1ea1aa711da678","datavalue":{"value":{"entity-type":"item","numeric-id":5054863,"id":"Q5054863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"654a873a6b3519b4eb48fa6ca2ce6af8747a6ad0","datavalue":{"value":{"amount":"+0.7442747950553894","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":"Q2783464$7E05B3C6-9901-45EB-A4A3-8B31DFC0B059","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ebb151ccc7a02c4f6c7812ab735cb8be59252b6","datavalue":{"value":{"entity-type":"item","numeric-id":4699172,"id":"Q4699172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf42afb362aebbc6928a11b79ba9612abb774e79","datavalue":{"value":{"amount":"+0.7287192344665527","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":"Q2783464$67FC0A05-44A4-45CB-868C-1B31A776DCC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0371d58ed7149883e6e2476f22c09bce52a87f49","datavalue":{"value":{"entity-type":"item","numeric-id":4259990,"id":"Q4259990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93c49db6948e37d1d37d16dea583c70751f7449c","datavalue":{"value":{"amount":"+0.7258078455924988","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":"Q2783464$E2D33EC1-AF80-4F41-9CFD-D5DF9DC5573B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8b8102f3ad567d6c5d54c2edb25a6fbc41513dc","datavalue":{"value":{"entity-type":"item","numeric-id":5301686,"id":"Q5301686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"096f36593d11977a8cdef6220b462afa8ff138b2","datavalue":{"value":{"amount":"+0.7158083915710449","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":"Q2783464$1DD1741B-A3B9-4873-9CAE-DD44D3DC310C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b5792b010f46060b043c9233e56fc4d873438ad","datavalue":{"value":{"entity-type":"item","numeric-id":5710448,"id":"Q5710448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84397e492a9fff3c119bcf49aeb46c18e9edd3bf","datavalue":{"value":{"amount":"+0.7049848437309265","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":"Q2783464$ACDDDA60-72A1-49CA-8DC5-3C7CE02BBA2D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Berkowitz's algorithm and clow sequences","badges":[]}}}}}