Fwd: [gdr-ifm] Minicourse, Kavitha Telikepalli

[Alexander SHEN]

(the topic sounds interesting, I don't know anything about the speaker, sorry)

-------- Forwarded Message --------

Subject:	[gdr-ifm] Minicourse, Kavitha Telikepalli
Date:	Mon, 6 May 2024 12:03:08 +0200
From:	Nabil Mustafa <mus...@lipn.univ-paris13.fr>
Reply-To:	Nabil Mustafa <mus...@lipn.univ-paris13.fr>
To:	gdr...@gdr-ifm.fr <gdr...@gdr-ifm.fr>

Dear Colleagues,

Prof. Kavitha Telikepalli (TIFR, India) will be giving a mini-course on popular matchings at USPN.

You are invited to attend, it will be broadcast at this link:

    https://bbb.lipn.univ-paris13.fr/b/ban-kpe-96w

Please find below an abstract of the mini-course.

Best wishes,

Nabil

-------------------------------------------------------------------

Lecture 1, Tuesday 07/05 at 16h : Introduction to popular matchings.

The problem of computing a stable matching in a bipartite graph is an old and well-studied problem. Gale and Shapley showed in 1962 that such a matching always exists and can be efficiently computed. This is a classical result in algorithms with many applications in economics and computer science. Stability is a strong and rather restrictive notion. This series of talks will be on a relaxation of stability called "popularity". In the first talk we will see simple and efficient algorithms for some popular matching problems. No background in algorithms or matching theory will be assumed.

-------------------------------------------------------------------

Lecture 2, Tuesday 14/05 at 14h: Popular matchings and optimality.

In this talk we will consider algorithms for finding optimal popular matchings. While it is easy to find max-size popular matchings, it is NP-hard to find a min-cost popular matching. This motivates us to relax popularity to a weaker notion called "quasi-popularity". Describing the popular and quasi-popular matching polytopes is hard, but there is an easy-to-describe integral polytope sandwiched between these two hard ones. So we can efficiently find a quasi-popular matching of cost at most that of a min-cost popular matching.

-------------------------------------------------------------------

Lecture 3, Tuesday 21/05 at 14h: Popular assignments and extensions.

This talk will be on popular matchings in the one-sided preferences model. Popular matchings need not always exist in this model and there is a simple combinatorial algorithm to decide if one exists. We will see an LP-duality inspired algorithm for the more general problem of deciding if a popular assignment (i.e., a popular maximum-matching) exists or not. This algorithm can be generalized to solve the popular common base problem in the intersection of two matroids where one matroid is the partition matroid, this implies the popular arborescence problem (relevant in liquid democracy) can be solved efficiently.

This mini-course is supported by the École Universitaire de Recherche de Paris Nord en Mathématiques et Informatique; https://eur.univ-paris13.fr/events/popular-matchings-mini-course-by-kavitha-telikepalli-tata-institute/.

[Nikolay Vereshchagin]

Date: May 13, 2024

Time: 18:30 (Moscow time), 17:30 (Paris time)

Speakers: Georgiy Khaziev, Umar Nalgiev

Title: Master thesis presentation (in Russian). Предзащита магистерских диссертаций.

Abstract:

Георгий Хазиев расскажет о комбинаторной интерпретации неравенств для энтропий трех случайных величин. Его результат состоит в том, что комбинаторная интерпретация любого шенноновского неравенства, полученного сложением базисных неравенств от переменных A,B,C (без умножения на дробные коэффициентами), истинна как есть, то есть, без поправочных множителей. 

Умар Нальгиев расскажет о барьерах при решении проблемы P vs NP (релятивизация и алгебризация).

https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

--
Вы получили это сообщение, поскольку подписаны на группу "Kolmogorov seminar on complexity".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес kolmogorov-seminar-on-...@googlegroups.com.
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/kolmogorov-seminar-on-complexity/8a666ad2-5884-4998-9380-bac20d174086%40lirmm.fr.

--

Н.В.