Fourier analysis for probabilistic communication complexity

DOI10.1007/BF01206318zbMath0851.68045MaRDI QIDQ1918947

Ran Raz

Publication date: 10 November 1996

Published in: Computational Complexity (Search for Journal in Brave)

zbMATH Keywords

Fourier analysisprobabilistic communication complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of computing (68Q99)

Related Items (11)

Bounds on the Fourier coefficients of the weighted sum function ⋮ The unbounded-error communication complexity of symmetric functions ⋮ The NOF multiparty communication complexity of composed functions ⋮ Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality ⋮ Kolmogorov complexity and combinatorial methods in communication complexity ⋮ Lifting Theorems for Equality ⋮ Lower bounds in communication complexity based on factorization norms ⋮ Concentration on the Boolean hypercube via pathwise stochastic analysis ⋮ Quantum communication and complexity. ⋮ Quantum versus randomized communication complexity, with efficient players ⋮ Circuit and decision tree complexity of some number theoretic problems

Cites Work

• On the distributional complexity of disjointness
• Inequalities in Fourier analysis
• The Probabilistic Communication Complexity of Set Intersection
• Unnamed Item
• Unnamed Item

This page was built for publication: Fourier analysis for probabilistic communication complexity