====== Integer Programming and Computational Social Choice 24/25 ======


{{tablelayout?colwidth="100px,-"&rowsHeaderSource=1&rowsVisible=100&float=left}}
^ data ^ what was taught [resources] ^
| 17. 2. | Fixed dimension IPs, birds-eye overview of iterative augmentation. **[LN 1-2]**|
| 24. 2. | Iterative augmentation: Graver basis, positive sum property **[LN 3, until Prop 6]**|
| 3. 3. | Iterative augmentation: convergence, (AugIP), feasibility **[LN 3, until end of 3.1]**|
| 10. 3. | Steinitz Lemma, basic $g_1(A)$ bound, sketch of extension to $n$-folds. **[LN 3, until Thm 17]**|
| 17. 3. | Basic (AugIP) DP, DP for $n$-folds **[LN 3, until Lemma 19]**|
| 24. 3. | Klein's lemma and $2$-stage norm bound, $2$-stage branching **[LN 3.5]**|
| 31. 3. | Extensions: proximity theorems, coefficient reduction, strongly-poly algorithms, sensitivity **[LN 4 + 5]**|
| 7. 4. |  Intro to voting: election, voting rule, some examples [[https://research.koutecky.name/logseq-export/#/page/juk%20p%C5%99edn%C3%A1%C5%A1ka%202024|(czech notes)]]; <typo fv:small-caps>YoungScore</typo> and <typo fv:small-caps>DodgsonScore</typo> as fixed-dimension ILPs (double-exponential algorithm), and as few rows / $n$-fold ILPs (single-exponential algorithm). <typo fv:small-caps>DodgsonScore</typo> is the same thing as unit cost Condorcet-<typo fv:small-caps>Swap Bribery</typo>.|
| 14. 4. | Bribery and manipulation actions as moves in societies, various voting rules, FPT algorithms. [[https://arxiv.org/abs/1801.09584|arxiv]]|
| 21. 4. | //Cancelled - Easter Monday//|
| 28. 4. | Presburger Arithmetic, Cooper's Algorithm, and Multi-party Campaigning [[https://arxiv.org/abs/2005.04455|arxiv]]|
| 5. 5. | Opinion Diffusion [[https://academic.oup.com/logcom/article/32/6/1162/6550815?guestAccessKey=b4db15d0-92c1-47c7-a095-87db25857df7&login=false|JLogCom]]|
| 13. 5. | Fine-grained liquid democracy for cummulative ballots [[https://arxiv.org/abs/2208.14441|arxiv]]|

/*
| 4. 3. | More details for iterative augmentation. **[LN up to Lemma 16]**|
| 11. 3. | Norm bound, DP for case of small $m$ and $\|A\|_\infty$ **[LN Lemma 16, 17]**; treedepth, block-structured matrices **[LN 3.4]**; norm bound for $n$-fold IPs **[LN Lemma 29]**|
| 18. 3. | norm bounds and augmentation IP algorithms for $n$-fold and $2$-stage stochastic IPs [LN 3.5.1 and 3.6]|
| 25. 3. | Extensions: proximity theorems, coefficient reduction, strongly-poly algorithms, sensitivity [LN 4 + 5]| 
| 1. 4. | //Easter Monday//|
| 8. 4. | Intro to voting: election, voting rule, some examples **[LN 6.1-6.3]**; <typo fv:small-caps>YoungScore</typo> and <typo fv:small-caps>DodgsonScore</typo> as fixed-dimension ILPs (double-exponential algorithm), and as few rows / $n$-fold ILPs (single-exponential algorithm). <typo fv:small-caps>DodgsonScore</typo> is the same thing as unit cost Condorcet-<typo fv:small-caps>Swap Bribery</typo>. Similar formulations are in **[LN 8.1]**. |
| 15. 4. | //Cancelled - KAM/IUUK spring school//|
| 22. 4. | Bribery and manipulation actions as moves in societies, various voting rules, FPT algorithms.|
| 29. 4. | More voting rules; what's the deal with Young-<typo fv:small-caps>Swap Bribery</typo>; define <typo fv:small-caps>Campaigning Game</typo>, connect it to Presburger Arithmetic.|
| 6. 5. | Cooper's algorithm for Presburger Arithmetic [[http://www2.imm.dtu.dk/courses/02917/Presburger1.pdf|slides]], discuss applications.|
| 13. 5. | Opinion diffusion|
| 20. 5. | Wrap up|
*/


==== Resources: ====


  * **{{:teaching:ipcomsoc2425:stfa-notes.pdf|[LN]}}**: Lecture notes (hopefully continuously updated 😅). [[https://gitlab.mff.cuni.cz/komarej3/selected-topics-in-algorithms/-/jobs/artifacts/master/raw/martin-notes/stfa-notes.pdf?job=build_pdf|autogenerated PDF (login required)]]


Eventually (😅😅😅) I will post lecture notes here.