2006/05/21 by Russell Impagliazzo · 5 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Cryptography and Data Security #Randomized algorithm #Algorithm #Computer science #A priori and a posteriori #Deterministic algorithm #Analysis of algorithms #Computation #Theoretical computer science #Mathematics
paper · doi:10.1145/1132516.1132571
openalex publication_date 2006/05/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Among the most important modern algorithmic techniques is the use of random decisions. Starting in the 1970's, many of the most significant results were randomized algorithms solving basic compuatational problems that had (to that time) resisted efficient deterministic computation. (Ber72, SS79, Rab80, Sch80, Zip79, AKLLR). In contrast, many of the most exciting recent work has been on derandomizing these same algorithms, coming up with efficient deterministic versions, e.g., (AKS02, Rein05). This raises the question, can such results be obtained for all randomized algorithms? Will the remaining classical randomized algorithms be derandomized by similar techniques?Clear but complicated answers to these questions have emerged from complexity-theoretic studies of randomized complexity classes (e.g., RP and BPP) and pseudo-random generators. These questions are inextricably linked to another basic problem in complexity: which functions require large circuits to compute?In this talk, we'll survey some results from the theory of derandomization. I'll stress connections to other questions, especially circuit complexity, explicit extractors, hardness amplification, and error-correcting codes. Much of the talk is based on joint work with Valentine Kabanets and Avi Wigderson, but it will also include results by many other researchers.A priori, possibilities concerning the power of randomized algorithms include: