Number of the records: 1  

Prague Summer School on Discrete Mathematics 2020

  1. 1.
    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
    Subject RIV: BA - General Mathematics
    OBOR OECD: Pure mathematics

    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:
Number of the records: 1