On Geometric Measures for Information Complexity
summary
Defines a transcript wave function by taking square roots of transcript probabilities and uses the induced Hellinger (L2) distance, then proves negative‑type inequalities that yield concrete information‑complexity lower bounds. Key claim: a point‑array inequality with parameter λ implies an Ω(λ) information cost lower bound for distance‑estimation problems; proof is three lines using triangle/Z lemmas and symmetrization. Applications include tight lower bounds for some streaming problems and a K‑party Hamming‑cube inequality involving the digital‑search‑tree constant.
AI-written summary · about