A Borsuk-Ulam lower bound for sign-rank and its applications
From MaRDI portal
Publication:6499244
DOI10.1145/3564246.3585210MaRDI QIDQ6499244
Kaave Hosseini, Unnamed Author, Hamed Hatami
Publication date: 8 May 2024
discrepancyrandomized communication complexityunbounded-error communication complexitysign-rankmargin complexitydimension complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Probabilistic communication complexity
- Semi-algebraic Ramsey numbers
- Halfspace matrices
- Complexity measures of sign matrices
- Unconditional lower bounds for learning intersections of halfspaces
- Private vs. common random bits in communication complexity
- A linear lower bound on the unbounded error probabilistic communication complexity.
- On the distortion required for embedding finite metric spaces into normed spaces
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- An algorithmic theory of learning: Robust concepts and random projection
- A semi-algebraic version of Zarankiewicz's problem
- The Sign-Rank of AC$^0$
- Overlap properties of geometric expanders
- METRIC DIMENSION REDUCTION: A SNAPSHOT OF THE RIBE PROGRAM
- Learning Complexity vs Communication Complexity
- Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization
- Improved Bounds on the Sign-Rank of AC^0
- Lower bounds on geometric Ramsey functions
- 10.1162/153244303321897681
- Communication Complexity
- An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
- Equality alone does not simulate randomness
- Near-optimal lower bounds on the threshold degree and sign-rank of AC 0
- Learning Theory
- Understanding Machine Learning
- Covering a sphere with spheres
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
This page was built for publication: A Borsuk-Ulam lower bound for sign-rank and its applications
