×

Lipschitz bijections between Boolean functions. (English) Zbl 1512.68181

Summary: We answer four questions from a recent paper of S. Rao and I. Shinkar [Comb. Probab. Comput. 27, No. 3, 411–426 (2018; Zbl 1392.68319)] on Lipschitz bijections between functions from \(\{0, 1\}^n\) to \(\{0, 1\}\). (1) We show that there is no \(O(1)\)-bi-Lipschitz bijection from Dictator to XOR such that each output bit depends on \(O(1)\) input bits. (2) We give a construction for a mapping from XOR to Majority which has average stretch \(O(\sqrt{n})\), matching a previously known lower bound. (3) We give a 3-Lipschitz embedding \(\phi \colon \{0,1\}^n \to \{0,1\}^{2n+1}\) such that \({\mathrm{XOR}}(x) = {\mathrm{Majority}}(\phi (x))\) for all \(x \in \{0,1\}^n\). (4) We show that with high probability there is an \(O(1)\)-bi-Lipschitz mapping from Dictator to a uniformly random balanced function.

MSC:

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

Citations:

Zbl 1392.68319

References:

[1] Ben-Or, M. and Linial, N. (1989) Collective coin flipping. Adv. Comput. Research591-115.
[2] Benjamini, I., Cohen, G. and Shinkar, I. (2016) Bi-Lipschitz bijection between the boolean cube and the Hamming ball. Israel J. Math.212677-703. · Zbl 1341.05012
[3] Benjamini, I., Kalai, G. and Schramm, O. (1999) Noise sensitivity of boolean functions and applications to percolation. Publ. Math. Inst. Hautes Études Sci.905-43. · Zbl 0986.60002
[4] Bernasconi, A. (1998) Mathematical techniques for the analysis of boolean functions. Bull. Eur. Assoc. Theor. Comput. Sci.65228-230.
[5] Boczkowski, L. and Shinkar, I. (2019) On mappings on the hypercube with small average stretch. arXiv:1905.11350
[6] Bollobás, B. (1986) Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability. Cambridge University Press. · Zbl 0595.05001
[7] Boppana, R. B. (1997) The average sensitivity of bounded-depth circuits. Inform. Process. Lett.63257-261. · Zbl 1337.68124
[8] Bourgain, J. (2002) On the distribution of the Fourier spectrum of boolean functions. Israel J. Math.131269-276. · Zbl 1021.43004
[9] Dinur, I. and Safra, S. (2005) On the hardness of approximating minimum vertex cover. Ann. of Math.162439-485. · Zbl 1084.68051
[10] Erdős, P. and Rényi, A. (1963) On random matrices. Magyar Tud. Akad. Mat. Kutató Int. Közl8455-461. · Zbl 0133.26003
[11] Hastad, J., Leighton, T. and Newman, M. (1987) Reconfiguring a hypercube in the presence of faults. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (STOC ’87), pp. 274-284. ACM.
[12] Kahn, J., Kalai, G. and Linial, N. (1988) The Influence of Variables on Boolean Functions. IEEE.
[13] Kindler, G., Kirshner, N. and O’Donnell, R. (2018) Gaussian noise sensitivity and Fourier tails. Israel J. Math.22571-109. · Zbl 1429.60038
[14] Lovett, S. and Viola, E. (2011) Bounded-depth circuits cannot sample good codes. In 26th Annual Conference on Computational Complexity (CCC 2011), pp. 243-251. IEEE. · Zbl 1282.68125
[15] Mitzenmacher, M. and Upfal, E. (2005) Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. · Zbl 1092.60001
[16] Mossel, E., O’Donnell, R. and Oleszkiewicz, K. (2010) Noise stability of functions with low influences: invariance and optimality. Ann. of Math.171295-341. · Zbl 1201.60031
[17] Rao, S. and Shinkar, I. (2018) On Lipschitz bijections between boolean functions. Combin. Probab. Comput.27411-426. · Zbl 1392.68319
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.