Θεωρητική Πληροφορική ΙΙ: Υπολογιστική Πολυπλοκότητα (ΣΗΜΜΥ, ΣΕΜΦΕ),
Δομική Πολυπλοκότητα (ΜΠΛΑ)
εαρινό εξάμηνο 2011-2012
Γενικά
Διδάσκοντες
- Στάθης Ζάχος, Καθηγητής ()
- Άρης Παγουρτζής, Επίκουρος Καθηγητής ()
Βοηθός διδασκαλίας
- Αντώνης Αντωνόπουλος ()
Έναρξη μαθήματος
Πέμπτη, 15 Μαρτίου 2012
Διαλέξεις
Πέμπτη 14:00-17:00, αίθουσα 1.1.31 (παλαιό) Κτίριο Ηλεκτρολόγων, Ε.Μ.Π.
Ώρες Γραφείου
- Τετάρτη, 5:00-7:00, Εργαστήριο Λογικής και Επιστήμης Υπολογισμών (CoReLab), Αίθουσα 1.1.3, Παλαιά Κτίρια Ηλεκτρολόγων
- Πέμπτη, 5:00-7:00 (μετά το μάθημα), Εργαστήριο Λογικής και Επιστήμης Υπολογισμών (CoReLab), Αίθουσα 1.1.3, Παλαιά Κτίρια Ηλεκτρολόγων
Προαπαιτούμενα
Μαθήματα σε Θεωρία Υπολογισιμότητας & Αλγόριθμους και Πολυπλοκότητα.
Περιεχόμενο μαθήματος
- Σχέσεις και αναγωγές μεταξύ κλάσεων πολυπλοκότητας. Ιεραρχίες (πολυωνυμική, προσεγγιστική κλπ).
- Διαλογικά Συστήματα Αποδείξεων (Interactibe Proofs): Private vs public coins, Arthur-Merlin Games, Arithmetization and IP=PSPACE, zero-knowledge etc.
- Πιθανοτικά Ελέγξιμες Αποδείξεις (PCPs): Constraint Satisfaction problems, low-degree testing, self-corrections of polynomials, PCP characterization of NP and NEXP, PCPs and Hardness of Approximations: Inapproximability results.
- Natural Proofs and Circuit Lower Bounds
- Counting Complexity: Main Classes, Valiant's and Toda's Theorems, Approximate Counting etc.
- Measure and Dimension in Complexity Classes
- Decision Trees
- Pseudorandomness: Pseudorandom Constructions, Expander Graphs, Applications to Complexity, Randomness Extractors.
- Derandomization of Complexity Classes: Basic introduction to the field, the nature of randomness in computation and mathematics, Non-Uniform Derandomization, Uniform Derandomization of BPP, RP, AM and AM∩coAM.
- Various Techniques and Notions in Structural Complexity Theory: Downward and Random self-reducibility, Bi-immunity, Mitoticity, sparse and tally sets, Density, Padding, Polynomial-time isomorphism, Infinity Often and Almost Everywhere Hierarchies, Hierarchies for semantic classes, Promise Problems, Reductions (Karp, Cook, 1-1, truth-table, query-monotonic) and relations among them, Arithmetization & Algebrization techniques, Tournament Divide & Conquer technique, Isolation technique, Witness Reduction technique, Random Restriction technique etc.
- Other Topics (to be selected by the participants): Hardness Amplification and Error-Correcting Codes, Alebraic Computation, Proof Complexity, Communication Complexity, Parameterized Complexity, Average-Case Complexity etc.
Βιβλιογραφία
- S. Arora and B. Barak, Complexity Theory: A Modern Approach, 2008, Princeton University. (draft available here.)
- O. Goldreich, Computational Complexity: A Conceptual Perspective, 2008, Cambridge University Press. (draft available here.)
- L. A. Hemaspaandra and M. Ogihara, The Complexity Theory Companion, 2002, Springer.
- L. Trevisan, Lecture Notes in Computational Complexity, 2002, UC Berkeley.
- S. Homer and A. L. Selman, Computability and Complexity Theory, 2001, Springer.
- C. H. Papadimitriou, Computational Complexity, 1994, Addison Wesley.
- M. R. Garey and D. S. Johnson, Computers and Intractability - A guide to the theory of NP-completeness,1979, Freeman.
Ανακοινώσεις
- [] Βαθμοί Ιουνίου 2012
- Εργασία (Σειρά Ασκήσεων)
- Προτεινόμενα θέματα (Syllabus)
- Το μάθημα θα διαρκέσει 17 εβδομάδες, και θα γίνει με με την μορφή ομιλιών-παρουσιάσεων.
Απαραίτητα για την προβιβάσιμη βαθμολογία στο μάθημα είναι: - (Τουλάχιστον) μία ομιλία-παρουσίαση από τα προτεινόμενα θέματα, ή με πρόταση του φοιτητή, αρκεί να είναι συγγενής με το αντικείμενο του μαθήματος.
- Παράδοση Εργασίας (θα ανακοινωθεί ένα μήνα πριν την λήξη του μαθήματος).
- Ικανοποιητική συμμετοχή στο μάθημα (παρουσίες).
Διαλέξεις - Παρουσιάσεις
| Η/Μ | Ομιλητής | Θέμα - Περιεχόμενο |
|---|---|---|
| 15/3/12 | Σ. Ζάχος |
Εισαγωγή - Διαδικαστικά Hierarchies of Complexity Classes (Slides) |
| 22/3/12 | Α. Αντωνόπουλος | Interactive Proof Systems: IPs, AMs, PCPs (Slides) Part 1: Interactive Proofs and Arthur-Merlin Games |
| 29/3/12 | Α. Αντωνόπουλος | Interactive Proof Systems: IPs, AMs, PCPs Part 2: Arithmetization (IP=PSPACE) & A Basic Introduction to PCPs |
| 5/4/12 | Θ. Λιανέας | Expanders and L=SL (Reingold's Theorem) |
| 26/4/12 | Α. Göbel | Complexity Classes of Counting Problems (Slides) |
| 3/5/12 | Α. Göbel Χ. Αγγελιδάκης |
Complexity Classes of Counting Problems (cont'd) PCPs, Hardness of Approximation & The Unique Games Conjecture (Slides) |
| 10/5/12 | Χ. Αγγελιδάκης | PCPs, Hardness of Approximation & The Unique Games Conjecture (cont'd) |
| 17/5/12 | Γ. Κοκκίνης Π. Γροντάς |
Natural Proofs (Slides) Pseudorandomness: Pseudorandom Generators (Slides) |
| 24/5/12 | Π. Γροντάς Α. Αντωνόπουλος |
Pseudorandom Generators (cont'd) Derandomization of Complexity Classes |
| 31/5/12 | Μ. Γεωργίου & Α. Ψωμάς |
Quantum Complexity (Slides) |
| 7/6/12 | Μ. Γεωργίου & Α. Ψωμάς Ε. Μπακάλη |
Quantum Complexity (cont'd) Pseudorandomness: Randomness Extractors |
| 14/6/12 | Ε. Μπακάλη | Pseudorandomness: Randomness Extractors (cont'd) |
| 21/6/12 | Π. Θεοφιλόπουλος Χ. Λίτσας |
Promise Problems (Slides) Worst vs. Average-Case Complexity in Lattice Problems (Slides) |
| 28/6/12 | Χ. Λίτσας Α. Göbel & Σ. Δεσποτάκης |
Worst vs. Average-Case Complexity in Lattice Problems (cont'd) A complexity dichotomy for counting Constraint Satisfaction Problems (#CSPs) (Slides) |
| 5/7/12 | Χ. Γαλανάκη Κ. Κοιλιάρης |
Algebrization: A new barrier in Complexity Theory (Slides) Measure & Dimension in Complexity Classes (Slides) |
| 12/7/12 | Α. Αντωνόπουλος | Expander Graphs & Applications to Computational Compexity (Slides) |
| 19/7/12 | Παρουσίαση Ασκήσεων |
Υλικό - Βιβλιογραφία
Interactive Proof Systems
- S. Goldwasser and M. Sipser, Private coins versus public coins in interactive proof systems, In Proceedings of the eighteenth annual ACM symposium on Theory of computing, STOC ’86, pages 59–68, New York, NY, USA, 1986. ACM.
- L. Babai and S. Moran, Arthur-Merlin Games: A randomized proof system, and a hierarchy of complexity classes, J. Comput. Syst. Sci., 36(2):254–276, 1988
- M. Fürer, O. Goldreich, Y. Mansour, M. Sipser and S. Zachos, On completeness and soundness in interactive proof systems, Advances in Computing Research: Randomness and Computation, JAI Press, 5:25-32, 1989
- A. Shamir, IP = PSPACE, J. ACM, 39:869–877, October 1992
- L. Babai and L. Fortnow, Arithmetization: A new method in structural complexity theory, Computational Complexity, 1:41–66, 1991
Counting Complexity
- Chapter 17 from [1]
- L. Fortnow,Counting complexity, In L. Hemaspaandra and A. Selman, editors, Complexity Theory Retrospective II, pages 81-107. Springer, 1997, Survey
- J. Torán, Counting the Number of Solutions, MFCS 1990: 121-134
- A. Pagourtzis and S. Zachos, The Complexity of Counting Functions with Easy Decision Version, In Proceedings of 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006), Lecture Notes in Computer Science 4162, pp. 741-752, Springer-Verlag
- L. Hemaspaandra, C. Homan, S. Kosub, K. Wagner, The Complexity of Computing the Size of an Interval, SIAM J. Comput. 36(5): 1264-1300 (2007)
(*The link is for arXiv's version) - E. Bampas, A. Göbel, A. Pagourtzis, A. Tentes, On the Connection between Interval Size Functions and Path Counting, TAMC 2009: 108-117
Probabilistically Checkable Proofs & Hardness of Approximation
- S. Arora, How NP got a new definition: a survey of probabilistically checkable proofs, CoRR cs.CC/0304038, 2003
- Prasad Raghavendra, Optimal algorithms and inapproximability results for every CSP?, STOC 2008: 245-254
- Lance Fortnow, John Rompel, Michael Sipser, On the Power of Multi-Prover Interactive Protocols, Theor. Comput. Sci. 134(2): 545-557 (1994)
- Irit Dinur, Probabilistically Checkable Proofs and Codes, Proceedings of the International Congress of Mathematicians, Hyderabad, India, 2010
- Uriel Feige, A Threshold of ln n for Approximating Set Cover, J. ACM 45(4): 634-652 (1998)
- Luca Trevisan, Inapproximability of Combinatorial Optimization Problems, CoRR cs.CC/0409043: (2004)
- Subhash Khot, On the Unique Games Conjecture (Invited Survey), IEEE Conference on Computational Complexity 2010: 99-121
Natural Proofs
- A.Razborov, S. Rudich, Natural Proofs, J. Comput. Syst. Sci. 55(1): 24-35 (1997)
- E. Allender, Cracks in the Defenses: Scouting Out Approaches on Circuit Lower Bounds, CSR 2008: 3-10
Pseudorandomness & Derandomization
- Luca Trevisan, Pseudorandomness and Combinatorial Constructions, CoRR abs/cs/0601100, 2006
- Oded Goldreich, Lecture Notes on Pseudorandomness - Part I (polynomial-time generators), 2000
- L. Trevisan, Lecture Notes on Pseudorandomness - Part II (derandomization), 2000.
- N. Nisan, A. Wigderson, Hardness vs Randomness, J. Comput. Syst. Sci., 49(2):149-167, 1994
- V. Kabanets, Derandomization: A Brief Overview, Bulletin of the European Association for Theoretical Computer Science, Number 76, pages 88-103, 2002
Expander Graphs
- S. Hoory, N. Linial and A. Wigderson, Expander Graphs and their applications, Bulletin of the American Mathematical Society, 43 (2006) 439--561
Applications to Complexity Theory
- I. Dinur, The PCP theorem by gap amplification, Journal of the ACM, 54(3):12, 2007
- O. Reingold, Undirected connectivity in log-space, Journal of the ACM, 55(4), 2008
Randomness Extractors
- R. Shaltiel, An Introduction to Randomness Extractors, In Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Part II, volume 67
Quantum Computation & Complexity
- Scott Aaronson's "Quantum Complexity" Course Lecture Notes
- Scott Aaronson's "Quantum Computing Since Democritus" Course
- Richard Cleve, An Introduction to Quantum Complexity Theory, coRR, 1999
- Ethan Bernstein, Umesh V. Vazirani: Quantum Complexity Theory, SIAM J. Comput. 26(5): 1411-1473 (1997)
- Tetsuro Nishino, An Introduction to Quantum Complexity Theory
- Larisse D. Voufo, Quantum Complexity Classes, Slides
- John Watrous, Quantum Computational Complexity, Encyclopedia of Complexity and Systems Science 2009: 7174-7201
Measure and Dimension in Complexity Classes
- Heribert Vollmer and Klaus W. Wagner, Measure one results in computational complexity theory, In Advances in Algorithms, Languages, and Complexity, pages 285–312, 1997
- Jack H. Lutz, Resource bounded measure, CoRR, abs/1101.5455, 2011
- Jack H. Lutz, Dimension in complexity classes, SIAM Journal on Computing, 32(5):1236–1259, 2003
- Xiaoyang Gu and Jack H. Lutz, Dimension characterizations of complexity classes, Computational Complexity, 17(4):459–474, 2008
- J.M. Hitchcock, J.H. Lutz, and E. Mayordomo, The fractal geometry of complexity classes, SIGACT News, 36:24–38, 2005