BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:International School-conference in Algorithms\, Combinatorics\, an
d Complexity
DTSTART;VALUE=DATE-TIME:20210524T070000Z
DTEND;VALUE=DATE-TIME:20210528T180000Z
DTSTAMP;VALUE=DATE-TIME:20220521T093140Z
UID:indico-event-199@indico.eimi.ru
DESCRIPTION:School in Algorithms\, Combinatorics\, and Complexity\n\nMay 2
4 - May 28\, 2021\n\nAn advanced school for young researchers featuring t
hree minicourses in vibrant areas of mathematics and computer science. T
he target audience includes graduate\, master\, and senior bachelor studen
ts of any mathematical speciality.\n\n\nLecturers:\n\n\n \n \n \n \n
\n \n \n Maria Chudnovsky\n Fedor Fomin\n Madhu Sudan\n \n \n
Princeton University\n University of Bergen\n Harvard University\n
\n \n\n\n \n\nCourses\n\n\nForbidding Induced Subgraphs (Maria Chudnovsky
)\n\nThe study of the structure of graphs with certain induced subgraphs f
orbidden has been an active area of research in graph theory in recent yea
rs\, after the long standing Strong Perfect Graph Conjecture was proved us
ing structural methods. The goal of this course is to cover some of the re
cent developments in the area. We will start with simple theorems about fo
rbidden induced subgraphs\, and work our way up to the latest research res
ults. The topics will include perfect graphs\, claw-free graphs\, coloring
graphs with forbidden induced subgraphs\, algorithms for detecting induce
d subgraphs and others.\n\n\nRepresentative Families and Algorithms (Fedo
r Fomin)\n\nThe theorems of Bollobás (1965) and Lovász (1977) about set
pairs are fundamental results in extremal set theory. In this tutorial\,
we discuss some algorithmic applications of these classical theorems. In p
articular\, we learn about representative families and their role in kerne
lization\, enumeration\, and parameterized algorithms.\n\n\nHighlights
of Algorithmic Coding Theory (Madhu Sudan)\n\nIn this series of talks\, we
will quickly introduce the mathematical notions of an error-correcting co
de\, and the associated notions of Encoding and Decoding Algorithms. After
reviewing some of the classical results on the existence\, construction a
nd limits on error-correcting codes\, we will zoom in on two results in th
e field.\n\n\n The construction of capacity achieving codes (based on Fold
ed Reed Solomon Codes) over large alphabets and their encoding and decodin
g: Given any error parameter $\\delta \\in [0\, 1]$ and $\\varepsilon > 0$
\, these codes achieve a rate $1 - \\delta - \\varepsilon$ and correct $\
\delta$ fraction of adversarial errors with alphabet size growing only wi
th $\\varepsilon$.\n The construction of binary error correcting codes (Po
lar codes) that achieve Shannon capacity at small block lengths: I.e\, giv
en $\\delta \\in [0\, 1 / 2]$ and $\\varepsilon > 0$ correct delta fract
ion of random errors with rate $1 - \\mathrm{h}(\\delta) - \\varepsilon$
at lengths $\\mathrm{poly}(1 / \\varepsilon)$. [Here $\\mathrm{h}(p) = -p
\\log_2 p - (1 - p) \\log_2 (1-p)$ is the binary entropy function].\n\n
\nBoth results come with polynomial time algorithms!\n\nVideos\n\nYoutube
channel\n\n\nLocal Organizers:\n\n\n Dmitry Sokolov\n\n\n\nInstitutions pa
rticipating in the organization of the event:\n\n\n Department of Mathemat
ics and Computer Science of St Petersburg University\n Leonhard Euler Inte
rnational Mathematical Institute in Saint Petersburg\n\n\nThe school is su
pported by a grant from the Government of the Russian Federation\, agreeme
nts 075-15-2019-1619 and 075-15-2019-1620.\n\nhttps://indico.eimi.ru/even
t/199/
LOCATION:Zoom
URL:https://indico.eimi.ru/event/199/
END:VEVENT
END:VCALENDAR