2024/04/11 by Yahel Manor, Manor, Yahel, Or Meir +1 · 1 citation
Computer Science · #Coding theory and cryptography #Computational Complexity (cs.CC) #Cryptography and Data Security #Cryptography and Residue Arithmetic #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2404.07606
openalex publication_date 2024/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Lifting theorems are theorems that bound the communication complexity of a composed function f∘ gn in terms of the query complexity of f and the communication complexity of g. Such theorems constitute a powerful generalization of direct-sum theorems for g, and have seen numerous applications in recent years. We prove a new lifting theorem that works for every two functions f,g such that the discrepancy of g is at most inverse polynomial in the input length of f. Our result is a significant generalization of the known direct-sum theorem for discrepancy, and extends the range of inner functions g for which lifting theorems hold.