Lifting with Inner Functions of Polynomial Discrepancy
<|reference_start|>Lifting with Inner Functions of Polynomial Discrepancy: 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.<|reference_end|>
@article{manor2024lifting,
    title={Lifting with Inner Functions of Polynomial Discrepancy},
    author={Yahel Manor and Or Meir},
    journal={arXiv preprint arXiv:2404.07606},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.07606},
    primaryClass={cs.CC}
}