Fast Derandomization Techniques: Eliminating Randomness Efficiently

Simple and fast derandomization from very hard functions Eliminating randomness at almost no cost Lijie Chen Roei Tell MIT MIT

Todays Plan Today s Plan Part I (Introduction) Previous results on Derandomization, the PRG approach The work of [DMOZ 2020] Our Results Part II (Taste of Techniques) Lower Bound Optimal Derandomization

Todays Plan Today s Plan Part I (Introduction) Previous results on Derandomization, the PRG approach The work of [DMOZ 2020] Our Results Part II (Taste of Techniques) Lower Bound Optimal Derandomization

Randomized Algorithms Randomized Algorithms Algorithms making coin tosses during computation, and are expected to be correct with high probability Randomized Algorithms are everywhere and very useful.

Derandomization: Motivation Derandomization: Motivation Derandomization Deterministic Algorithms Deterministic Algorithms Randomized Algorithms Randomized Algorithms Practical Concern Randomized Algorithm usually require access to high-quality random bits, which could be a scarce resource. randomized algorithms running on them do not have a correctness guarantee In practice, randomness are usually ``generated by deterministic procedure with a short seed.

Derandomization: Motivation Derandomization: Motivation Theoretical Concern I Theoretical Computer Science treats randomness as an important computational resource as well. Like computational time and space. Time vs Randomness Given two fundamental resource (time and randomness). The natural theoretical question would be to study the trade off between these two.

Derandomization: Motivation Derandomization: Motivation Theoretical Concern II Derandomization is also closely connected to the task of proving circuit lower bounds, another fundamental problem in Theoretical Computer Science [IW 04], [Wil 11] Derandomization Circuit Lower Bounds [NW 94], [IW 99]

Derandomization: Central Question Derandomization: Central Question To what extend can we reduce randomness requirement by allowing the algorithm more running time? BPP P all problems solvable in probabilistic polynomial time all problems solvable in deterministic polynomial time Central Question Is BPP = P?

Pseudorandom Generator (PRG) Pseudorandom Generator (PRG) A deterministic procedure ?: 0,1? 0,1? expanding a small seed? into a much longer output ? which looks uniform to poly-time procedures on 0,1? ???(??) fools randomized algorithm ? using ? random bits PRG ? bits ? bits ? in ?? deterministic time ?(log ?)-seed length PRG ??? = ?

Hardness Hardness- -to to- -Randomness Paradigm Randomness Paradigm Initiated and developed in classical work of [Yao82; BM84; NW94; IW99] Randomness can be extracted from very hard functions! A PRG construction ?? A hard function ? How to show ?? looks random to an efficient procedure? Efficient reduction! Any algorithm ? distinguishes ??(??) and ?? An algorithm ?? computing ? Hardness Randomness Implies No efficient algorithm ? can distinguishes ??(??) and ?? ? cannot be computed efficiently

Classic Work Classic Work [IW 99] If there is a function ? computable in ??time but cannot be computed by 20.99-time algorithms with 20.99 bits of advice, then ??? = ? at least ? ??-time deterministic algorithm a ?(?)-time randomized algorithm Still a bit slow? Can we do faster? Problem solved? if we only care about polynomialtime or not.

More Fine More Fine- -Grained Understanding? Grained Understanding? deterministic algorithm ? ?(?)-time a ?(?)-time randomized algorithm Alternatively, What is the fastest derandomization of ??????[?(?)]? all problems solvable in probabilistic?(?) time

[Doron, [Doron, Moshkovitz Moshkovitz, Oh, and Zuckerman, 2020] , Oh, and Zuckerman, 2020] Under some hardness assumption against nonuniform ?? protocols, ?????? ? ? ????[? ??] See next slide Open Question I Derandomization with a Quadratic Slowdown The lower bound shows the ? ?2 slowdown is necessary for ? ? = ?. Can we do better for ? ? ?? A Partial Converse in [Williams 2016] Under the Nondeterministic Strong Exponential-Time Hypothesis (NSETH), BPTIME[n] TIME[?1.99] See later slide

