Vazena pani, vazeny pane
Zasilame Vam pozvanku na prednasku doc. H. R. Tiwaryho, ktera se kona na MFF UK (Praha) v utery 28. listopadu. Budeme radi, kdyz informaci o ni predate kolegynim a kolegum.
Prejeme pekny den.
Za organizatory,
Jaroslav Nesetril a Martin Klazar
(pdf pozvanky - obsahuje laudatio a dalsi informace o kolokviich: https://kam.mff.cuni.cz/~klazar/tiwary.pdf) ____________________________________________________________________
- kolokvium:
LIMITATIONS OF LINEAR PROGRAMMING
H. R. Tiwary
utery 28. listopadu 2023 v 10:00, aula (refektar), prvni patro
MFF UK, Malostranske nam. 25, Praha 1 ____________________________________________________________________
Abstract. Linear Programming is a pervasive tool in algorithm design for optimization problems. Linear Programs (LPs) are known to be able to effectively model any problem that can be efficiently solved on a computer. But are they also able to efficiently model NP-hard problems? An affirmative answer to this question will settle the P vs. NP problem affirmatively, and so it is no surprise that the answer is no. However, attempts to prove such limits on the power of LPs lead us to explore interesting connections to communication complexity. In this talk, I will explore such a connection that resulted in a proof that the Traveling Salesman Problem cannot be solved well using LPs. I will first discuss the subtleties involved in making the above claim precise. Then I will describe the result, its connection to communication complexity, and various generalizations to the quantum setting and beyond. The talk is based on joint work with Samuel Fiorini, Serge Massar, Sebastian Pokutta, and Ronald de Wolf. ____________________________________________________________________