skip to main content
Language:
Search Limited to: Search Limited to: Resource type Show Results with: Show Results with: Search type Index

Query-to-Communication lifting using low-discrepancy gadgets

Digital Resources/Online E-Resources

Citations Cited by
  • Title:
    Query-to-Communication lifting using low-discrepancy gadgets
  • Author: Koroth, Sajin
  • Subjects: Computer science ; Mathematics ; Theoretical computer science
  • 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 Non UBC Unreviewed Author affiliation: Simon Fraser University Postdoctoral
  • Publisher: UBC cIRcle BIRS Workshop Lecture Videos
  • Creation Date: 2020
  • Language: English
  • Source: Lunaris – Canada’s National Data Discovery Service
Back to results list
INSPIRE LIBRARY - TON DUC THANG UNIVERSITY (84-028) 37 755 057 Feedback
19 Nguyen Huu Tho St. Dist.7, HCM thuvien@tdtu.edu.vn

Copyright © 2017 INSPIRE LIBRARY - TON DUC THANG UNIVERSITY

Searching Remote Databases, Please Wait