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

εαρινό εξάμηνο 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
8/6/2017 Ι. Μουλίνος Machine Learning
15/6/2017 Ν. Λεονάρδος Communication Complexity
22/6/2017 A. Παναγιωτίδης BPP, AM (and the operator ∃ +)
29/6/2017 Μ. Κουβαράς Sum of Squares
6/7/2017 Π. Πατσιλινάκος Search Problems

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

Pseudorandomness & Derandomization

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 AC0. 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

Quantum Computation & Complexity

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