Derandomizing Algorithms: Challenges and Solutions

Delve into the realm of derandomizing algorithms with Oded Goldreich from the Weizmann Institute of Science as he discusses standard and quantified derandomization challenges, exploring the search problems and proofs underlying the quest to find input solutions for specific circuit classes. Discover the intricate strategies and theorems that shed light on cracking AC0 circuits and reducing errors through clever restrictions and extractors.

• Derandomizing Algorithms
• Oded Goldreich
• Weizmann Institute
• Circuit Classes
• Derandomization Challenges

gledhill_a Follow

Uploaded on Oct 03, 2024 | 0 Views

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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. On Derandomizing Algorithms that Err Extremely Rarely Oded Goldreich Weizmann Institute of Science Based on Joint work with Avi Wigderson

2. Standard Derandomization Challenges Given a circuit C (from a certain class) such that Prob[C(x)=1] > , find an input x such that C(x)=1. Famous frontier: Solve it in poly-time for the class AC0. A two-sided error version: Given a circuit C (from a certain class) such that Prob[C(x)= ] > , for some , find an input x such that C(x)= . A black-box version: Given circuit parameters, find a set of inputs S such that every circuit C that satisfies Prob[C(x)=1] > , there exists x S such that C(x)=1 .

3. Quantified Derandomization Challenges (new) For a class C and a bound B, given an n-bit input circuit C from C such that | x:C(x)=0}| < B(n), find an input x such that C(x)=1. The above is called the (C,B)-search problem. Focus: Small B; e.g., quasi-polynomial, sub-exponential. Q: Is the (P/poly,nlog n)-search problem solvable in (deter.) poly-time? THM1: The (AC0,exp(n0.999))-search problem is solvable in (deter.) poly-time. THM2: Standard derandomization of AC0 is reducible to the (AC0,exp(n/log n))-search problem.

4. On Quantified Derandomization Problems (C,B)-search problem = given an n-bit input circuit C from C such that | x:C(x)=0}| < B(n), find an input x such that C(x)=1. THM1: The (AC0,exp(n0.999))-search problem is solvable in (deter.) poly-time. THM2: Standard derandomization of AC0 is reducible to the (AC0,exp(n/log n))-search problem. THM3: Standard derandomization of AC0[2]is reducible to the (AC0[2],exp(n0.001))-search problem.

5. On the proof of THM 1 (C,B)-search problem = given an n-bit input circuit C from C such that | x:C(x)=0}| < B(n), find an input x such that C(x)=1. THM1: The (AC0,exp(n0.999))-search problem is solvable in (deter.) poly-time. Idea: Hit the circuit with a pseudorandom restriction (generated based on a seed of log length) such that (i) at least 2n0.999variables survive, and (ii) the circuit simplifies to a constant. The PR-restriction may not preserve the acceptance probability of a generic AC0 circuit (not even approximately), but this suffices for us since the number of surviving variables exceeds the error bound B(n). When designing the PR-restriction we focus on the simplification, which is obtained by repeated applications of a PR switching lemma.

6. On the proof of THM 3 (C,B)-search problem = given an n-bit input circuit C from C such that | x:C(x)=0}| < B(n), find an input x such that C(x)=1. THM3: Standard derandomization of AC0[2]is reducible to the (AC0[2],exp(n0.001))-search problem. Idea: Given a circuit for the standard problem, obtain a circuit for the quantified problem via radical error reduction (using a randomness extractor). Extractors for min-entropy n0.001that use a seed of log length and extract n0.0005bits can be computed in AC0[2], whereas approximate majority can be computed in AC0.

7. On the proof of THM 2 (C,B)-search problem = given an n-bit input circuit C from C such that | x:C(x)=0}| < B(n), find an input x such that C(x)=1. THM2: Standard derandomization of AC0 is reducible to the (AC0,exp(n/log n))-search problem. We cannot perform error-reduction in AC0 since we do not know of an adequate extractor computable in AC0. But it suffices to perform error-reduction for AC0! (i) Reduce randomness to polylog (via PRG), (ii) perform radical error reduction (via an extractor), (iii) straightforward error+randomness amplification. in a class = via a randomness extractor, whereas for a class allows using a pseudo-extractor that only fools the class.

8. Summary: Quantified Derandomization (C,B)-search problem = given an n-bit input circuit C from C such that | x:C(x)=0}| < B(n), find an input x such that C(x)=1. Q: Is the (P/poly,nlog n)-search problem solvable in (deter.) poly-time? Results regarding quantified derand may improve over the known for standard derand (see Thm1), but in some cases quantified derand implies standard derand (see Thm2 and Thm3). Hope: A smooth transition. E.g., for AC0,from B(n)=exp(n0.999) as in Thm1 to B(n)=exp(n/log n) as in Thm2.

9. END Slides available at http://www.wisdom.weizmann.ac.il/~oded/T/aq.pptx Paper available at http://www.wisdom.weizmann.ac.il/~oded/p_aq.html