Sign rank vs discrepancy
From MaRDI portal
Publication:5092468
DOI10.4230/LIPIcs.CCC.2020.18OpenAlexW3046506586MaRDI QIDQ5092468
Kaave Hosseini, Shachar Lovett, Hamed Hatami
Publication date: 21 July 2022
Full work available at URL: https://doi.org/10.4230/lipics.ccc.2020.18
discrepancysign rankunbounded-error communication complexityweakly unbounded error communication complexity
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Probabilistic communication complexity
- Halfspace matrices
- Complexity measures of sign matrices
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- The Sign-Rank of AC$^0$
- The Pattern Matrix Method
- Simultaneous Approximation of Constraint Satisfaction Problems
- Learning Complexity vs Communication Complexity
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Improved Bounds on the Sign-Rank of AC^0
- Lower Bounds for Approximation by Nonlinear Manifolds
- Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
- Lower bounds in communication complexity based on factorization norms
This page was built for publication: Sign rank vs discrepancy
