The unbounded-error communication complexity of symmetric functions
From MaRDI portal
Publication:2428632
DOI10.1007/s00493-011-2580-0zbMath1265.03035OpenAlexW1965748471MaRDI QIDQ2428632
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
Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (8)
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
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The unbounded-error communication complexity of symmetric functions
