SU-CS254 FEB102025

Key Sequence

New Concepts

• randomized turing machine
• ZPP
• BPP in EXPTIME

Important Results / Claims

• BPP success amplication
• randomness hierarchy
• alternate (“deterministic”) definition of randomized TM

Questions

Interesting Factoids