Prague Summer School on Discrete Mathematics 2020

0539966 - MÚ 2021 RIV eng U - Conference, Workshop Arrangement
Dvořák, Z. - Hladký, Jan
Prague Summer School on Discrete Mathematics 2020.
[Prague, 24.08.2020-28.08.2020, (W-WRD 70/66)]
Institutional support: RVO:67985840
Keywords : topology * theoretical computer science * graph theory
OECD category: Pure mathematics
http://pssdm.math.cas.cz/2020

Subhash Khot: Hardness of Approximation: From the PCP Theorem to the 2-to-2 Games Theorem
Computer scientists firmly believe that no algorithm can efficiently compute optimal solutions to a class of problems called NP-hard problems. For many NP-hard problems, even computing an approximately optimal solution remains NP-hard. This phenomenon, known as the hardness of approximation, has numerous connections to proof checking, optimization, combinatorics, discrete Fourier analysis, and geometry.
Shayan Oveis Gharan: Polynomial Paradigm in Algorithm Design
In this course we discuss the fruitful paradigm of encoding discrete phenomena in complex multivariate polynomials, and understanding them via the interplay of the coefficients, zeros, and function values of these polynomials. Over the last fifteen years, this perspective has led to several breakthroughs in computer science, and an unexpected bridge between seemingly distant scientific areas including combinatorics, probability, statistical physics, convex and algebraic geometry, and computer science has been built. In this course I plan to cover part of these developments with an emphasis on more recent developments specially connections to traveling salesman problem, matroids, high dimensional expanders and mixing time of random walks.
Permanent Link: http://hdl.handle.net/11104/0317649