2025/03/31 by Siddharth Iyer, Iyer, Siddharth
Computer Science · Engineering · #Advanced Graph Theory Research #Algebra over a field #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Degree (music) #FOS: Computer and information sciences #Matrix (chemical analysis) #Rank (graph theory) #Sensitivity (control systems) #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.2503.24351
openalex publication_date 2025/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We prove a sensitivity-to-communication lifting theorem for arbitrary gadgets. Given functions f: \0,1\n→ \0,1\ and g : \mathcal X× \mathcal Y→ \0,1\, denote f∘ g(x,y) := f(g(x1,y1),…,g(xn,yn)). We show that for any f with sensitivity s and any g, D(f∘ g) ≥ s⋅ ((Ω(D(g)))/(\logrk(g)) - \logrk(g)), where D(⋅) denotes the deterministic communication complexity and rk(g) is the rank of the matrix associated with g. As a corollary, we get that if D(g) is a sufficiently large constant, D(f∘ g) = Ω(min\s,d\⋅ √(D(g))), where s and d denote the sensitivity and degree of f. In particular, computing the OR of n copies of g requires Ω(n⋅√(D(g))) bits.