[Doron, [Doron, Moshkovitz Moshkovitz, Oh, and Zuckerman, 2020] , Oh, and Zuckerman, 2020] some hardness assumption against nonuniform ?? protocols If there is a function ? computable in 2? time but cannot be computed computed by by ??.??- -time Merlin time Merlin- -Arthur protocol with of advice of advice, then ?????? ? ? cannot be Arthur protocol with ??.?? ? bits bits ????[? ??] Their power is less understood Nonstandard Assumption Assumed hardness against exponential-time nonuniform Merlin-Arthur protocols Open Question II Can we obtain similar results under standard assumptions like [IW 99]?

Result I: Result I: Derandomization with Overhead Derandomization with Overhead ? For every ? 1. If the following two assumptions hold, then ?????? ?? ????[??+1] Assumption (2) Assumption (1) One-Way Functions Exist Time Hierarchy Theorem still holds against 20.99? bits of advice The Standard and Minimum Assumption in Cryptography Against poly- size circuits Natural Generalization of Classic Circuit Lower Bounds. Is in fact necessary !

Result I: Result I: Derandomization with Overhead Derandomization with Overhead ? For every ? 1. If the following two assumptions holds, then ?????? ?? ????[??+1] Assumption (2) Time Hierarchy Theorem still holds against 20.99? bits of advice Assumption (1) One-Way Functions Exist Time Hierarchy Theorem There is a function ? computable in 2?? time but cannot be computed by 2? 0.01 ?-time algorithms. Our Assumption (2) There is a function ? computable in 2?? time but cannot be computed by 2? 0.01 ?-time algorithms with ??.??? bits of advice.

Result I: Result I: Derandomization with Overhead Derandomization with Overhead ? Compare with the Assumption in [IW 99] The Assumption in [IW 99] The Assumption in [IW 99] There is a function ? computable in ??time but cannot be computed by ??.???-time algorithms with ??.??? bits of advice ??.??-size circuits. There is a function ? computable in ??time but cannot be computed by The Common Philosophy Nonuniform advice cannot significantly speed up generic computation Our Assumption (2) There is a function ? computable in ??? time but cannot be computed by ?? ?.?? ?-time algorithms with ??.??? bits of advice.

Assumption (2) is Necessary for PRGs Assumption (2) is Necessary for PRGs PRG Approach to Derandomization with Overhead ? Needs a log ?-seed length PRG against ??-time algorithms unconditional Equivalent? under OWFs Assumption (2) Time Hierarchy Theorem still holds against 20.99? bits of advice

Result II: Result II: Overhead Overhead ? is Optimal under #NSETH is Optimal under #NSETH #SAT What is #NSETH? Given a formula ? on ? variables, how many satisfying assignments does it have? Nondeterministic Algorithms for #SAT A nondeterministic algorithm ? solves #SAT, if for every input formula ?. On a computational path, ? either (1) outputs the correct answer or (2) outputs ``Failed . And (1) happens for at least one computational path.

Result II: Result II: Overhead Overhead ? is Optimal under #NSETH under #NSETH is Optimal #NSETH No ??.??-time nondeterministic algorithm can solve #???. Under #NSETH, for all constants ? BPTIME[??] TIME[??+0.99].

Result III: Result III: Better Derandomization for Better Derandomization for Average Average- -Case Case Can we do faster than ? ? ?? Under similar assumptions as in our first result. Average-Case Derandomization For every ? ??????[?(?)], there exists a deterministic algorithm ?? running in time ? ? ??.??, such that for every?(?)-time sampleable distribution ?, ?? ? ???? ? ? For ? ??????[?(?)], design a deterministic algorithm ?? such that, with respect to inputs drawn from any natural distribution, ?? correctly solves ? with overwhelming probability. ? ?(?).

Todays Plan Today s Plan Part I (Introduction) Previous results on Derandomization, the PRG approach The work of [DMOZ 2020] Our Results Part II (Taste of Techniques) Lower Bound Optimal Derandomization

Result II: Result II: Overhead Overhead ? is Optimal under #NSETH under #NSETH is Optimal #NSETH No ??.??-time nondeterministic algorithm can solve #???. Under #NSETH, for all constants ? BPTIME[??] TIME[??+0.99].

Proof System View of Nondeterministic Algorithms Proof System View of Nondeterministic Algorithms #SAT Given a formula ? on ? variables, how many satisfying assignments does it have? Nondeterministic Algorithms for #SAT A T(n)-time nondeterministic algorithms for #??? is a linear-time verifier ? which takes a formula ? of ? variables and a proof ? of length ?(?). ?(?,?)is either (1) (the proof is wrong) (2) the correct answer of ?. (2) happens with at least one proof ?.

