SU-CS254 FEB052025

Key Sequence

Notation

New Concepts

• randomness
• some random algorithms
  • matrix multiplication verification
  • minimum spanning tree
  • undirected STCONN
  • PERFECT-MATCHING
  • polynomial identity testing
• randomized turing machine
  • BPTIME
  • RP

Important Results / Claims

• some questions of randomness
• RP in NP
• RP success amplifies

Questions

Interesting Factoids