Deterministic Communication vs. Partition Number
summary
Proves a superlinear gap: deterministic communication complexity grows like (log partition number)^{1.5} (up to polylogs) and for the one-rectangle measure chi_1 it achieves a quadratic gap. Method composes an outer Boolean f with the indexing gadget, proves a decision-tree (query) separation of k versus k^2 using matrices with pointer entries, and lifts that gap via a modified Raz-McKenzie lifting (information-theoretic ingredients). Construction yields an explicit composed family, improves prior 1.26 exponent to about 1.5, and yields a new log-rank lower bound.
AI-written summary · about