Θεωρητική Πληροφορική ΙΙ:
Προχωρημένα Θέματα Αλγορίθμων και Πολυπλοκότητας
εαρινό εξάμηνο 2013-2014
Γενικά
Διδάσκοντες
- Στάθης Ζάχος, Καθηγητής ()
- Άρης Παγουρτζής, Επίκουρος Καθηγητής ()
Βοηθός διδασκαλίας
- Αντώνης Αντωνόπουλος ()
Έναρξη μαθήματος
Πέμπτη, 8 Μαΐου 2014
Διαλέξεις
Πέμπτη 15:00-19:00, αίθουσα 1.1.31 (παλαιό) Κτίριο Ηλεκτρολόγων, Ε.Μ.Π.
Ώρες Γραφείου
- Δευτέρα, 11:00-13:00, Εργαστήριο Λογικής και Επιστήμης Υπολογισμών (CoReLab), Αίθουσα 1.1.3, Παλαιά Κτίρια Ηλεκτρολόγων
- Παρασκευή, 12:00-14:00 (μετά το μάθημα), Εργαστήριο Λογικής και Επιστήμης Υπολογισμών (CoReLab), Αίθουσα 1.1.3, Παλαιά Κτίρια Ηλεκτρολόγων
Προαπαιτούμενα
Μαθήματα σε Θεωρία Υπολογισιμότητας & Αλγόριθμους και Πολυπλοκότητα.
Βιβλιογραφία
- 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.
Ανακοινώσεις
- [ΠΡΟΣΟΧΗ!] Λεπτομέρειες και υλικό για την βιβλιογραφία του μαθήματος, όπως και η ανακοίνωση και παράδοση της τελικής εργασίας θα γίνονται αποκλειστικά μέσα από το moodle του μαθήματος. Οδηγίες για την εγγραφή έχουν έρθει στο mail σας.
- Το μάθημα θα γίνει με με την μορφή ομιλιών-παρουσιάσεων.
Απαραίτητα για την προβιβάσιμη βαθμολογία στο μάθημα είναι: - (Τουλάχιστον) μία ομιλία-παρουσίαση από τα προτεινόμενα θέματα, ή με πρόταση του φοιτητή, αρκεί να είναι συγγενής με το αντικείμενο του μαθήματος.
- Παράδοση Εργασίας.
- Ικανοποιητική συμμετοχή στο μάθημα (παρουσίες).
Διαλέξεις - Παρουσιάσεις
(Λεπτομέρειες στο
)
| Η/Μ | Ομιλητής | Θέμα - Περιεχόμενο |
|---|---|---|
| 8/5/2014 | Σ. Ζάχος Α. Αντωνόπουλος |
Εισαγωγή - Διαδικαστικά Hierarchies of Complexity Classes Uniform Derandomization of Complexity Classes (slides) |
| 15/5/2014 | Α. Αντωνόπουλος | Uniform Derandomization of Complexity Classes (cont'd) (slides) |
| 22/5/2014 | Α. Παγουρτζής Α. Αντωνόπουλος |
Counting with easy decision and the class TotP Counting Complexity: Gaps and Toda's Theorem (slides) |
| 29/5/2014 | Γ. Νέμπαρης Μ. Ζαμπετάκης |
Counting algorithms and Complexity: A brief overview of the field (slides) An Introduction to Mechanism Design |
| 5/6/2014 | E. Μπακάλη S. Obraztsova |
Hardness of Approximations Computational Social Choice |
| 12/6/2014 | Δ. Χατζηδημητρίου S. Obraztsova |
TBA Computational Social Choice |
| 19/6/2014 | Ζ. Αβαρικιώτη S. Obraztsova |
Parameterized Complexity Computational Social Choice |
| 26/6/2014 | X. Τζόβας Μ. Ζαμπετάκης Λ. Ζακυνθινού |
Decision Trees ΤΒΑ ΤΒΑ |
| 3/7/2014 | Ι. Ψαρρός Α. Μάντης Π. Τελώνη |
ΤΒΑ Average-Case Complexity Circuit Complexity |
| 10/7/2014 | Κ. Νικολιδάκη Δ. Μυρισιώτης Σ. Μανιάτης |
Pseudorandomness The Witness Reduction Technique Complexity of Search Problems |
| 17/7/2014 | Δ. Μπογιόκας Α. Αγγελόπουλος Ε. Μπακάλη |
Counting classes & Leaf Languages Games & Puzzles Αλλαγές Φάσης - Ising Model |
| 24/7/2014 | Γ. Καρυστιανός Γ. Ζηρδέλης |
Derandomization TBA |
Υλικό - Βιβλιογραφία
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