Προχωρημένα Θέματα Αλγορίθμων και Πολυπλοκότητας
Περιγραφή εβδομάδας
- Εαρινό Εξάμηνο 2013-2014
- 8 May - 14 May
8 May - 14 May
Εισαγωγή - Διαδικαστικά
- Σ. Ζάχος: Hierarchies of Complexity Classes
- Α. Αντωνόπουλος: Uniform Derandomization of Complexity Classes
Χρήσιμο Υλικό:
- 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
- Σ. Ζάχος: Hierarchies of Complexity Classes
- 15 May - 21 May
- 22 May - 28 May
22 May - 28 May
- Α. Παγουρτζής: Counting with easy decision and the class TotP
Υλικό:
- Aris Pagourtzis, Stathis Zachos: The Complexity of Counting Functions with Easy Decision Version. MFCS 2006: 741-752 - Α. Αντωνόπουλος: Counting Complexity: Gaps and Toda's Theorem
- Α. Παγουρτζής: Counting with easy decision and the class TotP
- 29 May - 4 June
29 May - 4 June
- Γ. Νέμπαρης: Counting algorithms and Complexity: A brief overview of the field
- Μ. Ζαμπετάκης: An Introduction to Mechanism Design
- 5 June - 11 June
5 June - 11 June
- S. Obraztsova: Computational Social Choice
That is 2 quite good sets of slides, a survey paper and a paper about STV NP-hardness:
http://www.cs.duke.edu/courses/fall09/cps296.1/csecon_voting.pdf
http://staff.science.uva.nl/~ulle/teaching/comsoc/2009/slides/comsoc-vote-complexity.pdf
http://www.aaai.org/ojs/index.php/aimagazine/article/view/2314/2180
http://www2.isye.gatech.edu/~jjb/papers/stv.pdf
About tie-breaking Edith wrote good survey in the beginning of our paper:
http://www1.spms.ntu.edu.sg/~eelkind/ties.pdf
- E. Μπακάλη: Hardness of Approximations
Βασισμένο στα παρακάτω Lecture Notes από το μάθημα "Probabilistically Checkable Proofs and Hardness of Approximation" του S. Khot.
Lecture 1 (Basic definitions)
Lecture 2 (Equivalence of PCP Theorem to inapproximability of MAX-3SAT)
Lecture 3 (Hardness of Set Cover)
Lecture 4 (Hastad’s 3-bit PCP)
Lecture 5 (Hastad’s 3-bit PCP continued)
Lecture 6 (Hardness of Minimum distance of code)
Lecture 7 (Hardness of Clique, FGLSS)
- S. Obraztsova: Computational Social Choice
- 12 June - 18 June
12 June - 18 June
- S. Obraztsova: Computational Social Choice
That is a link to the Jerome Lang tutorial at IJCAI-2011:
http://ijcai-11.iiia.csic.es/files/proceedings/T09-ijcai11-tutorial-t9.pdf - Δ. Χατζηδημητρίου: Parameterized Complexity Classes and Hierarchies
- S. Obraztsova: Computational Social Choice
- 19 June - 25 June
19 June - 25 June
- S. Obraztsova: Computational Social Choice
References:
1) Iterative voting.
Reshef Meir, Maria Polukarov, Jeffrey S. Rosenschein, and Nicholas R.
Jennings "Convergence to Equilibria in Plurality Voting."
Reyhaneh Reyhani, Mark C. Wilson "Best Reply Dynamics for Scoring
Rules." This paper is quite easy reading.
2) Voting one-shot game, players=voters
David Robert Martin Thompson, Omer Lev, Kevin Leyton-Brown, Jeffrey S.
Rosenschein "Empirical analysis of plurality election equilibria."
Svetlana Obraztsova, Evangelos Markakis, David R. M. Thompson:
Plurality Voting with Truth-Biased Agents.
Zinovi Rabinovich, Svetlana Obraztsova, Omer Lev, Evangelos Markakis
and Jeffrey Rosenschein "Analysis of Equilibria in Iterative Voting
Schemes"
3) Voting one-shot game, players=candidates.
Jérôme Lang, Nicolas Maudet, Maria Polukarov: New Results on
Equilibria in Strategic Candidacy. - Δ. Χατζηδημητρίου: Parameterized Complexity Classes and Hierarchies (cont'd)
- S. Obraztsova: Computational Social Choice
- 26 June - 2 July
26 June - 2 July
- Ζ. Αβαρικιώτη: Parameterized Maximum Path Coloring
- X. Τζόβας: Decision Trees
- Λ. Ζακυνθινού: Communication Complexity
- 3 July - 9 July
3 July - 9 July
- Α. Μάντης: Average-Case Complexity
- Π. Τελώνη: Quantum Complexity
- Μ. Ζαμπετάκης: Smoothed Analysis of Algorithms
- 10 July - 16 July
10 July - 16 July
- Π. Τελώνη: Quantum Complexity (cont'd)
- Α. Μάντης: Average-Case Complexity (cont'd)
- Δ. Μυρισιώτης: Structural Complexity: The Witness Reduction Technique
- 17 July - 23 July
17 July - 23 July
- Σ. Μανιάτης: The Complexity of Search Problems
- Κ. Νικολιδάκη: Pseudorandomness
- A. Αγγελόπουλος: The Complexity of Games and Puzzles
- Ε. Μπακάλη: Phase Transitions
- 24 July - 30 July
24 July - 30 July
- Γ. Ζηρδέλης: Expanders and Application to Complexity
- Π. Γροντάς: Convergence in Iterative Voting