Sign-rank vs. discrepancy

DOI10.4086/TOC.2022.V018A019MaRDI QIDQ5093405zbMATH OpenOpenAlexFDO

Authors Kaave Hosseini, Hamed Hatami, Shachar Lovett

Publication date 26 July 2022

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2022.v018a019

zbMATH Keywords

communication complexitydiscrepancysign-rank

Mathematics Subject Classification ID

Communication complexity, information complexity (68Q11) Theory of computing (68Qxx)

Recommendations

• Sign rank vs discrepancy
• Halfspace matrices
• The Sign-Rank of AC^0
• Improved bounds on the sign-rank of \(\mathrm{AC}^0\)
• A linear lower bound on the unbounded error probabilistic communication complexity.

Cites work

• Halfspace matrices
• Lower bounds for the approximate degree of block-composed functions
• The hardest halfspace
• The pattern matrix method
• The Sign-Rank of AC^0

Cited in

(3)

• Sign rank vs discrepancy
• A Borsuk-Ulam lower bound for sign-rank and its applications
• Communication complexity and discrepancy of halfplanes

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 Q5093405)