Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-071 | 10th April 2024 19:06

Lifting with Inner Functions of Polynomial Discrepancy

RSS-Feed




TR24-071
Authors: Yahel Manor, Or Meir
Publication: 10th April 2024 20:50
Downloads: 328
Keywords: 


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.



ISSN 1433-8092 | Imprint