New Direct Product Results in Communication Complexity by Rahul Jain
Explore the latest research by Rahul Jain from the Centre for Quantum Technologies and Department of Computer Science at the National University of Singapore, focusing on new direct product results in communication complexity. The study delves into solving k copies faster, direct product scenarios, one-way and two-way cases, applications, and open questions in the field of communication complexity.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
New Direct Product results in Communication Complexity Rahul Jain Centre for Quantum Technologies and Department of Computer Science National University of Singapore.
Can we solve k copies faster ? Direct Product f X Y Z Let there be ERROORR! x1;:::;xk y1;:::;yk Task: Output z1;:::zk2 Zksuch that for all i;(xi;yi;zi) 2 f Direct Product : Isthetrivial protocol essentially optimal ? Open: Rpub 1 2 - (k )(fk) = - (k Rpub (f )) ?
Our Results f X Y Z x1;:::;xk y1;:::;yk x1;:::;xk y1;:::;yk Application: Direct product for (First shown by [Klauck 10])
New Characterization y1 y2y3 y1 y2y3 x1 x2 x3 ... x1 x2 x3 ... ... ... 1 rec1; (f ) = minf log (R)g isone-way for haserror at most
New Characterization Use message compression of [Braverman, Rao 10] to get a one-way protocol with communication
Message Compression [Braverman, Rao 10]
Two-way case f X Y Z y1 y2y3 y1 y2y3 x1 x2 x3 ... x1 x2 x3 ... ... ... 1 rec (f ) = minf log (R)g ismessage-likefor haserror at most
Application Direct Product for Set Disjointness [Razborov 92] Our result
Questions ? Holy Grail: Rpub 1 2 - (k )(fk) = - (k Rpub (f )) ? En route: Thanks !
