{"entities":{"Q5090435":{"pageid":7120011,"ns":120,"title":"Item:Q5090435","lastrevid":55413664,"modified":"2026-02-17T15:51:05Z","type":"item","id":"Q5090435","labels":{"en":{"language":"en","value":"Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7559099"}},"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":"Q5090435$CFC6C37D-212B-4BF3-B66C-71A5E3A03F3B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"faf323fb9e9f7c8d893e5231b2bf47698fc4b676","datavalue":{"value":{"entity-type":"item","numeric-id":5090434,"id":"Q5090434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$31623579-99B2-4F33-B429-6D153F7992F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"78a3ebf267830b34bb8ced5ebe00bd1ba645205f","datavalue":{"value":{"entity-type":"item","numeric-id":937200,"id":"Q937200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$A53C9225-8A8E-43E9-81C4-36F2B86BCF9E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6793430fc5b4ace9180691774574e339423361ba","datavalue":{"value":{"time":"+2022-07-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5090435$7F697D0C-F272-4FBE-B787-0589D6653FD2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f969879f531643f058f8dd4c87a7dd4eb7b8c4c8","datavalue":{"value":"68Qxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5090435$09159294-D3B5-4E3E-B570-9EB2E1499056","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1f5bc778da375ad04a6184257434192fe6ad2c95","datavalue":{"value":"7559099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5090435$31FE5DC1-101B-4FE6-9B34-1915D1CE6BAC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec24897927a0742784fae89aed9a922bc2a81fec","datavalue":{"value":"branching programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5090435$1EF8290B-3F2A-4BD9-9D42-69D37B50C4D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d243e060be5f8c397fa8b96e683ca1b64d47b073","datavalue":{"value":"random oracles","type":"string"},"datatype":"string"},"type":"statement","id":"Q5090435$176A24B5-5F49-41C5-9036-C877F0206B5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bf5e86d34b629e124b4bc7a75dd155da8e3cd8d","datavalue":{"value":"time-space tradeoffs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5090435$6EA89450-79BC-4AC5-BD22-C0E12B511A0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q5090435$D8CC8943-5F05-48BC-8B08-9059B1E5CD3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5867ec7b44aefc01672736513dfe6410a0300cd5","datavalue":{"value":"SAT","type":"string"},"datatype":"string"},"type":"statement","id":"Q5090435$C8536F48-B5B2-4967-9C3F-D844DB4B2C38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5540e3a97aefc78b1cc58b39eaa31222058ad3d","datavalue":{"value":"counting complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5090435$C30CDD2E-EE14-469D-8357-06AC2338BE71","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":"Q5090435$065B13D1-FEED-4625-AD72-C152D30DB334","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe1806742d8bdb7f1e88779a2c5629b608d36a03","datavalue":{"value":{"entity-type":"item","numeric-id":3790661,"id":"Q3790661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$0FF434AA-A314-4F26-AA66-5B0F70C2268A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b2cb4894c9300ce14e43ee0bcd37557703e3535","datavalue":{"value":{"entity-type":"item","numeric-id":1176102,"id":"Q1176102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$F62A0693-DE0B-4652-B104-3815B449C810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"add8d07cbc87d19da403e0fe882fcf6513dc7b1d","datavalue":{"value":{"entity-type":"item","numeric-id":1869934,"id":"Q1869934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$00866510-844D-465F-86D9-7D2FF3F9248B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d32c3a04c5b2c5d49c75130c55c7113418f0e3a","datavalue":{"value":{"entity-type":"item","numeric-id":3002761,"id":"Q3002761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$B3363E24-AADC-432F-B85E-EA4778F1A53D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d8653d2e6f53b17cedec7b9470bcf88609d4f1f","datavalue":{"value":{"entity-type":"item","numeric-id":5320667,"id":"Q5320667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$729EBA4A-90B7-487B-97E2-538736DBAABB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96799e6f2b17a2e37cc41d736e6f0ae192b84ef0","datavalue":{"value":{"entity-type":"item","numeric-id":1183604,"id":"Q1183604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$E9676936-AD66-4EB1-9ABE-983418E65CCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"197c225799e487294a747ce7acf284840e35974d","datavalue":{"value":{"entity-type":"item","numeric-id":3210181,"id":"Q3210181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$D76D35AF-DC10-4E52-8F8E-1E2870EFB853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e829ea50318f576a76deefc5f66e35383fc7395","datavalue":{"value":{"entity-type":"item","numeric-id":1604208,"id":"Q1604208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$9679941E-B8BE-45CE-B7F0-73AFFDA43DDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e8c6d821a4f69ba181c2830853e09ab999c4e4f","datavalue":{"value":{"entity-type":"item","numeric-id":3455560,"id":"Q3455560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$E84481A4-A6EE-4926-94A1-1EFADF73E524","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29c30f9f448fb1fd75a320e8b96473cbce649725","datavalue":{"value":{"entity-type":"item","numeric-id":3579215,"id":"Q3579215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$B020B1F2-B3F1-49AB-BC31-FCC34D8002E8","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":"Q5090435$D7457EBE-6375-47B5-B485-3A8D8E7E8B2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a015c2b0b90472359eabf001a5b9af2d64ab6f12","datavalue":{"value":{"entity-type":"item","numeric-id":496301,"id":"Q496301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$D0247D7D-80D9-442A-9188-6951C7EDE523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9194e9b150f8488fef979658da21ddd0e60751fc","datavalue":{"value":{"entity-type":"item","numeric-id":3651735,"id":"Q3651735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$CD03FA8A-23E3-4B6B-BD3F-BB512FB82AD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee27ff857d991d6b3f8e75bf9b44517be8c42b24","datavalue":{"value":{"entity-type":"item","numeric-id":5896979,"id":"Q5896979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$CD2891F9-2479-431B-B5B6-ADE80BA9EAAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8be9dbfaaad9151faf5c5db0312c48c62ecd9dc2","datavalue":{"value":{"entity-type":"item","numeric-id":3455209,"id":"Q3455209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$B7BBAD7E-9AAE-4239-BED9-4AD69EB295AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47a6cab000a8620ee751c1c3c2333e16e8513bfb","datavalue":{"value":{"entity-type":"item","numeric-id":4302285,"id":"Q4302285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$7F7C7AE9-3F56-49E3-A630-BE994679826C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a14259755a9136b7b26201f5111f10df5b52f768","datavalue":{"value":{"entity-type":"item","numeric-id":4109299,"id":"Q4109299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$8A054CD7-8C44-4658-AA74-E904384D153D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"464796b3d7fe846d1db7baf0e2ae3ec55ec86321","datavalue":{"value":{"entity-type":"item","numeric-id":1208411,"id":"Q1208411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$191B9247-9A96-4DF2-94E1-47C674538D29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"634a72bd59e8a666b5945fde9369e940396445b0","datavalue":{"value":{"entity-type":"item","numeric-id":3594440,"id":"Q3594440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$3471E28A-9755-4FF1-808A-C43E1EAC7C74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0272da4ea39681ecf8b28e766cd053edfc72ba63","datavalue":{"value":{"entity-type":"item","numeric-id":1603493,"id":"Q1603493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$73B35564-B83A-4FF4-9102-335F8D7FCEFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6799f10c75d08391d77d9ac7ef080e9fb4530e4","datavalue":{"value":{"entity-type":"item","numeric-id":3581269,"id":"Q3581269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$93174BC3-D1AF-403B-881C-51778F63FECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe5cc7dcd0e75dbddea1dd510a0befa7dc03094e","datavalue":{"value":{"entity-type":"item","numeric-id":3587579,"id":"Q3587579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$A5C3A0DB-DE38-4A3C-9BE9-7EE8F774860F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94c794b8411f92b6cbaefc2d439218ae5944c5aa","datavalue":{"value":{"entity-type":"item","numeric-id":937201,"id":"Q937201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$12333538-2005-4B24-B92F-9715B1ED6EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc9295637fd4e359fc8e65c1b474446e900dfad6","datavalue":{"value":{"entity-type":"item","numeric-id":3189637,"id":"Q3189637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$2A10F153-CC84-4D9D-95C2-2AF6E28A71FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c731fd97fc54301a48fb801be9df90976d0215da","datavalue":{"value":{"entity-type":"item","numeric-id":1065546,"id":"Q1065546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5090435$A969B4A5-C3B3-4058-86C4-DE6DBCCFC387","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fefb00bd178755c8410ce5fec61dc6cf3b304e56","datavalue":{"value":"https://doi.org/10.4230/LIPIcs.ITCS.2019.56","type":"string"},"datatype":"url"},"type":"statement","id":"Q5090435$22615988-C8A7-461A-9E99-5DEF89D18BA0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b5004e7c31b1cba15a639aa42708d6f926e752c7","datavalue":{"value":"W2912512664","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5090435$32B3EAFC-C71A-45DF-BAC6-F6D839288756","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"486c1b7aa1ca0646bf7cbfccd64a8fcbe37814a2","datavalue":{"value":{"text":"Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5090435$CA98CB1E-9C70-4D0B-BF11-4624F61B1ADF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b601ea8932e5b00225d046932abb390375b05e2d","datavalue":{"value":"10.4230/LIPICS.ITCS.2019.56","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5090435$6728A35C-1547-41D3-8E2D-760808FDA949","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1ab36b0d11475917bd6c9eb5d7282cc4a9488b4","datavalue":{"value":{"entity-type":"item","numeric-id":3455560,"id":"Q3455560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"575f631ca8b8cc5af1792b0026b57b57baf773f1","datavalue":{"value":{"amount":"+0.8050627708435059","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":"Q5090435$2B0F12BF-704F-4F5C-9FD4-E8FD9C02253F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba06b8090e102dee3dff66c6a706a8072e7873cb","datavalue":{"value":{"entity-type":"item","numeric-id":3446808,"id":"Q3446808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"932844a9556c2572bff537d02653aa40d88ac8c9","datavalue":{"value":{"amount":"+0.7626886367797852","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":"Q5090435$ADDEC19F-A7C9-40B5-A067-8828C83ABF04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"098e82279a3a4eff6630fc88764173d1d09a44df","datavalue":{"value":{"entity-type":"item","numeric-id":1604208,"id":"Q1604208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5f0af07d2ed30ff5bc5cd99b9f2d95d2024a1db","datavalue":{"value":{"amount":"+0.7598781585693359","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":"Q5090435$4F913FD5-1CE1-4E36-BAA2-4FC653407AE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"143f83e82906f59c7836778facb8332060f8ebdd","datavalue":{"value":{"entity-type":"item","numeric-id":2729236,"id":"Q2729236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24dc45ff347e6936f628d28635380dbe3755bc63","datavalue":{"value":{"amount":"+0.7540615797042847","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":"Q5090435$4B5673F8-8246-45EC-BB9C-B9016104BF1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f403df34ec278f1523a8eca7923b9e4f4ab8cb5e","datavalue":{"value":{"entity-type":"item","numeric-id":5716845,"id":"Q5716845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef5c3a372766a56cbbf9c0c9265b8d377010c812","datavalue":{"value":{"amount":"+0.7526700496673584","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":"Q5090435$86F38D79-C22C-4509-A26D-8756BA1DA6A4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5090435","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5090435"}}}}}