Communication complexity and discrepancy of halfplanes

DOI10.4230/LIPICS.SOCG.2024.5MaRDI QIDQ6895904zbMATH OpenFDO

Authors Manasseh Ahmed, Tsun-Ming Cheung, Hamed Hatami, Kusha Sareen

Publication date 24 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2024.5

zbMATH Keywords

discrepancy theoryfactorization normrandomized communication complexity

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Communication complexity, information complexity (68Q11) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• A discrepancy lower bound for information complexity
• A trace bound for the hereditary discrepancy
• Communication Complexity
• Complexity measures of sign matrices
• Crossing patterns of semi-algebraic sets
• Discrepancy of set-systems and matrices
• Geometric discrepancy. An illustrated guide
• Halfspace matrices
• scientific article; zbMATH DE number 1263236 (Why is no real title available?)
• scientific article; zbMATH DE number 524134 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• Learning complexity vs communication complexity
• Lower bound methods for sign-rank and their limitations
• Lower bounds for the approximate degree of block-composed functions
• Lower bounds in communication complexity based on factorization norms
• Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
• Probabilistic communication complexity
• Sign-rank vs. discrepancy
• The pattern matrix method
• Tight upper bounds for the discrepancy of half-spaces
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(1)

• Randomized communication and implicit graph representations

This page was built for publication: Communication complexity and discrepancy of halfplanes

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