Number of the records: 1
Prague Summer School on Discrete Mathematics 2020
- 1.
SYSNO ASEP 0539966 Document Type U - Organizing Conference, Workshop, Exhibition R&D Document Type W - Uspořádání workshopu R&D Document Type Není vybrán druh dokumentu Title Prague Summer School on Discrete Mathematics 2020 Author(s) Dvořák, Z. (CZ)
Hladký, Jan (MU-W) RID, SAI, ORCIDEvent type W - Workshop Event date 24.08.2020 - 28.08.2020 VEvent location Prague Country CZ - Czech Republic Event type WRD Total number of participants 70 Number of foreign participants 66 Language eng - English Keywords topology ; theoretical computer science ; graph theory Subject RIV BA - General Mathematics OECD category Pure mathematics Institutional support MU-W - RVO:67985840 Annotation 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.Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2021 Electronic address http://pssdm.math.cas.cz/2020
Number of the records: 1