Lifting with Inner Functions of Polynomial Discrepancy
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914749079355392 |
|---|---|
| author | Manor, Yahel Meir, Or |
| author_facet | Manor, Yahel Meir, Or |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_07606 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lifting with Inner Functions of Polynomial Discrepancy Manor, Yahel Meir, Or Computational Complexity 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. |
| title | Lifting with Inner Functions of Polynomial Discrepancy |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2404.07606 |