{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,11,11]],"date-time":"2022-11-11T07:50:45Z","timestamp":1668153045045},"reference-count":17,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2020,11,16]],"date-time":"2020-11-16T00:00:00Z","timestamp":1605484800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,7]]},"abstract":"Abstract<\/jats:title>We answer four questions from a recent paper of Rao and Shinkar [17] on Lipschitz bijections between functions from {0, 1}n<\/jats:italic><\/jats:sup> to {0, 1}. (1) We show that there is no O<\/jats:italic>(1)-bi-Lipschitz bijection from Dictator to XOR such that each output bit depends on O<\/jats:italic>(1) input bits. (2) We give a construction for a mapping from XOR to Majority which has average stretch \n$O(\\sqrt{n})$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, matching a previously known lower bound. (3) We give a 3-Lipschitz embedding \n$\\phi \\colon \\{0,1\\}^n \\to \\{0,1\\}^{2n+1}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> such that \n$${\\rm{XOR }}(x) = {\\rm{ Majority }}(\\phi (x))$$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for all \n$x \\in \\{0,1\\}^n$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. (4) We show that with high probability there is an O<\/jats:italic>(1)-bi-Lipschitz mapping from Dictator to a uniformly random balanced function.<\/jats:p>","DOI":"10.1017\/s0963548320000541","type":"journal-article","created":{"date-parts":[[2020,11,16]],"date-time":"2020-11-16T10:21:37Z","timestamp":1605522097000},"page":"513-525","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":2,"title":["Lipschitz bijections between boolean functions"],"prefix":"10.1017","volume":"30","author":[{"given":"Tom","family":"Johnston","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex","family":"Scott","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,11,16]]},"reference":[{"key":"S0963548320000541_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00131-2"},{"key":"S0963548320000541_ref16","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2010.171.295"},{"key":"S0963548320000541_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-018-1646-8"},{"key":"S0963548320000541_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02698830"},{"key":"S0963548320000541_ref5","unstructured":"[5] Boczkowski, L. and Shinkar, I. (2019) On mappings on the hypercube with small average stretch. arXiv:1905.11350"},{"key":"S0963548320000541_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603"},{"key":"S0963548320000541_ref4","first-page":"228","article-title":"Mathematical techniques for the analysis of boolean functions","volume":"65","author":"Bernasconi","year":"1998","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"key":"S0963548320000541_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02785861"},{"key":"S0963548320000541_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-016-1302-0"},{"key":"S0963548320000541_ref6","volume-title":"Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability","author":"Bollob\u00e1s","year":"1986"},{"key":"S0963548320000541_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28425"},{"key":"S0963548320000541_ref10","first-page":"455","article-title":"On random matrices","volume":"8","author":"Erd\u0151s","year":"1963","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl"},{"key":"S0963548320000541_ref14","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.11"},{"key":"S0963548320000541_ref12","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21923"},{"key":"S0963548320000541_ref1","first-page":"91","article-title":"Collective coin flipping","volume":"5","author":"Ben-Or","year":"1989","journal-title":"Adv. Comput. Research"},{"key":"S0963548320000541_ref9","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.439"},{"key":"S0963548320000541_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548317000578"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000541","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,10]],"date-time":"2021-06-10T14:35:07Z","timestamp":1623335707000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000541\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,16]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["S0963548320000541"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000541","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,16]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}