{"entities":{"Q1065546":{"pageid":1076298,"ns":120,"title":"Item:Q1065546","lastrevid":66189543,"modified":"2026-04-12T08:09:27Z","type":"item","id":"Q1065546","labels":{"en":{"language":"en","value":"Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3924145"}},"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":"Q1065546$82C4EF84-02A0-4550-85BF-C942AAD3E7C0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7d2d4c984a3b1a7ea3f2831c9140382b9b16b7b4","datavalue":{"value":{"text":"Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1065546$3AA5329E-B8D4-4B96-BAD2-7C80004F1658","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"588c2ee1807ce696060d1c3b922e2ac329440953","datavalue":{"value":"0577.68060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065546$3774C11F-4E2B-4E19-844B-00F61B2AF6F1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ea2da44b12c506c435eae0153cb8a801e5f69d8f","datavalue":{"value":"10.1016/0022-0000(84)90029-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065546$EEBA4A27-FC56-4E7D-B0A9-2DE9F8D95E5E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9859a4dcc00fc8d1566f43eb1abbd6d402c90633","datavalue":{"value":{"entity-type":"item","numeric-id":751803,"id":"Q751803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065546$5B854901-A87B-47C7-90EB-B524B4EC05CE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065546$79FA441C-5D9B-4F27-A344-19607CA3BD9B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1065546$4230CD5F-0F8E-4D82-B738-38BBC3BA1677","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b82b496ffee7036a6c1dad832ae5143449d996ae","datavalue":{"value":"Lower bounds on the product TS (time \\(\\cdot space)\\) are obtained for any general sequential model of computation with random-access input (e.g. logarithmic cost RAM) for the following two problems. For computing the discrete Fourier transform with N entries over finite prime fields TS is not \\(o(N^ 2)\\). For computing \\(M\\times M\\) matrix multiplication \\(TS\\geq \\Omega (M^ 3)\\). Previously the same bounds were ascertained for straight-line programs. As an important technical tool a notion of mixing function is introduced.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065546$7AED2054-F6F8-4E3B-9F01-0437DF1FC3DB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065546$20FC15DD-B8B4-4692-A804-6D4FBF38E49A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fd2811201c5e0222c1dbbebc9c86a900557f19c3","datavalue":{"value":"3924145","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065546$E16E2221-E31E-41EC-85A8-5016FAA2B773","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a459471a373091a4dfec49ccefb26591da9ebae","datavalue":{"value":"Lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065546$F35C3F06-DEDC-4880-9A36-B75B0296ED61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee8763f78da0824eeb3d224d69ee8eb56cc8e7ab","datavalue":{"value":"general sequential model","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065546$606D268C-1AF6-4BF7-A6E8-E44EAC0A5DD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ace3e81a649cc52d585ee6069d0ac4f20bb74a17","datavalue":{"value":"random-access input","type":"string"},"datatype":"string"},"type":"statement","id":"Q1065546$91DC8725-4A64-44EF-983B-1DD984C02F39","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":"Q1065546$434CCE20-F785-4E21-8AE0-B039A99FF67B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ca1e4190c3df9dcf7ea84c6dd1f7fac29e0cf099","datavalue":{"value":"https://doi.org/10.1016/0022-0000(84)90029-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1065546$6530C584-251B-4E29-A285-237D67215D70","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6f8541cf713ba70b2553fad0b984e54ee320da56","datavalue":{"value":"W2009807436","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1065546$23BAE0CE-0B68-4BB7-8BEC-226ABAC918C4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065546$CDC3FA12-9190-44CE-9EDB-CC5B81004AE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfda1aaef4d74a55b724a4e4b97259bc5a577f06","datavalue":{"value":{"entity-type":"item","numeric-id":3936210,"id":"Q3936210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065546$6955F507-2F4F-45BD-B32D-6B4B0025F2DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ced94d64cba541a6dd4a04afa905ed5db4c5701e","datavalue":{"value":{"entity-type":"item","numeric-id":4109584,"id":"Q4109584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065546$A57C25E8-50AB-46C9-A4A7-5AFFA9669AC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065546$BC3DF946-E9AD-49C3-B41B-D7B21FA43CD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8deb347436f608da886b12b432642ffa2e8ea605","datavalue":{"value":{"entity-type":"item","numeric-id":5402558,"id":"Q5402558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1065546$56B09960-8844-4916-A0CB-82432268E8D4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c725c737f5d7f4134dbf00369c833654a10cfcad","datavalue":{"value":{"entity-type":"item","numeric-id":1176102,"id":"Q1176102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4adb6d624d17093ecb8296575ee740cf197424c6","datavalue":{"value":{"amount":"+0.8100489974021912","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":"Q1065546$9FB10484-EF78-4D85-B43F-8533050181D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62a60ff24fc907d02c6e2231b6a1bf220f30bb33","datavalue":{"value":{"entity-type":"item","numeric-id":1854488,"id":"Q1854488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"060a3506ffed7c65d027af10bd584e38931fdf35","datavalue":{"value":{"amount":"+0.7819392085075378","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":"Q1065546$D932FBFC-0C2E-4EC3-9563-9653DE69D77A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c2f89bbc1ffaaaa2e2834a8fa553eee6db9e155","datavalue":{"value":{"entity-type":"item","numeric-id":2662018,"id":"Q2662018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c52f6bad6856038ea6bc6d95cbf1f5774e21b1a","datavalue":{"value":{"amount":"+0.780193567276001","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":"Q1065546$7238B84B-2FA1-44AA-93B5-A100F46E466D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf2b966e8763263e242c640f5fe578b089d9eb4e","datavalue":{"value":{"entity-type":"item","numeric-id":1201877,"id":"Q1201877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19eebfad588b5538e5ed96113f3f093483d0685a","datavalue":{"value":{"amount":"+0.7795303463935852","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":"Q1065546$74D1A1D6-EF37-4164-88B9-B0EECDA5FE93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"149088ffb1b14214976941191100a205b7ca266d","datavalue":{"value":{"entity-type":"item","numeric-id":3026340,"id":"Q3026340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"104f5eb3a0ab1d9fe17d7e283bc5837613ebcfbd","datavalue":{"value":{"amount":"+0.7760211229324341","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":"Q1065546$DDDCF702-577D-4D75-9F6F-24DA1002388B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer","badges":[]}}}}}