5 June - 11 June
Section outline
-
- 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