Anticoncentration and the Exact Gap-Hamming Problem

DOI10.1137/21M1435288MaRDI QIDQ5074948

Amir Yehudayoff, Anup Rao

Publication date: 10 May 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

probabilitycommunication complexityanticoncentration

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Summenmengen in lokalkompakten abelschen Gruppen
• Solution of the Littlewood-Offord problem in high dimensions
• Concentration of measure and isoperimetric inequalities in product spaces
• Singularity of discrete random matrices
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• A near-optimal algorithm for estimating the entropy of a stream
• A sharp inverse Littlewood-Offord theorem
• Better Gap-Hamming Lower Bounds via Better Round Elimination
• Weyl Groups, the Hard Lefschetz Theorem, and the Sperner Property
• Estimates for the concentration function of combinatorial number theory and probability
• On the Probability That a Random ± 1-Matrix Is Singular
• Communication Complexity
• An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
• Communication Complexity
• On products of sets in a locally compact group
• Über ein Problem von Erdös und Moser
• The computational complexity of linear optics
• On a Problem of Sidon in Additive Number Theory, and on some Related Problems
• On a lemma of Littlewood and Offord