Sign rank vs discrepancy

DOI10.4230/LIPICS.CCC.2020.18MaRDI QIDQ5092468zbMATH OpenOpenAlexFDO

Authors Hamed Hatami, Kaave Hosseini, Shachar Lovett

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/lipics.ccc.2020.18

zbMATH Keywords

discrepancysign rankunbounded-error communication complexityweakly unbounded error communication complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Sign-rank vs. discrepancy
• Improved bounds on the sign-rank of \(\mathrm{AC}^0\)
• On rank vs. communication complexity
• The Sign-Rank of AC^0
• Exponential separation of information and communication for Boolean functions

Cites work

• Complexity measures of sign matrices
• Halfspace matrices
• scientific article; zbMATH DE number 524134 (Why is no real title available?)
• Improved bounds on the sign-rank of \(\mathrm{AC}^0\)
• Learning complexity vs communication complexity
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Lower Bounds for Approximation by Nonlinear Manifolds
• Lower bounds for the approximate degree of block-composed functions
• Lower bounds in communication complexity based on factorization norms
• Probabilistic communication complexity
• Simultaneous approximation of constraint satisfaction problems
• The pattern matrix method
• The Sign-Rank of AC^0
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(3)

• The hardest halfspace
• Sign-rank vs. discrepancy
• A hierarchy of constant communication complexity

This page was built for publication: Sign rank vs discrepancy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092468)