Pseudodeterministic Algorithms and PPD Algorithms Explained
Explore the concepts of pseudodeterministic algorithms for binary relations, error reduction strategies, and the non-adaptive composition of PPD algorithms. Learn how these algorithms work and their applications in solving search problems efficiently.
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
A pseudo-gift by Oded
Pseudodeterministic algorithms For a binary relation R, let R(x)= y:(x,y) R and SR= x:R(x) , and consider the search problem associated with R. A pseudodeterministic algorithm A solving R satisfies For every x SRthere exists cx R(x) s.t Prob[A(x)=cx] 2/3. (canonical) For every x SRit holds that Prob[A(x)= ] 2/3. Error reduction applies. Drawback: Cannot approximate the average value of a huge function. [slide 4]
Pseudo-pseudodeterministic algorithms For a binary relation R, let R(x)= y:(x,y) R and SR= x:R(x) , and consider the search problem associated with R. An m-pseudodeterministic algorithm A solving R satisfies For every x SRthere exists Cx R(x) of size at most m s.t Prob[A(x) Cx] (m+1)/(m+2). For every x SRit holds that Prob[A(x)= ] 2/3. Error reduction applies (since outputs not in Cxare detected). Original notion coincides with m=1.
Whats the point? Well, while a super-fast randomized algorithm can approximate the average value of a function, a pseudodeterminstic algorithm cannot do that [GGR]. Yet, a 2-pseudodterministic algorithm can! Actually, a (t+1)-pseudodeterministic algorithm can approximate the average value of t functions.* Round according to a single, randomly selected (small) shift of the thresholds. ) This improves over the obvious 2t-pseudodeterministic alg.
Non-adaptive composition of PPD algorithms THM: Suppose that A is an m-pseudeterministic algorithm for solving the search problem R. Then, we can solve t instances of R by a (t (m-1)+1)-pseudodeterministic algorithm that invokes A for poly(tm) times. Proof idea: Estimate the probability that the various solutions appear (for each of the instances), trim each list by a single random threshold (chosen in the gap between the most frequent privileged* solution and any non-privileged solution), and use the lex-first remaining solution. *) Privileged/canonical solution for x = one of the elements of Cx (in def of PPD).
Dedication TO A GREAT WOMAN
