{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T09:50:15Z","timestamp":1666086615061},"reference-count":8,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2017,12,19]],"date-time":"2017-12-19T00:00:00Z","timestamp":1513641600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2018,5]]},"abstract":"<jats:p>Given two functions <jats:italic>f<\/jats:italic>,<jats:italic>g<\/jats:italic> : {0,1}<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup> \u2192 {0,1}, a mapping \u03c8 : {0,1}<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup> \u2192 {0,1}<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup> is said to be a <jats:italic>mapping from f to g<\/jats:italic> if it is a bijection and <jats:italic>f<\/jats:italic>(<jats:italic>z<\/jats:italic>) = <jats:italic>g<\/jats:italic>(\u03c8(<jats:italic>z<\/jats:italic>)) for every <jats:italic>z<\/jats:italic> \u2208 {0,1}<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup>. In this paper we study Lipschitz mappings between Boolean functions.<\/jats:p><jats:p>Our first result gives a construction of a <jats:italic>C<\/jats:italic>-Lipschitz mapping from the <jats:monospace>Majority<\/jats:monospace> function to the <jats:monospace>Dictator<\/jats:monospace> function for some universal constant <jats:italic>C<\/jats:italic>. On the other hand, there is no <jats:italic>n<\/jats:italic>\/2-Lipschitz mapping in the other direction, namely from the <jats:monospace>Dictator<\/jats:monospace> function to the <jats:monospace>Majority<\/jats:monospace> function. This answers an open problem posed by Daniel Varga in the paper of Benjamini, Cohen and Shinkar (<jats:italic>FOCS 2014<\/jats:italic> [1]).<\/jats:p><jats:p>We also show a mapping from <jats:monospace>Dictator<\/jats:monospace> to <jats:monospace>XOR<\/jats:monospace> that is 3-local, 2-Lipschitz, and its inverse is <jats:italic>O<\/jats:italic>(log(<jats:italic>n<\/jats:italic>))-Lipschitz, where by <jats:italic>L<\/jats:italic>-local mapping we mean that each output bit of the mapping depends on at most <jats:italic>L<\/jats:italic> input bits.<\/jats:p><jats:p>Next, we consider the problem of finding functions such that any mapping between them must have large <jats:italic>average stretch<\/jats:italic>, where the average stretch of a mapping \u03c6 is defined as\n<jats:disp-formula-group><jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548317000578_eqnU1\" \/><jats:tex-math>\n$${\\sf avgstretch}(\\phi) = {\\mathbb E}_{x,i}[{\\sf dist}(\\phi(x),\\phi(x+e_i)].$$\n<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:disp-formula-group>\nWe show that any mapping \u03c6 from <jats:monospace>XOR<\/jats:monospace> to <jats:monospace>Majority<\/jats:monospace> must satisfy <jats:monospace>avgStretch<\/jats:monospace>(\u03c6) \u2265 <jats:italic>c<\/jats:italic><jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548317000578_inline1\" \/><jats:tex-math>$\\sqrt{n}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for some absolute constant <jats:italic>c<\/jats:italic> &gt; 0. In some sense, this gives a \u2018function analogue\u2019 to the question of Benjamini, Cohen and Shinkar (<jats:italic>FOCS 2014<\/jats:italic> [1]), who asked whether there exists a set <jats:italic>A<\/jats:italic> \u2286 {0,1}<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup> of density 0.5 such that any bijection from {0,1}<jats:sup><jats:italic>n<\/jats:italic>\u22121<\/jats:sup> to <jats:italic>A<\/jats:italic> has large average stretch.<\/jats:p><jats:p>Finally, we show that for a random balanced function <jats:italic>f<\/jats:italic>: {0,1}<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup> \u2192 {0,1}<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup>, with high probability there is a mapping \u03c6 from <jats:monospace>Dictator<\/jats:monospace> to <jats:italic>f<\/jats:italic> such that both \u03c6 and \u03c6<jats:sup>\u22121<\/jats:sup> have constant average stretch. In particular, this implies that one cannot obtain lower bounds on average stretch by taking uniformly random functions.<\/jats:p>","DOI":"10.1017\/s0963548317000578","type":"journal-article","created":{"date-parts":[[2017,12,19]],"date-time":"2017-12-19T06:41:10Z","timestamp":1513665670000},"page":"411-426","source":"Crossref","is-referenced-by-count":3,"title":["On Lipschitz Bijections Between Boolean Functions"],"prefix":"10.1017","volume":"27","author":[{"given":"SHRAVAS","family":"RAO","sequence":"first","affiliation":[]},{"given":"IGOR","family":"SHINKAR","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2017,12,19]]},"reference":[{"key":"S0963548317000578_ref7","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2010.171.295"},{"key":"S0963548317000578_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0039-3"},{"key":"S0963548317000578_ref5","doi-asserted-by":"crossref","unstructured":"Kindler G. and O'Donnell R. (2012) Gaussian noise sensitivity and Fourier tails. In CCC 2012: 27th IEEE Conference on Computational Complexity, IEEE Computer Society, pp. 137\u2013147.","DOI":"10.1109\/CCC.2012.35"},{"key":"S0963548317000578_ref4","unstructured":"H\u00e5stad J. , Leighton T. and Newman M. (1987) Reconfiguring a hypercube in the presence of faults. In STOC 1987: 19th Annual ACM Symposium on Theory of Computing, pp. 274\u2013284."},{"key":"S0963548317000578_ref3","first-page":"191","article-title":"On the set of divisors of a number","volume":"23","author":"de Bruijn","year":"1951","journal-title":"Nieuw Arch. Wiskunde"},{"key":"S0963548317000578_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-016-1302-0"},{"key":"S0963548317000578_ref8","doi-asserted-by":"publisher","DOI":"10.1137\/100814998"},{"key":"S0963548317000578_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02785861"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548317000578","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,14]],"date-time":"2019-04-14T20:57:14Z","timestamp":1555275434000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548317000578\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,19]]},"references-count":8,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["S0963548317000578"],"URL":"https:\/\/doi.org\/10.1017\/s0963548317000578","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,19]]}}}