Abstract
We use Fourier analysis to get general lower bounds for the probabilistic communication complexity of large classes of functions. We give some examples showing how to use our method in some known cases and for some new functions. Our main tool is an inequality by Kahn, Kalai, and Linial, derived from two lemmas of Beckner.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 205-221 |
| Number of pages | 17 |
| Journal | Computational Complexity |
| Volume | 5 |
| Issue number | 3-4 |
| DOIs | |
| State | Published - Sep 1995 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- General Mathematics
- Computational Theory and Mathematics
- Computational Mathematics
Keywords
- Fourier analysis
- Lower-bound
- Subject classifications: 68Q25, 68Q99
- complexity