11th workshop of the Center for Foundations of Modern Computer Science

11. workshop Centra základů moderní informatiky

The eleventh workshop of the Center for Foundations of Modern Computer Science took place on Monday June 5 and Tuesday June 6, 2023, in Prague as a part of STTI 2023.

Abstracts

Martin Koutecký: Dva modely šíření názorů ve společnosti

Významným prvkem marketingových a politických kampaní posledních let je, že "nepřímé" ovlivňování společnosti, při němž kampaň počítá s důsledky šíření zpráv a názorů ve společnosti. Ačkoliv existuje mnoho různých modelů tohoto fenoménu, z algoritmického hlediska se o nich typicky nedá říct mnoho pozitivního -- výpočetní problém optimálního ovlivnění společnosti je obvykle těžký i pro extrémně jednoduché třídy grafů. Proto představím dva nové a vzájemně související modely šíření názorů, které tento neduh řeší. Zmíním i několik přístupných otevřených problémů.

Přednáška vychází ze společné práce s Faliszeweskim, Gonen a Talmonem (IJCAI 2018) a bakalářské práce Aleše Prokopa (2023).

Pavel Veselý: Proudové algoritmy pro Eukleidovské Facility Location a geometrické hešování

V problému Euklidovské Facility Location s uniformní cenou potřebujeme otevřít jistá zařízení (např. ordinace doktorů), která obslouží danou množinu klientů rozmístěných v R^d. Cílem je minimalizovat sumu ceny za otevření zařízení a celkové vzdálenosti jednotlivých klientů k jejich nejbližšímu zařízení.

Zaměříme se na tzv. proudové (streaming) algoritmy, které zpracují množinu bodů (klientů) v jednom průchodu s malou pamětí, ideálně logaritmickou v počtu bodů a polynomiální v dimenzi.
Představíme novou techniku pro návrh proudových algoritmů pro Facility Location na aproximaci optimální ceny. Tato technika je založena na geometrickém hešování bodů v R^d do přihrádek, jehož klíčovou vlastností je, že libovolná množina bodů o dost malém průměru se zahešuje do omezeného počtu přihrádek (polynomiálního v d). Díky tomu naše algoritmy fungují dobře i ve vysoké dimenzi d.

Příspěvek obsahuje výsledky společné práce s Arturem Czumajem, Arnoldem Filtserem, Shaofengem Jiangem, Robertem Krauthgamerem a Mingweiem Yangem.

Martin Balko: On Helly numbers of exponential lattices

For every set subset S of R^2, the Helly number of S is the smallest positive integer N, if it exists, such that, for every finite family F of convex sets in R^2 the following statement is true: if the intersection of any N or fewer members of F contains at least one point of S, then the intersection of sets in F contains at least one point of S.

We prove that the Helly numbers of exponential lattices {alpha^n: n >= 0}^2 are finite for every alpha > 1 and we determine their exact values in some instances, which in particular solves a problem posed by Dillon. We also fully characterize nondiagonal exponential lattices {alpha^n: n >= 0} times {beta^n: n >= 0} with alpha, beta > 1 with finite Helly numbers using results from number theory.

Joint work with Gergely Ambrus, Nóra Frankl, Attila Jung, and Márton Naszódi.