Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
19cs422 [2019-06-03] Martin Ziegler19cs422 [2019-06-09] (current) Martin Ziegler
Line 66: Line 66:
   * Quantifier Alternations   * Quantifier Alternations
  
-VII. Advanced Complexity +VII. Advanced Complexity  ({{19cs422g.ppt|ppt}}, {{19cs422g.pdf|pdf}}): 
-  * Time Hierarchy+  * (Time Hierarchy)
   * complexity of cryptography: UP and one-way functions   * complexity of cryptography: UP and one-way functions
-  * counting problems, Toda's Theorem +  * (counting problems, Toda's Theorem) 
-  * LOGSPACE, Immerman-Szelepcsenyi Theorem +  * (LOGSPACE, Immerman-Szelepcsenyi Theorem) 
-  * Approximation algorithms and hardness +  * (Approximation algorithms and hardness) 
-  * randomized algorithms, probability amplification, BPP, Adleman and Sipser-Gacs-Lautemann Theorems+  * (randomized algorithms, probability amplification, BPP, Adleman and Sipser-Gacs-Lautemann Theorems)
  
 ===== Homework/Assignments =====  ===== Homework/Assignments =====