Complete Problems for Multi-Pseudodeterministic Computations

on YouTube ↗26m

" summary

Establishes that collision probability estimation is complete for turning approximation and multi-valued search algorithms into pseudodeterministic ones: if collision estimation is pseudodeterministic (with error small enough) then any constant-factor multi-pseudodeterministic algorithm becomes pseudodeterministic. Builds a selector that runs two strategies, estimates collisions, and uses a 34/64 threshold (bounds like 9/16 and 1/2+2ε^2 appear) to pick reliably. Generalizes to multi-pseudodeterminism K+1/(K+2) and uses prefix-search for search-BPP via per-bit acceptance estimates losing ε per bit.

AI-written summary · about

" chapters (11)

1. 0:00Introduction
2. 0:14Complete Problems
3. 0:40Outline
4. 2:48Pseudodeterminism
5. 4:46Pseudorandomness
6. 6:33Results
7. 7:25Thresholds
8. 18:58Other Complete Problems
9. 19:22Multivalued Functions
10. 22:39Prefix Search
11. 25:12Conclusion

" related talks

• 45mImproved Learning from Time-bounded Kolmogorov ComplexityHalley Goldberg · Lower Bounds, Learning, and Average-Case Complexity
• 47mRange Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs AlgorithmsHanlin Ren · Lower Bounds, Learning, and Average-Case Complexity
• 58mDichotomy Theorems for Counting Problems IIXi Chen · Counting Complexity and Phase Transitions Boot Camp
• 56mEntropy, Capacity, and CountingNisheeth Vishnoi · Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019)
• 27mSmall Value Parallel Repetition for General GamesAnkit Garg · Information Theory in Complexity Theory and Combinatorics 2015
• 48mUnstructured Hardness to Average-Case RandomnessRoei Tell · Lower Bounds, Learning, and Average-Case Complexity
• 53mA Commentary on the Collision of WorldsRahul Santhanam · Lower Bounds, Learning, and Average-Case Complexity
• 01h 10mDistribution Estimation and Applications IAlon Orlitsky · Information Theory Boot Camp 2015