Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > OR MEIR:
All reports by Author Or Meir:

TR24-071 | 10th April 2024
Yahel Manor, Or Meir

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




ISSN 1433-8092 | Imprint