{"entities":{"Q1659336":{"pageid":1670077,"ns":120,"title":"Item:Q1659336","lastrevid":57425217,"modified":"2026-03-30T21:43:50Z","type":"item","id":"Q1659336","labels":{"en":{"language":"en","value":"Structure theory of flip graphs with applications to weak symmetry breaking"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6918480"}},"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":"Q1659336$BD475B60-10E7-4356-925A-496BF0CC4EC1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c655d630fc659ab067f3b34bfe139424bd7b19ea","datavalue":{"value":{"text":"Structure theory of flip graphs with applications to weak symmetry breaking","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1659336$77E06CF5-2AD5-4816-BB22-48E296113D2E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"11e51cbd06cc23bd4ad2623377457314a4d5601e","datavalue":{"value":"1400.68157","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1659336$F6DD3AC7-D3C9-4178-AAD8-3328423157A3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fbe52a955fe87ebf7724ee2cb9164de8d0f8099b","datavalue":{"value":{"entity-type":"item","numeric-id":215085,"id":"Q215085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$C9652EAC-A6F7-464E-BBEF-1E9A00CBB2A8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"beb416faced81cecea274fa4bf7248d0a36a68d7","datavalue":{"value":{"entity-type":"item","numeric-id":141942,"id":"Q141942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$B3BE8E78-7B75-4621-950C-459E1375574B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"db9626bb787427167dc8802eb63a193ac3c35362","datavalue":{"value":{"time":"+2018-08-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1659336$310C31E2-8079-432E-9D06-6E62B49295A7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"be3371dd72e144624a4889e1a5879db247fb3ea2","datavalue":{"value":"https://arxiv.org/abs/1511.00457","type":"string"},"datatype":"url"},"type":"statement","id":"Q1659336$3AEFA9D3-FD9F-46D0-8CD5-F62D9E7D3252","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c8c9bafa6632de7cb7e4269c78fe1120f923f729","datavalue":{"value":"This paper is devoted to advancing the theoretical understanding of the iterated immediate snapshot (IIS) complexity of the Weak Symmetry Breaking task (WSB). The WSB for \\(n\\) processes is an inputless task with possible outputs \\(0\\) and \\(1\\). A distributed protocol is said to solve the WSB if in any execution without failed processes, there exists at least one process with has value \\(0\\) as well as at least one process which has value \\(1\\). WSB for \\(n\\) processes is equivalent to the Hard \\((2n-2)\\)-Renaming task, providing one of the main reasons to study its solvability and its complexity. The main theorem states that there exist infinitely many values of \\(n\\), such that WSB for \\(n\\) processes is solvable by a certain explicitly constructed \\(3\\)-round IIS protocol. In particular, the minimal number of rounds, which an IIS protocol needs in order to solve the WSB task, does not go to infinity, when the number of processes goes to infinity. The methods can also be used to generate such values of \\(n\\). The proofs are phrased in combinatorial language, the central notion is the notion of flip graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1659336$467F6903-5351-4049-A769-85EB00C561D2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b83d2f7098073ec0ce332f8e7bca96a6bda9b9ca","datavalue":{"value":{"entity-type":"item","numeric-id":589562,"id":"Q589562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$A9EFCA01-EF74-4EC2-987B-3640E8D37DA8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1659336$962DB50D-C582-408E-B3AF-497C9C0EE595","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e669b60521e14398c1f2263792cea32c3a9da254","datavalue":{"value":"05E45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1659336$52EFF274-FF15-47FB-81BC-F2975BF298BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1722e8eaf8d0b6e989e3d4620a85df21f8eb2337","datavalue":{"value":"55U10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1659336$FC6409E5-FD21-4E78-9E39-7AAFDD63F6BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b8f412c62952107f7ff74e77578c2ab25d3e121a","datavalue":{"value":"68Q85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1659336$D3A36E10-C731-424A-9D3D-05293386864F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5008b52176bbef78cca1d57ce3456fdd697cda61","datavalue":{"value":"6918480","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1659336$7C8F4E03-B405-45E9-BE02-7E2901C01B37","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b36d924addd0d2f364b26835d91730b673a9f92","datavalue":{"value":"distributed computing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1659336$F3D3703C-12A7-48CA-95FA-EAD47FE6EDBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"003ddb75181b6c2c93d6847953c1917237d4d7e0","datavalue":{"value":"combinatorial algebraic topology","type":"string"},"datatype":"string"},"type":"statement","id":"Q1659336$0BB544D7-8ECB-44A6-93D8-1138F30D82A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a4efa8053f4dc69b95d92f2f7a4cce088207607","datavalue":{"value":"immediate snapshots","type":"string"},"datatype":"string"},"type":"statement","id":"Q1659336$0B600CF8-D45C-4998-9F7F-0BDDCBF64EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa36941144e04250bb12f93a0e4a002c7b864604","datavalue":{"value":"protocol complexes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1659336$CF0503B2-54E2-4647-B0FA-AD5B12100901","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1459f0fd455ff772aa5821c023e2a73b9508e85","datavalue":{"value":"weak symmetry breaking","type":"string"},"datatype":"string"},"type":"statement","id":"Q1659336$56FFD140-B9B0-4537-AEFB-F5F44D99AD1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"866ef3f0d9549a87fe4df7257d5f4790011b55a0","datavalue":{"value":"chromatic subdivision","type":"string"},"datatype":"string"},"type":"statement","id":"Q1659336$3DAAFC3F-D7BB-4407-8273-4059193996A2","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":"Q1659336$334C5BF3-D689-441C-9DC1-A9BE16040C06","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5205f90e791dea0d70e0511e844be2833932de16","datavalue":{"value":"W2963220706","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1659336$197B6B6B-D0BB-48BE-9DBE-46041F369A68","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab4b1ad1bb0a35486f435727254efc829c0824ed","datavalue":{"value":{"entity-type":"item","numeric-id":5740661,"id":"Q5740661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$963ECFCA-A180-4B1B-8608-5DF427BA821E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddab9f18a5ba28068f6f64f55265e7761f65fe73","datavalue":{"value":{"entity-type":"item","numeric-id":5176094,"id":"Q5176094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$4A79A8AB-5A82-4BD7-8B78-7162E553DE41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"324462dcce0b1328049179001adb4bbae472ba72","datavalue":{"value":{"entity-type":"item","numeric-id":4909423,"id":"Q4909423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$2ED03BB2-3E64-4A18-8D1E-04200B5F5C8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0bf3a80fdb21f79885f9c2d79abe3e0259e1947","datavalue":{"value":{"entity-type":"item","numeric-id":4398822,"id":"Q4398822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$E89C7079-8866-4048-A678-B7C73FDB58F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e00ee617c134a09a8798b947d1b3421057a1f99","datavalue":{"value":{"entity-type":"item","numeric-id":2802937,"id":"Q2802937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$AC78C4FC-9929-4995-A377-DFA94BB14643","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4245ea564cd3b6c0d0e92107206c02dccb350ad8","datavalue":{"value":{"entity-type":"item","numeric-id":5365157,"id":"Q5365157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$CDF0877D-C297-44A4-B017-43ACB6DD99A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e94f0172fe47454a309e1531d8b6602ec11115c4","datavalue":{"value":{"entity-type":"item","numeric-id":5361482,"id":"Q5361482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$52388536-4C3E-4C33-A3E7-99AA0B7FB01C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b07346cd4b38550a907b0c5232bb85b9c35d7f8","datavalue":{"value":{"entity-type":"item","numeric-id":2934354,"id":"Q2934354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$1AD32565-02DC-49EA-A7E4-12B1FCE8B7FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"567d22c9f85c0590531db09823924c49f6ed6873","datavalue":{"value":{"entity-type":"item","numeric-id":992504,"id":"Q992504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$FB016DAA-8D99-4EE9-9077-1C33C05095C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5dc359db6423918db7346a8c5d3289fdb35f0dd","datavalue":{"value":{"entity-type":"item","numeric-id":5395676,"id":"Q5395676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$C2F20B07-E191-45CF-A1A7-4ACEEEB89202","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cd9c4a403d37feb7083da3269440252f84c001b","datavalue":{"value":{"entity-type":"item","numeric-id":5498755,"id":"Q5498755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$3EA521B4-D51D-46DC-856C-E59D211BEDFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53c2bf518f07c352a8e3930c7ca19270bad30af8","datavalue":{"value":{"entity-type":"item","numeric-id":3158560,"id":"Q3158560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$52F6DA8A-88A6-4945-9983-EFBDDA7706C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf05925c161b50902a475d27429912f455994b38","datavalue":{"value":{"entity-type":"item","numeric-id":5919887,"id":"Q5919887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$D548BAD2-B59E-4A52-9835-FA25C018A5B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"130a19e6474321079cd0128f985f47f42c1dff1a","datavalue":{"value":{"entity-type":"item","numeric-id":1935105,"id":"Q1935105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$9D0F001F-0A47-4D72-8208-ABFF118318BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26ee45283c40c2864d6318bfd00a0583d4f6f2ba","datavalue":{"value":{"entity-type":"item","numeric-id":471457,"id":"Q471457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$100F06F7-980C-4901-8A62-F22118E2AC2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94e994e7ca55c3ce2ab5b583a8087293feb6950b","datavalue":{"value":{"entity-type":"item","numeric-id":4560213,"id":"Q4560213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$FC6C6603-FD5E-4D82-9961-53DDC9422C34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80ef49cfffc303a05e8d663ad48140e16cc34c48","datavalue":{"value":{"entity-type":"item","numeric-id":2354983,"id":"Q2354983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$8EB8490F-2B7A-43B0-A07C-FE1B062DE2CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9257131300c5f521b03618c819eaa9f0886173f5","datavalue":{"value":{"entity-type":"item","numeric-id":4608477,"id":"Q4608477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$829FDAB9-465A-49C9-B69F-E9EAE55964D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3308c7fb8e62d2428d37f80c5597dfc0bd7c1853","datavalue":{"value":{"entity-type":"item","numeric-id":730270,"id":"Q730270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1659336$84E32965-FE27-47FC-9CB4-F6BC6EC0D59A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"705879d5319ac4d79ea350fbbc626d4d98834eab","datavalue":{"value":"10.1007/S41468-017-0001-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1659336$BEA8BB34-4101-484B-8B4A-C3C69B246280","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41565933a09c9b08924dd7452410f36d610e3569","datavalue":{"value":{"entity-type":"item","numeric-id":5740661,"id":"Q5740661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00980941fdaae8efe9b0735ab18726098f38f7eb","datavalue":{"value":{"amount":"+0.7983964681625366","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":"Q1659336$B40D1EFF-1538-4951-9471-2CDBEF28867B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8243de21d55ea534ba6d959882457550810561ad","datavalue":{"value":{"entity-type":"item","numeric-id":4608477,"id":"Q4608477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"580ba38d0a8f6468bba5afe72e5f0392a45342fe","datavalue":{"value":{"amount":"+0.7926545143127441","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":"Q1659336$754AAE20-F307-4DF6-86E5-11AA21C8A946","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2a48c87e04d388aaf56d2d4a714471f4e5fbbda","datavalue":{"value":{"entity-type":"item","numeric-id":5179018,"id":"Q5179018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d608f9f99ab895954774d6ab5c89405b711ace0f","datavalue":{"value":{"amount":"+0.770934522151947","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":"Q1659336$5B0BB995-4356-4BC4-B154-6583511E8BFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f10cb28e12f465a6a27d780e0e5c5a6e8367de2","datavalue":{"value":{"entity-type":"item","numeric-id":3149868,"id":"Q3149868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb8903e8ead1a9c1e40a610119cb890ccceecbc9","datavalue":{"value":{"amount":"+0.7414658665657043","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":"Q1659336$3C178EAD-6CE6-4E72-A0E9-536E66F0088A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"428f859414f4434b190f09793d8761212aadf745","datavalue":{"value":{"entity-type":"item","numeric-id":2802146,"id":"Q2802146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"251ee22444f72590993434bd5083820e412f4ecb","datavalue":{"value":{"amount":"+0.7381052374839783","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":"Q1659336$F28EEEBD-E8F8-499F-B0CD-D18FC907F94D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1659336","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1659336"}}}}}