1 of 29

The Iterative Win-Win Paradigm�(Part I):�Pseudodeterministic Construction of Primes

November 9, 2023

0 / 21

Hanlin Ren

Oxford

Joint work with Lijie Chen, Zhenjian Lu, Igor Oliveira, and Rahul Santhanam

Algorithm PSEUDO

 

 

❌

 

 

 

2 of 29

Primes & Dense Properties

3 of 29

Finding a prime

  •  

 

1 / 21

 

 

 

4 of 29

A Naïve Algorithm

2 / 21

 

 

 

Can use [AKS04] deterministic primality test!

 

Far from what we want! ☹

5 of 29

Dense Properties

  •  

3 / 21

 

Easy with randomness!

 

6 of 29

Hardness vs Randomness

4 / 21

 

 

Assuming the lower bound hypothesis, the PRG hits every dense property

  • In particular, the PRG contains a prime

 

Far from what we want! ☹

PRG: Pseudorandom generator

7 of 29

Our result

5 / 21

 

 

Next: what does “pseudodeterministic” mean?

8 of 29

Intermediate notion between deterministic and randomized algorithms

6 / 21

Deterministic algorithms

Algorithm DET

 

Randomized algorithms

Algorithm RAND

 

 

❌

 

 

 

 

One drawback of rejection sampling:

it outputs different primes on different executions

Let’s require different executions of RAND to output the same prime!

9 of 29

Pseudodeterministic algorithms

  • A randomized algorithm is pseudodeterministic, if on most of its computational branches, it outputs the same answer.
  • Any (bounded) observer thinks the algorithm is deterministic!

7 / 21

Pseudodeterministic algorithms

Algorithm PSEUDO

 

 

❌

 

 

 

Deterministic algorithms

Algorithm DET

 

Randomized algorithms

Algorithm RAND

 

 

❌

 

 

 

10 of 29

Our result

8 / 21

 

 

 

“canonical” primes

Spoiler ahead: little number theory but heavy complexity theory ☺

 

11 of 29

Warm-Up:�sub-exponential time

12 of 29

Warm-up: Pseudodeterministic constructions in subexponential time

  •  

9 / 21

13 of 29

Idea II: Win-win Analysis

10 / 21

 

 

YES

NO

 

14 of 29

Idea I: Hardness vs Randomness

11 / 21

 

 

against non-uniform circuits

against non-uniform circuits

 

 

 

NW94, IW97

IW01, TV07

Recap

 

Randomness is powerful, �so pseudodet algo possible

YES

Derand. is possible,�so det algo possible

NO

 

15 of 29

Subexponential Time…?

12 / 21

 

 

 

YES

 

NO

 

Time complexity of…

 

 

 

 

 

 

 

 

… YES case

… NO case

… the overall algorithm

 

16 of 29

A refined win-win analysis!

 

17 of 29

The Chen-Tell generator: Scaled-down uniform hardness-randomness tradeoff

13 / 21

 

Generators in IW01, TV07

H vs R

The GKR protocol

Chen-Tell Generator

H vs R

scaled-down

scaled-down

 

 

 

 

 

 

 

18 of 29

The Chen-Tell generator�(reconstructive version)

14 / 21

 

 

 

 

 

 

 

 

19 of 29

Pseudodeterministic Constructions�from Chen-Tell?

15 / 21

 

 

 

 

 

YES

NO

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

“derand. is possible”, so get det. algo

20 of 29

Apply it again?

16 / 21

 

 

 

 

 

YES

NO

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

21 of 29

… and again

17 / 21

 

 

YES

NO

 

 

 

 

 

 

 

 

YES

YES

 

 

 

 

 

 

 

 

 

 

 

 

NO

 

NO

22 of 29

Each Iteration

  •  

18 / 21

 

 

YES

NO

 

 

 

 

 

 

 

 

 

 

23 of 29

 

  •  

19 / 21

 

 

 

 

24 of 29

Algorithm CLORS23

20 / 21

 

 

 

25 of 29

Summary

21 / 21

 

YES

NO

YES

NO

YES

NO

 

Thank you!

Questions are welcome!

 

 

YES

NO

 

 

 

 

 

 

 

 

 

 

 

26 of 29

 

  •  

22 / 25

27 of 29

Bounded Relativization

  •  

23 / 25

28 of 29

Omitted Details: Shaltiel-Umans Generator

24 / 25

 

 

 

Nisan-Wigderson

 

Shaltiel-Umans

This paper: Shaltiel-Umans as a HSG with learning reconstruction!

 

 

 

 

 

 

 

29 of 29

Using SU in Chen-Tell

25 / 25

 

 

 

 

 

 

 

 

Shaltiel-Umans