On Lipschitz bijections between Boolean functions

DOI10.1017/S0963548317000578MaRDI QIDQ4635511zbMATH OpenOpenAlexFDO

Publication date 23 April 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.03016

Boolean functions (06E30) Combinatorial probability (60C05) Combinatorics in computer science (68R05)

Abstract: For two functions

f, g : {0, 1}^{n} o 0, 1

a mapping

p s i : {0, 1}^{n} o {0, 1}^{n}

is said to be a

f

t o

g

if it is a bijection and

f (z) = g (p s i (z))

for every

z i n {0, 1}^{n}

. In this paper we study Lipschitz mappings between boolean functions. Our first result gives a construction of a

C

-Lipschitz mapping from the

s f M a j o r i t y

function to the

s f D i c t a t o r

function for some universal constant

C

. On the other hand, there is no

n / 2

-Lipschitz mapping in the other direction, namely from the

s f D i c t a t o r

function to the

s f M a j o r i t y

function. This answers an open problem posed by Daniel Varga in the paper of Benjamini et al. (FOCS 2014). We also show a mapping from

s f D i c t a t o r

to

s f X O R

that is 3-local, 2-Lipschitz, and its inverse is

O (l o g (n))

-Lipschitz, where by

L

-local mapping we mean that each of its output bits depends on at most

L

input bits. Next, we consider the problem of finding functions such that any mapping between them must have large emph{average stretch}, where the average stretch of a mapping

p h i

is defined as

s f a v g S t r e t c h (p h i) = {m a t h b b E}_{x, i} [d i s t (p h i (x), p h i (x + e_{i})]

. We show that any mapping

p h i

from

s f X O R

to

s f M a j o r i t y

must satisfy

s f a v g S t r e t c h (p h i) g e q O m e g a (s q r t n)

. In some sense, this gives a "function analogue" to the question of Benjamini et al. (FOCS 2014), who asked whether there exists a set

A s u b s e t {0, 1}^{n}

of density 0.5 such that any bijection from

{0, 1}^{n - 1}

to

A

has large average stretch. Finally, we show that for a random balanced function

f : {0, 1}^{n} o {0, 1}^{n}

with high probability there is a mapping

p h i

from

s f D i c t a t o r

to

f

such that both

p h i

and

p h i^{- 1}

have constant average stretch. In particular, this implies that one cannot obtain lower bounds on average stretch by taking uniformly random functions.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: On Lipschitz bijections between Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635511)