The unbounded-error communication complexity of symmetric functions

DOI10.1007/s00493-011-2580-0zbMath1265.03035MaRDI 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 functions; unbounded-error communication complexity

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Unnamed Item, On the Power of Statistical Zero Knowledge, Optimal bounds for sign-representing the intersection of two halfspaces by polynomials, Rectangles Are Nonnegative Juntas, The landscape of communication complexity classes

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