Fourier analysis for probabilistic communication complexity

Ran Raz

doi:10.1007/BF01206318

Fourier analysis for probabilistic communication complexity

Ran Raz

Computer Science

Research output: Contribution to journal › Article › peer-review

38 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 language	English (US)
Pages (from-to)	205-221
Number of pages	17
Journal	Computational Complexity
Volume	5
Issue number	3-4
DOIs	https://doi.org/10.1007/BF01206318
State	Published - 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

Access to Document

10.1007/BF01206318

Cite this

@article{dcc08df22f9c463797d071cf506d6565,

title = "Fourier analysis for probabilistic communication complexity",

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.",

keywords = "Fourier analysis, Lower-bound, Subject classifications: 68Q25, 68Q99, complexity",

author = "Ran Raz",

year = "1995",

month = sep,

day = "1",

doi = "10.1007/BF01206318",

language = "English (US)",

volume = "5",

pages = "205--221",

journal = "Computational Complexity",

issn = "1016-3328",

publisher = "Birkhauser Verlag Basel",

number = "3-4",

}

TY - JOUR

T1 - Fourier analysis for probabilistic communication complexity

AU - Raz, Ran

PY - 1995/9/1

Y1 - 1995/9/1

N2 - 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.

AB - 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.

KW - Fourier analysis

KW - Lower-bound

KW - Subject classifications: 68Q25, 68Q99

KW - complexity

UR - http://www.scopus.com/inward/record.url?scp=21344441171&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21344441171&partnerID=8YFLogxK

U2 - 10.1007/BF01206318

DO - 10.1007/BF01206318

M3 - Article

AN - SCOPUS:21344441171

SN - 1016-3328

VL - 5

SP - 205

EP - 221

JO - Computational Complexity

JF - Computational Complexity

IS - 3-4

ER -

Fourier analysis for probabilistic communication complexity

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this