dr hab. Bartłomiej Bosek​
​​​​​​​

czwartek 14:00-15:30, sala 0174

Jest to seminarium magisterskie, którego tematyka dotyczy optymalizacji kombinatorycznej. W szczególności interesują nas następujące tematy:

1. Zaawansowane algorytmy znajdujące skojarzenia w grafach (także dwudzielnych) w przypadkach nieważonych i ważonych krawędzi.
2. Problemy konstruowania on-line skojarzeń w grafach dwudzielnych, AdWords Problem - rozwiązania optymalne, randomizowane.
3. Algorytmiczne aspekty pokrycia uniłańcuchami produktów częściowych porządków.

Strona seminarium na UsosWeb znajduje się tutaj.

Jan Tułowiecki

We prove that any perfect quantum strategy for the two-prover game encoding a constraint satisfaction problem (CSP) can be simulated via a perfect classical strategy with an extra classical communication channel, whose size depends only on (i) the size of the shared quantum system used in the quantum strategy, and (ii) structural parameters of the CSP template. The result is obtained via a combinatorial characterisation of perfect classical strategies with extra communication channels and a geometric rounding procedure for the projection-valued measurements involved in quantum strategies.

1. Jan Tułowiecki. Classical Simulation of Quantum CSP Strategies. slides. (2026).