The unbounded-error communication complexity of symmetric functions

DOI10.1007/s00493-011-2580-0zbMath1265.03035OpenAlexW1965748471MaRDI QIDQ2428632

Alexander A. Sherstov

Publication date: 26 April 2012

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-011-2580-0

zbMATH Keywords

symmetric functionsunbounded-error communication complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

The landscape of communication complexity classes ⋮ A Short List of Equalities Induces Large Sign-Rank ⋮ On the Power of Statistical Zero Knowledge ⋮ Optimal bounds for sign-representing the intersection of two halfspaces by polynomials ⋮ Unnamed Item ⋮ Rectangles Are Nonnegative Juntas ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ A Lifting Theorem with Applications to Symmetric Functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic communication complexity
• An information statistics approach to data stream and communication complexity
• On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes
• Powering requires threshold depth 3
• Halfspace matrices
• Unconditional lower bounds for learning intersections of halfspaces
• Private vs. common random bits in communication complexity
• On the distributional complexity of disjointness
• Majority gates vs. general weighted threshold gates
• Improved lower bounds on the rigidity of Hadamard matrices
• The expressive power of voting polynomials
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• A linear lower bound on the unbounded error probabilistic communication complexity.
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Fourier analysis for probabilistic communication complexity
• Threshold circuits of bounded depth
• Cryptographic hardness for learning intersections of halfspaces
• Separating ${AC}^0$ from Depth-2 Majority Circuits
• A theory of the learnable
• The Probabilistic Communication Complexity of Set Intersection
• Cryptographic limitations on learning Boolean formulae and finite automata
• Quantum communication complexity of symmetric predicates
• Communication Complexity
• Cryptographic hardness of distribution-specific learning
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• A Lower Bound for Agnostically Learning Disjunctions

This page was built for publication: The unbounded-error communication complexity of symmetric functions