Bi-Lipschitz bijection between the Boolean cube and the Hamming ball

DOI10.1007/s11856-016-1302-0zbMath1341.05012arXiv1310.2017OpenAlexW2406726738MaRDI QIDQ2630133

Itai Benjamini, Igor Shinkar, Gil Cohen

Publication date: 25 July 2016

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityBoolean circuits

Mathematics Subject Classification ID

Combinatorial identities, bijective combinatorics (05A19) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On the failure of concentration for the \(\ell_\infty\)-ball ⋮ On mappings on the hypercube with small average stretch ⋮ Lipschitz bijections between boolean functions ⋮ Unnamed Item ⋮ On Lipschitz Bijections Between Boolean Functions ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The average sensitivity of bounded-depth circuits
• Bounded-depth circuits cannot sample good codes
• Geometric properties of Poisson matchings
• A phase transition for the metric distortion of percolation on the hypercube
• A note on the edges of the n-cube
• Boolean functions with low average sensitivity depend on few coordinates
• The Complexity of Distributions
• Log Space Recognition and Translation of Parenthesis Languages
• Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
• On the Implementation of Huge Random Objects
• Extractors for Circuit Sources
• Optimal numberings and isoperimetric problems on graphs