Computational Complexity Theory

Instructor                           :    H. Adorna
e-mail                                :    ha@dcs.upd.edu.ph
Schedule                            :    Tuesdays and Thursdays, 14.00 to 16.00 / ACLab
Consultation Hours             :    M-F 16.00 to 18.00 / ACLab, please by appointment

Course Pre-requisites:
    Theory of
    Computation, and
    Algorithms courses
    or equivalent       
   
    [
if interested,
      consult with the

         instructor.]


Course Requirements:
    Problem Sets (PSet)
    Oral Reports (ORep)

Grade:
    40% PSet
    60% ORep

must obtained at least 60% in order to gain credit.

References:


Announcements!
  1. Kinakailangang magpakita sa unang araw ng pagpupulong, ika-10 ng Nobyembre 2009.  Kakatagpuin kayo ng isang bisitang taga-pamahala sa araw na ito sa ACLab sa ikatlong palapag ng gusaling UPAECH (gusali ng DCS at EnggLib2) sa ganap na ika-2 at kalahati ng hapon. 
  2. Si Henry, ang magtuturo ng kursong ito,  ay kasalukuyan pang nasa Uni Sevilla sa Espanya. Siya ay makaka-uwi sa Maynila ng hating-gabi ng ika-16 ng Disyembre 2009.  Samakatuwid, ika-17 ng Disyembre  2009 na ang kanyang pagdalo sa U.P. 
  3. Ninanais sana na mapanood ng bawat nagpatala sa seminar na ito ang mga palabas pang-akademiko na nakalaan sa bawat araw habang wala pa si Henry.  Ang mga ito ay tinatayang makakatulong sa paghahanda sa mga panayam na kakaharapin sa darating na taon.
  4. Ang kursong ito ay opisyal na magsisimula sa ika-17 ng Disyembre 2009 sa ganap na ika-2 at kalahati ng hapon sa silib pananaliksik ng Algorithms and Complexity (ACLab) sa ikatlong palapag ng gusaling (UPAECH) pangakademiko ng ating departamento.  Subalit ang pormal na panayam sa kursong ito ay magsisimula sa ika-5 ng Enero 2010.


Schedule of Lectures:

 Date Topics Resource file
  Part 1: [Self Recap]
  
 10. Nov Administrivia: GTKY (Getting-to-know-you) minus Instructor!
  
 12. Nov The "P vs. NP" Problem: Efficient Computation, Internet Security, and the Limits of Human Knowledge Video Public Lecture of
Avi Wigderson (IAS)
 video
 17. & 19.
 Nov
 Upang mabalik-tanawan ang nakaraang mga kurso sa Algorithms noong mga nakaraang mga taon, iminumungkahi namin na tunghayan ninyo ang mga pelikula na ito ng panayam sa MIT sa Estados Unidos.  Ito ay ginawang pampubliko sa mga sumusunod na webpage: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-00Fall-2008/LectureVideos/index.htm
mahalaga tunghayan ang ika-7 at ika-8 sa grupo ng mga pelikulang panayam na ito nina
Prof. Eric Grimson at Prof. John Guttag ng MIT.
  
 24. & 26.
 Nov
 Sa mga sumusunod na pelikulang panayam na isinapubliko rin ng MIT sa Estados Unidos ay matutunghayan ang mas formal na paglalahad ng topics sa naunang serye ng panayam sa Algorithms at Complexity :  http://academicearth.org/courses/introduction-to-algorithms  mahalagang balik tanawan ang una at ikalawang pelikulang panayam. Ito ay ang isinapelikulang panayam nina Prof. Charles Leiserson at Prof. Eric Demaine, pawa ng MIT.
  
 01. & 03.
  Dec
 Mahalaga ring mabalik tanawan ang mga panayam sa Theory of Computations.  Ang mga sumusunod na pelikulang panayam ay matutunghayan sa pampublikong pahinang http://aduni.org/courses/theory/  o sa googlevideo.
  
 08. & 10.
  Dec
 Ang mga sumusunod na pelikulang panayam ay magbabahagi sa atin ng kalagayan ng suliraning P vs. NP.  Ang pelikulang panayam ay isinagawa ni Prof. Michael Sipser.
Ang pamagat ng panayam ay
The History and Status of the P and NP Question:
  
 15.  Dec   
 17.  Dec Pormal na unang pagkikita para sa Semestre.
 H. Adorna
 
  Holiday Season Break!
  

 DateTopics
Resource
 file
  Part 2 [Extended Lectures]
All Lectures will be based on the book of Prof. Sanjeev Arora et al [link]
  
 05. Jan
 Mathematical Preliminaries
  
 07. Jan
 The Class P and NP
  
 12. Jan
 NP Problems
  
 14. Jan
 NP Completeness
  
 19. Jan
 Reduction and Completeness (1)
  
 21. Jan
 Reduction and Completeness (2)
  
 26. Jan
 Diagonalization (*)
  
 28. Jan
 Time and Space Hierarchy (*)
  
 02. Feb
 Space Complexity
  ppt
 04. Feb
 The Class L and NL
  
 09.Feb PH and Alternation I
  
 11.Feb PH and Alternation II (*)
  
 16.Feb Boolean Circuit
  
 18.Feb
 Randomized Computation (*)
  
 23.Feb   
 25.FebNo Classes