Αρχική σελίδα | Επικοινωνία | Πίνακας πλοήγησης |

Προχωρημένα Θέματα Αλγορίθμων (και Πολυπλοκότητας)

εαρινό εξάμηνο 2016-2017

● Γενικά ● Ανακοινώσεις ● Διαλέξεις-Παρουσιάσεις ● Υλικό-Βιβλιογραφία ●

Γενικά

Διδάσκοντες

• Στάθης Ζάχος, Καθηγητής ()
• Άρης Παγουρτζής, Αναπληρωτής Καθηγητής ()

Βοηθός διδασκαλίας

• Αγγελική Χαλκή, Υ.Δ. ()

Έναρξη μαθήματος

Πέμπτη, 2 Μαρτίου 2017

Διαλέξεις

Πέμπτη 16:00-20:00, αίθουσα 1.1.31 (παλαιό) Κτίριο Ηλεκτρολόγων, Ε.Μ.Π.

Ώρες Γραφείου

• Πέμπτη, 14:00-16:00, Εργαστήριο Λογικής και Επιστήμης Υπολογισμών (CoReLab), Αίθουσα 1.1.3, Παλαιά Κτίρια Ηλεκτρολόγων

Προαπαιτούμενα

Μαθήματα σε Θεωρία Υπολογισιμότητας, Αλγορίθμων και Πολυπλοκότητας.

Ανακοινώσεις

Διαλέξεις - Παρουσιάσεις

Η/Μ	Ομιλητής	Θέμα - Περιεχόμενο
2/3/2017	Β. Λίβανος Ε. Μπακάλη	Εισαγωγή-Διαδικαστικά Opinion Dynamics (slides) Pseudorandomness (slides)
9/3/2017	Α. Αντωνόπουλος Π. Παπαδόπουλος	Oracles, Relativizing, AM, IP=PSPACE (slides) Circuit Complexity Classes and Complete Problems (slides)
16/3/2017	Π. Παπαδόπουλος	PARITY ∉ AC0 Ryan Williams' Algorithm for ACC0-SAT (slides)
23/3/2017	Π. Παπαδόπουλος	Παρουσίαση διπλωματικής με θέμα "Ενοποίηση φυσικών και σχετικιστικών αποδείξεων για νέα κάτω φράγματα" Φυσικές Αποδείξεις NEXP-συμπυκνώσεις Μη ύπαρξη σύντομων κυκλωμάτων
30/3/2017	Π. Παπαδόπουλος	Αποτελέσματα και ουσία του αλγορίθμου του Ryan Williams NEXP ⊈ ACC0 ENP ⊈ ACC0 (2nδ size) Παραλλαγές MCSP, CAPP (σχέση NEXP με BPP)
6/4/2017	A. Χαλκή	Complexity of counting: Subclasses of #P (slides)
27/4/2017	Δ. Μυρισιώτης	Deutsch’s Algorithm (slides)
4/5/2017	Α. Ζαχαράκης	Intoduction to Lattices (slides)
11/5/2017	B. Mαργώνης	PCP and Hardness of Approximation (slides)
18/5/2017	Α. Aντωνόπουλος	Algorithmic Information Theory and Randomness (slides)
25/5/2017	NO CLASS	10th International Conference on Algorithms and Complexity (CIAC 2017)
1/6/2017	Π. Γροντάς	ZK-SNARKS (slides)
8/6/2017	Ι. Μουλίνος	Machine Learning (slides)
15/6/2017	Ν. Λεονάρδος	Communication Complexity
28/6/2017	Σ. Πετσαλάκης	Lattices
29/6/2017	Π. Πατσιλινάκος	Local Search (slides)
3/7/2017	M. Κουβαράς	Sum of Squares

Υλικό - Βιβλιογραφία

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.

Circuit Complexity

• Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, New York, NY, USA, 1st edition, 2009. (chapters 6, 14, 20)
• Peter Clote and Evangelos Kranakis. Boolean Functions and Computation Models. Texts in Theoretical Computer Science. An EATCS Series. 2002.
• Claude. E. Shannon. The synthesis of two-terminal switching circuits. Bell System Technical Journal, 28(1):59-98, 1949.
• Gudmund Skovbjerg Frandsen and Peter Bro Miltersen. Reviewing bounds on the circuit size of the hardest functions. Information Processing Letters, 95(2):354-357, 2005.
• Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC'71, pages 151-158, New York, NY, USA, 1971. ACM.
• Martin Fürer. The tight deterministic time hierarchy. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC '82, pages 8-16, New York, NY, USA, 1982. ACM.
• Merrick Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical systems theory, 17(1):13-27, 1984. Preliminary version FOCS '81.
• J Håstad. Almost optimal lower bounds for small depth circuits. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC '86, pages 6-20, New York, NY, USA, 1986. ACM.
• A.C.C. Yao. On ACC and threshold circuits. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 00:619-627 vol.2, 1990.
• Eric Allender and Vivek Gore. On strong separations from AC⁰. In Fundamentals of Computation Theory, 8th International Symposium, FCT '91, Gosen, Germany, pages 1-15, 1991.
• Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. In search of an easy witness: Exponential time vs. probabilistic polynomial time. J. Comput. Syst. Sci., 65(4):672-694, December 2002.
• R. Williams. Non-uniform acc circuit lower bounds. In 2011 IEEE 26th Annual Conference on Computational Complexity, pages 115-125, June 2011.
• Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. SIAM Journal on Computing, 42(3):1218-1244, 2013.

Counting Complexity

• Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, New York, NY, USA, 1st edition, 2009. (chapter 17).
• 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.

Quantum Computation & Complexity

• Scott Aaronson's "Quantum Complexity" Course Lecture Notes.
• Scott Aaronson's "Quantum Computing Since Democritus" Course.
• Scott Aaronson's "The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes" Lecture Notes.
• Andrew Childs' Lecture Notes.
• 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.

Algorithmic Information Theory

• Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, Springer, New York, 3rd edition, 2007.
• Cristian Calude, Information and Randomness: An Algorithmic Perspective. Springer, Berlin, 2nd edition, 2002.
• Rod Downey and Denis Hirschfeldt, Algorithmic Randomness and Complexity. Springer, Berlin, 2007.
• Osamu Watanabe, Kolmogorov Complexity and Computational Complexity. Springer-Verlag, 1992.
• Chaitin, G.J, Algorithmic information theory. IBM Journal of Research and Development, v.21, No. 4, 350359, 1977 Kolmogorov Complexity and Computational Complexity, Lance Fortnow.
• Sophie Laplante, A Kolmogorov Complexity Proof of Hastad Switching Lemma: An Exposition.

Communication Complexity

• Eyal Kushilevitz, Noam Nisan, Communication Complexity, Cambridge University Press, 1997.

Local Search

• W. Michiels, E.H.L. Aarts, and J.H.M.Korst. Theoretical aspects of local search. Springer, 2007.
• S. Parsons. Algorithmic Game Theory by Noam Nisan, Tim Roughgarden, Éva Tardos and Vijay V. Vazirani. Cambridge university press, 2011.
• A. A. Schaffer and M. Yannakakis. Simple local search problems that are hard to solve SIAM J, 1991.
• A. Fabrikant, C.H. Papadimitriou, and K. Talwar. The complexity of pure nash equilibria. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June13-16,2004, pages 604–612, 2004.