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:20260414T000351Z
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