- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Query-to-Communication lifting using low-discrepancy...
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Query-to-Communication lifting using low-discrepancy gadgets Koroth, Sajin
Description
Lifting theorems are theorems that relate the query complexity of a function f : {0, 1}^n â {0, 1} to the communication complexity of the composed function f â ¦ g^n, for some â gadgetâ g : {0, 1}^b à {0, 1}^b â {0, 1}. Such theorems allow transferring lower bounds from query complexity to the communication complexity, and have seen numerous applications in the recent years. In addition, such theorems can be viewed as a strong generalization of a direct-sum theorem for the gadget g. We prove a new lifting theorem that works for all gadgets g that have logarithmic length and exponentially-small discrepancy, for both deterministic and randomized communication complexity. Thus, we increase the range of gadgets for which such lifting theorems hold considerably. Our result has two main motivations: First, allowing a larger variety of gadgets may support more applications. In particular, our work is the first to prove a randomized lifting theorem for logarithmic-size gadgets, thus improving some applications the theorem. Second, our result can be seen a strong generalization of a direct-sum theorem for functions with low discrepancy. Joint work with Arkadev Chattopadhyay, Yuval Filmus, Or Meir, Toniann Pitassi
Item Metadata
Title |
Query-to-Communication lifting using low-discrepancy gadgets
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2019-07-10T11:18
|
Description |
Lifting theorems are theorems that relate the query complexity of a function f : {0, 1}^n â {0, 1} to the communication complexity of the composed function f â ¦ g^n, for some â gadgetâ g : {0, 1}^b à {0, 1}^b â {0, 1}. Such theorems allow transferring lower bounds from query complexity to the communication complexity, and have seen numerous applications in the recent years. In addition, such theorems can be viewed as a strong generalization of a direct-sum theorem for the gadget g.
We prove a new lifting theorem that works for all gadgets g that have logarithmic length and exponentially-small discrepancy, for both deterministic and randomized communication complexity. Thus, we increase the range of gadgets for which such lifting theorems hold considerably.
Our result has two main motivations: First, allowing a larger variety of gadgets may support more applications. In particular, our work is the first to prove a randomized lifting theorem for logarithmic-size gadgets, thus improving some applications the theorem. Second, our result can be seen a strong generalization of a direct-sum theorem for functions with low discrepancy.
Joint work with Arkadev Chattopadhyay, Yuval Filmus, Or Meir, Toniann Pitassi
|
Extent |
53.0 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: Simon Fraser University
|
Series | |
Date Available |
2020-01-07
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0387521
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Postdoctoral
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International