Seminar: Topics in Complexity
Spring 2022

George Voutsadakis

• List of Books in Complexity through which one may learn much more and in which one may find many more references.
• I am not an expert in Complexity; I am studying and sharing some of its fascinating concepts and results.
• The topics chosen are not necessarily closely interrelated and the lectures are not interdependent.
  
• The seminar is not aiming at a full understanding of all concepts presented nor at recounting every detail.
  Some of the topics are challenging and require a more dedicated, in-depth study to fully grasp.
  The goal of the seminar is to convey the main ideas and afford a quick, introductory look at a few concepts.
  
  
• Week 1 (Friday, January 21, 2:00pm EST): Spanning Trees and the Determinant
• Week 2 (Friday, January 28, 2:00pm EST): Communication Complexity
• Week 3 (Friday, February 11, 2:00pm EST): HORNSAT and φ-GRAPHS
  
• Week 4 (Friday, February 18, 2:00pm EST): Two Randomized Algorithms
• Week 5 (Friday, February 25, 2:00pm EST): Parallel Random Access Machines
• Week 6 (Friday, March 4, 2:00pm EST): The Classes P, NP and co-NP
• Week 7 (Friday, March 18, 2:00pm EST): Black Box Complexity
• Week 8 (Friday, April 1, 2:00pm EST): Gate Elimination
• Week 9 (Friday, April 15, 2:00pm EST): Oracle Turing Machines Part I
                                                                     The Baker, Gill, Solovay Theorem
  
• Week 10 (Friday, April 22, 2:00pm EST): Oracle Turing Machines Part II
                                                                      The Polynomial Hierarchy
  
• Week 11 (Friday, April 29, 2:00pm EST): Second-Order Logic and Graphs