@prefix vivo: .
@prefix edm: .
@prefix dcterms: .
@prefix dc: .
@prefix skos: .
@prefix ns0: .
vivo:departmentOrSchool "Non UBC"@en ;
edm:dataProvider "DSpace"@en ;
dcterms:creator "Sajin Koroth"@en ;
dcterms:issued "2020-01-07T09:22:10Z"@en, "2019-07-10T11:18"@en ;
dcterms: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"""@en ;
edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/73160?expand=metadata"@en ;
dcterms:extent "53.0 minutes"@en ;
dc:format "video/mp4"@en ;
skos:note ""@en, "Author affiliation: Simon Fraser University"@en ;
dcterms:spatial "Banff (Alta.)"@en ;
edm:isShownAt "10.14288/1.0387521"@en ;
dcterms:language "eng"@en ;
ns0:peerReviewStatus "Unreviewed"@en ;
edm:provider "Vancouver : University of British Columbia Library"@en ;
dcterms:publisher "Banff International Research Station for Mathematical Innovation and Discovery"@en ;
dcterms:rights "Attribution-NonCommercial-NoDerivatives 4.0 International"@en ;
ns0:rightsURI "http://creativecommons.org/licenses/by-nc-nd/4.0/"@en ;
ns0:scholarLevel "Postdoctoral"@en ;
dcterms:isPartOf "BIRS Workshop Lecture Videos (Banff, Alta)"@en ;
dcterms:subject "Mathematics"@en, "Computer Science, Theoretical Computer Science"@en ;
dcterms:title "Query-to-Communication lifting using low-discrepancy gadgets"@en ;
dcterms:type "Moving Image"@en ;
ns0:identifierURI "http://hdl.handle.net/2429/73160"@en .