Sparsity

winter term 2019/20

Instructors

Classes

Lectures: | Fridays, 12^{15}-13^{45}, room 3160 |

Tutorials: | Fridays, 14^{15}-15^{45}, room 3160 |

Documents and links

Evaluation criteria

Rules and list of topics for the exam

Reservation of time slots for the exam

Website of the previous edition

Youtube channel with lectures

Tutorials for algomanet lectures

Classes at MBL'19

Rules and list of topics for the exam

Reservation of time slots for the exam

Website of the previous edition

Youtube channel with lectures

Tutorials for algomanet lectures

Classes at MBL'19

News

24.01.20 | Notes for the fourteenth lecture, fourteenth tutorial |

17.01.20 | Notes for the thirteenth lecture, thirteenth tutorial |

08.01.20 | Publication of sixth homework, notes for the twelfth lecture, twelfth tutorial |

18.12.19 | Notes for the eleventh lecture, eleventh tutorial |

13.12.19 | Publication of fifth homework, notes for the tenth lecture, tenth tutorial |

04.12.19 | Notes for the ninth lecture, ninth tutorial |

29.11.19 | Eigth tutorial |

22.11.19 | Publication of fourth homework, seventh tutorial, and notes for the seventh lecture |

10.11.19 | Sixth tutorial, notes for the sixth and the eight lecture, and selected solutions |

08.11.19 | Publication of third homework, fifth tutorial, notes for the fifth lecture |

25.10.19 | Publication of second homework, fourth tutorial, notes for the fourth lecture |

19.10.19 | Third tutorials, notes for the third lecture |

11.10.19 | Second tutorials, notes for the second lecture, link to videos of lectures |

04.10.19 | Publication of first homework, first tutorial, notes for the first lecture |

Homeworks

Homework 1: | Introduction and definitions | Deadline: October 25^{th} |

Homework 2: | Measuring sparsity | Deadline: November 14^{th} |

Homework 3: | Generalized coloring numbers | Deadline: November 28^{th} |

Homework 4: | Structural measures | Deadline: December 12^{th} |

Homework 5: | Uniform quasi-wideness and friends | Deadline: January 16^{th} |

Homework 6: | VC dimension and polynomial expansion | Deadline: January 30^{th} |

Selected students' solutions |

Lecture notes

Chapter 1: | Measuring sparsity | (Lectures 1, 2, and 3) |

Chapter 2: | Structural measures | (Lectures 4, 5, 6, and 7) |

Chapter 3: | Model-checking FO | (Lecture 8) |

Chapter 4: | Uniform quasi-wideness | (Lectures 9 and 10) |

Chapter 5: | Beyond Sparsity | (Lectures 11 and 12) |

Chapter 6: | Polynomial expansion | (Lectures 13 and 14) |

Tutorials

Tutorial 1: | Introduction and motivating examples |

Tutorial 2: | Shallow minors and main definitions |

Tutorial 3: | Measuring sparsity continued |

Tutorial 4: | Introduction to generalized coloring numbers |

Tutorial 5: | Generalized coloring numbers |

Tutorial 6: | Domination, independence, and neighborhood complexity |

Tutorial 7: | Low treedepth colorings |

Tutorial 8: | FO model-checking, low shrubdepth colorings |

Tutorial 9: | Low shrubdepth colorings, uniform quasi-wideness |

Tutorial 10: | Splitter Game and applications of uqw |

Tutorial 11: | Ladders and VC dimension |

Tutorial 12: | VC dimension and approximation of hitting sets |

Tutorial 13: | Polynomial expansion |

Tutorial 14: | Applications of polynomial expansion |

Solutions to selected problems from tutorials |