__
TR24-071 | 10th April 2024 19:06
__

#### Lifting with Inner Functions of Polynomial Discrepancy

**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.