MK's wiki

Uživatelské nástroje

Nástroje pro tento web

Historie:
teaching:ipcomsoc2425

Rozdíly

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

Odkaz na výstup diff

Obě strany předchozí revizePředchozí verze
Následující verze		Předchozí verze
teaching:ipcomsoc2425 [2025/05/10 21:14] – updated recap of covered material Martin Kouteckyteaching:ipcomsoc2425 [2025/05/15 08:53] (aktuální) – Martin Koutecky
Řádek 4: Řádek 4:
 {{tablelayout?colwidth="100px,-"&rowsHeaderSource=1&rowsVisible=100&float=left}} {{tablelayout?colwidth="100px,-"&rowsHeaderSource=1&rowsVisible=100&float=left}}
 ^ data ^ what was taught [resources] ^ ^ data ^ what was taught [resources] ^
-| 17. 2. | Fixed dimension IPs, birds-eye overview of iterative augmentation.| +| 17. 2. | Fixed dimension IPs, birds-eye overview of iterative augmentation. **[LN 1-2]**| 
-| 24. 2. | Iterative augmentation: Graver basis, positive sum property | +| 24. 2. | Iterative augmentation: Graver basis, positive sum property **[LN 3, until Prop 6]**| 
-| 3. 3. | Iterative augmentation: convergence, (AugIP), feasibility | +| 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.| +| 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| +| 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 | +| 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]| +| 31. 3. | Extensions: proximity theorems, coefficient reduction, strongly-poly algorithms, sensitivity **[LN 4 + 5]**| 
-| 7. 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]**.| +| 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.|+| 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//| | 21. 4. | //Cancelled - Easter Monday//|
-| 28. 4. | Presburger Arithmetic, Cooper's Algorithm, and Multi-party Campaigning | +| 28. 4. | Presburger Arithmetic, Cooper's Algorithm, and Multi-party Campaigning [[https://arxiv.org/abs/2005.04455|arxiv]]| 
-| 5. 5. | Opinion Diffusion |+| 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]]|
  
 /* /*
teaching/ipcomsoc2425.1746911665.txt.gz · Poslední úprava: autor: Martin Koutecky