The unbounded-error communication complexity of symmetric functions
From MaRDI portal
The paper proves that the unbounded-error communication complexity of every symmetric function \(f(x,y) = D(| x \wedge y| )\), where \(D\) is a predicate on \(\{0,1,,\cdots ,n\}\) and \(x,y \in \{0,1\}^{n}\), is between \(\theta (k/log^{5} n)\) and \(\theta (k log n)\), where \(k\) is the number of value changes of D in \(\{0,1,\dots ,n\}\).
Recommendations
- Communication complexities of symmetric XOR functions
- Tight bounds on communication complexity of symmetric XOR functions in one-way and SMP models
- On multiparty communication with large versus unbounded error
- Probabilistic communication complexity
- Lower bounds to the complexity of symmetric Boolean functions
Cites work
- A linear lower bound on the unbounded error probabilistic communication complexity.
- A Lower Bound for Agnostically Learning Disjunctions
- A theory of the learnable
- An information statistics approach to data stream and communication complexity
- Communication Complexity
- Cryptographic hardness for learning intersections of halfspaces
- Cryptographic hardness of distribution-specific learning
- Cryptographic limitations on learning Boolean formulae and finite automata
- Fourier analysis for probabilistic communication complexity
- Halfspace matrices
- scientific article; zbMATH DE number 5568623 (Why is no real title available?)
- scientific article; zbMATH DE number 1324671 (Why is no real title available?)
- scientific article; zbMATH DE number 524134 (Why is no real title available?)
- scientific article; zbMATH DE number 2081103 (Why is no real title available?)
- scientific article; zbMATH DE number 3314813 (Why is no real title available?)
- Improved lower bounds on the rigidity of Hadamard matrices
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- Majority gates vs. general weighted threshold gates
- On the distributional complexity of disjointness
- On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes
- Powering requires threshold depth 3
- Private vs. common random bits in communication complexity
- Probabilistic communication complexity
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- Quantum communication complexity of symmetric predicates
- Separating AC\(^0\) from depth-2 majority circuits
- Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
- The expressive power of voting polynomials
- The Probabilistic Communication Complexity of Set Intersection
- Threshold circuits of bounded depth
- Unconditional lower bounds for learning intersections of halfspaces
Cited in
(14)- Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC
- Communication errors in the \(\pi\)-calculus are undecidable
- The landscape of communication complexity classes
- Computing unrestricted synopses under maximum error bound
- Tight bounds on communication complexity of symmetric XOR functions in one-way and SMP models
- Communication complexities of symmetric XOR functions
- On multiparty communication with large versus unbounded error
- Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
- A short list of equalities induces large sign-rank
- Sign-rank can increase under intersection
- On the power of statistical zero knowledge
- A lifting theorem with applications to symmetric functions
- Rectangles are nonnegative juntas
- A hierarchy of constant communication complexity
This page was built for publication: The unbounded-error communication complexity of symmetric functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2428632)
