A linear lower bound on the unbounded error probabilistic communication complexity.
From MaRDI portal
Publication:1872728
DOI10.1016/S0022-0000(02)00019-3zbMath1058.68058OpenAlexW2143355494MaRDI QIDQ1872728
Publication date: 14 May 2003
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(02)00019-3
Computational learning theory (68Q32) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (37)
Weights of exact threshold functions ⋮ The Paulsen problem made simple ⋮ Essential sign change numbers of full sign pattern matrices ⋮ A Quiver Invariant Theoretic Approach to Radial Isotropy and the Paulsen Problem for Matrix Frames ⋮ Approximate Degree in Classical and Quantum Computing ⋮ The landscape of communication complexity classes ⋮ Unnamed Item ⋮ Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization ⋮ Nearest neighbor representations of Boolean functions ⋮ Revealed preference dimension via matrix sign rank ⋮ Space lower bounds for low-stretch greedy embeddings ⋮ Linear algebraic methods in communication complexity ⋮ Unnamed Item ⋮ The unbounded-error communication complexity of symmetric functions ⋮ Unbounded-error quantum query complexity ⋮ Dimension-free bounds and structural results in communication complexity ⋮ Computing the Distance Between Frames and Between Subspaces of a Hilbert Space ⋮ Sign rank versus Vapnik-Chervonenkis dimension ⋮ On a theorem of Razborov ⋮ Unbounded-Error Classical and Quantum Communication Complexity ⋮ Using elimination theory to construct rigid matrices ⋮ Minimum (maximum) rank of sign pattern tensors and sign nonsingular tensors ⋮ Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling ⋮ Exponential lower bounds on the size of constant-depth threshold circuits with small energy complexity ⋮ Threshold circuit lower bounds on cryptographic functions ⋮ Ranks of dense alternating sign matrices and their sign patterns ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Minimum ranks of sign patterns and zero-nonzero patterns and point-hyperplane configurations ⋮ Polynomial threshold functions and Boolean threshold circuits ⋮ Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ ⋮ Rank conditions for sign patterns that allow diagonalizability ⋮ Rational realization of the minimum ranks of nonnegative sign pattern matrices ⋮ Spectral Analysis of Matrix Scaling and Operator Scaling ⋮ Sign patterns with minimum rank 2 and upper bounds on minimum ranks ⋮ Unnamed Item ⋮ IMPROVED RANK BOUNDS FOR DESIGN MATRICES AND A NEW PROOF OF KELLY’S THEOREM
Cites Work
- Probabilistic communication complexity
- Geometric arguments yield better bounds for threshold circuits and distributed computing
- Relative loss bounds for temporal-difference learning
- Learnability and the Vapnik-Chervonenkis dimension
- Matrix Analysis
- Communication Complexity
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A linear lower bound on the unbounded error probabilistic communication complexity.
