G204 Tutorials

The purpose of these tutorials is to strengthen mathematical and algorithmic thinking. The topics can be interesting algorithms (not necessary state-of-the-art), proofs of some fundamental theorems, introduction to advanced methods or discussion about a state-of-the-art paper (in this case, all the attendees are expected to read the corresponding paper beforehand - if you do not read it do not attend the tutorial). The tutorials will take place every two weeks (see the "IIG group seminar" calendar). The length of each tutorial should be approximately 15-30 minutes. The tutorials should not be exclusively about your current work/research, for that we have IIG seminars.

Calendar link (ICS) Calendar link (html)

The cyclic order of the speakers is following:

1. István Módos
2. Aasem Ahmad
3. Antonín Novák
4. Libor Bukata
5. Jan Dvořák
6. Aня Mинаева <-- next speaker

If you don't have any ideas about your tutorial's topic, here are some suggestions:

• Network simplex
• AKS primality test
• Survey on cutting planes

Supplementary materials for the past tutorials:

• Istvan Modos - Introduction to matroids
  • Jeff Erickson - Matroids (the tutorial was heavily inspired by these lecture notes - beware, proofs contain small errors but the ideas are correct IMHO)
  • David L. Neel and Nancy Ann Neudauer - Matroids You Have Known
• Antonín Novák - Approximation algorithms 1
  • Vijay V. Vazirani - Approximation Algorithms [1]
  • UG-hardness
  • Problem Complexity ZOO
• Jan Dvořák - SMT Problem and its solvers
  • Presentation
  • Z3 Solver
  • List of SMT Solvers and its features
• Istvan Modos - Augmented Lagrangian Method
  • Penalty function and Augmented Lagrangian methods (short version)
  • Summary of unconstrained optimization. Optimization with constraints
  • Penalty function and Augmented Lagrangian methods (long version)
• Antonín Novák - Branch and Cut
  • Structure of a simple scheduling polyhedron

Topics of the past tutorials:

• Newton method
• Benders Decomposition
• Interior point method
• Closed-form formula for counting spanning trees
• Totally unimodular matrices
• Fourier-Motzkin elimination
• Distributed shortest path algorithms
• Independent vertices
• Polynomial algorithm for LP
• Matroids
• Semidefinite Programming
• Approximation algorithms
• Trainspotting
• SMT Problem
• Augmented Lagrangian Method
• Branch and Cut
• Farkas Lemma