ECCC-Report TR24-012https://eccc.weizmann.ac.il/report/2024/012Comments and Revisions published for TR24-012en-usFri, 26 Jan 2024 08:09:06 +0200
Paper TR24-012
| Structure in Communication Complexity and Constant-Cost Complexity Classes |
Hamed Hatami,
Pooya Hatami
https://eccc.weizmann.ac.il/report/2024/012Several theorems and conjectures in communication complexity state or speculate that the complexity of a matrix in a given communication model is controlled by a related analytic or algebraic matrix parameter, e.g., rank, sign-rank, discrepancy, etc. The forward direction is typically easy as the structural implications of small complexity often imply a bound on some matrix parameter. The challenge lies in establishing the reverse direction, which requires understanding the structure of Boolean matrices for which a given matrix parameter is small or large. We will discuss several research directions that align with this overarching theme.Fri, 26 Jan 2024 08:09:06 +0200https://eccc.weizmann.ac.il/report/2024/012