"Non UBC"@en .
"DSpace"@en .
"Sajin Koroth"@en .
"2020-01-07T09:22:10Z"@en .
"2019-07-10T11:18"@en .
"Lifting theorems are theorems that relate the query complexity of a function f : {0, 1}^n \u00E2 {0, 1} to the communication complexity of the composed function f \u00E2 \u00A6 g^n, for some \u00E2 gadget\u00E2 g : {0, 1}^b \u00C3 {0, 1}^b \u00E2 {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.\n\n\nWe 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.\n\n\nOur 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.\n\n\nJoint work with Arkadev Chattopadhyay, Yuval Filmus, Or Meir, Toniann Pitassi"@en .
"https://circle.library.ubc.ca/rest/handle/2429/73160?expand=metadata"@en .
"53.0 minutes"@en .
"video/mp4"@en .
""@en .
"Author affiliation: Simon Fraser University"@en .
"Banff (Alta.)"@en .
"10.14288/1.0387521"@en .
"eng"@en .
"Unreviewed"@en .
"Vancouver : University of British Columbia Library"@en .
"Banff International Research Station for Mathematical Innovation and Discovery"@en .
"Attribution-NonCommercial-NoDerivatives 4.0 International"@en .
"http://creativecommons.org/licenses/by-nc-nd/4.0/"@en .
"Postdoctoral"@en .
"BIRS Workshop Lecture Videos (Banff, Alta)"@en .
"Mathematics"@en .
"Computer Science, Theoretical Computer Science"@en .
"Query-to-Communication lifting using low-discrepancy gadgets"@en .
"Moving Image"@en .
"http://hdl.handle.net/2429/73160"@en .