Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- teaching:ipcomsoc2324 [2024/03/06 23:44] – Martin Koutecky
+++ teaching:ipcomsoc2324 [2024/05/17 15:10] (aktuální) – Martin Koutecky
@@ Řádek 8: / Řádek 8: @@
 | 26. 2. | Fixed dimension IPs, intro to iterative augmentation. **[LN up to Lemma 7]** |
 | 4. 3. | More details for iterative augmentation. **[LN up to Lemma 16]**|
-| 11. 3. | //Plan: norm bound, DP for case of small  $m$  and  $\|A\|_\infty$  **[LN Lemma 16, 17]**; read **[LN 3.4]** without proofs.//|
+| 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: ====