Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-071 | 10th April 2024 19:06

Lifting with Inner Functions of Polynomial Discrepancy

RSS-Feed




TR24-071
Authors: Yahel Manor, Or Meir
Publication: 10th April 2024 20:50
Downloads: 109
Keywords: 


Abstract:

Lifting theorems are theorems that bound the communication complexity
of a composed function $f\circ g^{n}$ 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.



ISSN 1433-8092 | Imprint