Lecturer: László Végh

Location: Gerhard-Konow Hörsaal, Lennéstr 2

Times: Tuesday 16-18, Thursday 16-18

More info can be found at  https://www.or.uni-bonn.de/lectures/ss25/lgo_ss25.html

Lecturer: Matthias Kaul

Location: Seminarraum, Lennéstr 2

Times: Wednesday 14-16

 
Hardness of Approximation is one of the most active subfields of complexity theory and has been making steady progress in establishing which problems admit polynomial time approximation algorithms (up to reasonable hardness assumptions). For many problems, matching lower and upper bounds on their polynomial-time approximability have been shown, proving that often very simple algorithms -such as the algorithm of Goemans-Williamson or random sampling of a solution- achieve best-possible approximation ratios. This course will focus on giving a working understanding of the current state of the field, focusing on some standout results that represent well the standard techniques, as well as some applications of these foundational theorems.

Concretely the goal is to work on the following tentative list of topics:

Irit Dinur's proof of the PCP-theorem
Håstad's tight inapproximability theorems for some MaxCSPs
Fourier Analysis of Boolean Functions and Dictatorship Testing
Tight inapproximability of Max-Cut up to the Goemans-Williamson threshold under the Unique Games Conjecture
 

The course will be given in English; lecture notes are available here. Sources for the course will include the following textbooks and articles:

Irit Dinur. The PCP theorem by gap amplification. Journal of the ACM (2007)
Johan Håstad. Some optimal inapproximability results. Journal of the ACM (2001)
Subash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell. Optimal Inapproximability Results for MAX-CUT and Other 2-variable CSPs? Siam Journal on Computing (2007)
Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press (2014); ArXiv 2021

Lecturer:Hannaneh Akrami, Wenzheng Li, László Végh

Location: Seminarraum, Lennéstr 2

Times: Fridays 14-16. Approval talks: 16-18

Interested students are encouraged to contact Hannaneh Akrami at hakrami (at) uni-bonn.de. Students who cannot attend the planning meeting can still sign up by sending an email.

The schedule and more details can be found on the page https://www.laszlovegh.eu/fairness-seminar/

This seminar will explore foundational and contemporary research on the fair division of resources. Fair division theory addresses the challenge of allocating a set of resources among individuals (often referred to as agents) in a way that is considered ''fair'', despite their differing preferences. This problem is highly relevant in various real-world contexts, such as dividing inheritances, resolving business partnership dissolutions, settling divorce agreements, and allocating computational resources in cloud environments, to name a few.

The concept of fairness encompasses a variety of interpretations, which are broadly categorized into envy-based and share-based approaches. Additionally, the nature of the items being divided—whether divisible or indivisible, goods or chores—introduces further complexity. Depending on the fairness criteria and item characteristics, a wide range of questions arise regarding the fair allocation of resources.

In this seminar, we will examine several key scenarios and discuss the theoretical results and methods developed to address them. 

Lecturer:Hannaneh Akrami, Wenzheng Li, László Végh

Location: Seminarraum, Lennéstr 2

Times: Wednesday 14-16. Approval talks: 16-18

Interested students are encouraged to contact Hannaneh Akrami at hakrami (at) uni-bonn.de. Students who cannot attend the planning meeting can still sign up by sending an email.

The schedule and more details can be found on the page https://www.laszlovegh.eu/agt-seminar/

The seminar will cover selected chapters from the Algorithmic Game Theory book by Nisan, Roughgarden, Tardos, and Vazirani, available here.