Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-194 | 28th November 2018 01:37

Anti-concentration in most directions

RSS-Feed




Revision #1
Authors: Amir Yehudayoff
Accepted on: 28th November 2018 01:37
Downloads: 31
Keywords: 


Abstract:

We prove anti-concentration for the inner product of two independent random vectors in the discrete cube. Our results imply Chakrabarti and Regev's lower bound on the randomized communication complexity of the gap-hamming problem. They are also meaningful in the context of randomness extraction. The proof provides a framework for establishing anti-concentration in discrete domains. The argument has two different components. A local component that uses harmonic analysis, and a global ("information theoretic") component.



Changes to previous version:

Conversations with Anup Rao lead to a sharp bound with a simpler proof. Some calculations from the previous version may be useful elsewhere.


Paper:

TR18-194 | 15th November 2018 20:15

Anti-concentration in most directions





TR18-194
Authors: Amir Yehudayoff
Publication: 18th November 2018 18:01
Downloads: 158
Keywords: 


Abstract:

We prove anti-concentration for the inner product of two independent random vectors in the discrete cube. Our results imply Chakrabarti and Regev's lower bound on the randomized communication complexity of the gap-hamming problem. They are also meaningful in the context of randomness extraction. The proof provides a framework for establishing anti-concentration in discrete domains. The argument has two different components. A local component that uses harmonic analysis, and a global ("information theoretic") component.



ISSN 1433-8092 | Imprint