Lifting with Inner Functions of Polynomial Discrepancy

Yahel Manor, Or Meir

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…