Fourier analysis for probabilistic communication complexity

Research output: Contribution to journalArticlepeer-review

30 Scopus citations

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 languageEnglish (US)
Pages (from-to)205-221
Number of pages17
JournalComputational Complexity
Volume5
Issue number3-4
DOIs
StatePublished - Sep 1 1995

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics
  • Computational Mathematics

Keywords

  • Fourier analysis
  • Lower-bound
  • Subject classifications: 68Q25, 68Q99
  • complexity

Fingerprint Dive into the research topics of 'Fourier analysis for probabilistic communication complexity'. Together they form a unique fingerprint.

Cite this