Or Meir

University of Haifa

ירצה על

Will lecture on

Query-to-Communication Lifting Using Low-Discrepancy Gadgets

Lifting theorems are theorems that relate the query complexity of a function f to the communication complexity of the composed function f o g, for some “gadget” function g . 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 significantly increase the range of gadgets for which such lifting theorems hold. 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 of the theorem. Second, our result can be seen as a strong generalization of a direct-sum theorem for functions with low discrepancy. Joint work with Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, and Toniann Pitassi    


Bio: Or Meir is a senior lecturer at the university of Haifa. He did his Ph.d. at the Weizmann institute for science under the supervision of Oded Goldreich, and was a postdoctoral fellow at Stanford university, the institute of advanced study at Princeton, and the Weizmann institute of science.

הרצאה פרונטלית – יש להגיע פיזית להרצאה


בניין 211/212 אולם 25 

בניין ליברנט אולם 25