Proof Idea Proof Idea [Williams 2016] There is a 2?/2-time Merlin-Arthur Protocol for #??? ?????? ? ????[?1.9] means this ? can be derandomized in 20.95 time! 2?/2-time Merlin-Arthur Protocol for #SAT There is a linear-time randomized verifier ? which takes a formula ? of ? variables and a proof ? of length 2?/2. ?(?,?)is either (1) (the proof is wrong) with high probability; (2) the correct answer of ? with high probability. (2) happens with at least one proof.

Improvement Improvement There is a 2? (? 1)/?-time Merlin-Arthur Protocol for #???, with proof length 2?/? ?????? ?? 1 ????[?? 0.01] means this ? can be derandomized in 20.99? time! New Merlin-Arthur Protocol for #SAT There is a ?? 1-time randomized verifier ? which takes a formula ? of ? variables and a proof ? of length ? = 2?/?. ?(?,?)is either (1) (the proof is wrong) with high probability; (2) the correct answer of ? with high probability. (2) happens with at least one proof.

Bottleneck of the PRG Approach: Seed Length Previous work (including [DMOZ 2020]) To fool a ?(?)-time randomized algorithm, it suffices to build a PRG fooling ?(?)-size circuits. Need to enumerate every seeds, running time becomes 2log ?(?) ? ? = ?(?)2 PRG for ?(?)-size circuits Requires log?(?) seed length How do we get faster-than-quadratic derandomization? We need a PRG with seed length log ? instead of log ?(?)

A Closer Look at the PRG Approach There is a linear-time algorithm ?(?,?) such that ? 0,1?, ? 0,1?(?). Let ? ?????? ? ? . ? ? Pr ?? ?,? = 1 ?/? ? ? Pr ?? ?,? = 1 ?/? Let ??? ?(?,?). We need a PRG to fool all the functions ??(?) Previous work Our Observation All functions ??(?) can be simulated by ? ? -size circuits. So it suffices to fool all ?(?)-size circuits. of nonuniform advice bits. All ??(?) are functions on ?(?) bits, but only with ? bits

Optimal Derandomization: A More Sophisticated PRG Approach Let ??? ?(?,?). We need a PRG to fool all functions ??(?) Our Observation All ??(?) are linear-time functions on ?(?) bits, but only with ? bits of nonuniform advice bits. That is, it suffices to construct a PRG to fool linear-time function on ? = ?(?)bits, with ? ?? = ?bits of advice

Our Results in More Detail For every ? 1. If the following assumptions hold, then there is a ? log? seed length PRG ? fooling linear-time functions with ?1/? bits of advice 1 Assumption (2) Assumption (1) One-Way Functions Exist There is a function ? computable in 2?? time but cannot be computed by 2? 0.01 ?-time algorithms with ??.??? bits of advice.

Bottleneck of the PRG Approach: Reduction Overhead Bottleneck of the PRG Approach: Reduction Overhead at least ? ??-time deterministic algorithm a ?(?)-time randomized algorithm Why such a big blowup? A PRG construction ?? Issue A hard function ? How to show ?? looks random to a uniform procedure? Hardness against ??-time algorithms only translates to pseudo randomness against ?-time algorithms Efficient Reduction Any T-time algorithm ? distinguishes ??(??) and ?? An algorithm ?? computing ? in ?? time To fool ?-time algo, ? needs at least ?? time, so ?? also takes ?? time! Implies No efficient ?-algorithm ? can distinguishes ??(??) and ?? ? cannot be computed efficiently in ?? time

Key Ingredient Key Ingredient Super Efficient Reduction Assuming OWFs Super Efficient Reduction Assuming OWFs A PRG construction ?? A hard function ? How to show ?? looks random to a uniform procedure? Improvement Hardness against ?-time algorithms translates to pseudo randomness against T-time algorithms with no loss Efficient Reduction Any T-time algorithm ? distinguishes ??(??) and ?? An algorithm ?? computing ? in ? time Implies No efficient ?-algorithm ? can distinguishes ??(??) and ?? ? cannot be computed efficiently in ? time

Conclusion Conclusion We proved that under hardness assumption against deterministic computation with advice, ?????? ? ? ????[? ?(?)] The ? overhead is optimal under #?????. For average-case derandomization, nearly ?(?)-time derandomization is possible.

Thanks you! Any Questions?