Friday 08.03.2024 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Petr Savický (ICS CAS): TBA
Abstract: TBA
Friday 23.02.2024 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Tomáš Hons (Charles University): First-order limits and rooted inverse problems
Abstract: The main goal of graph limit theory is to assign to a given well-behaved sequence of graphs a certain limit object capturing significant properties of the sequence. When seeking the right definition of the limit object, we consider the inverse problem asking which objects can actually arise as a limit. This seems to be very difficult for some notions of convergence. A simplified problem of a similar nature is approximation of vertices of the limit object, which we call rooted inverse problem. In this talk, we introduce the rooted inverse problem in the context of first-order limit theory. We describe the current state-of-the-art, discuss some open problems and possible approaches.
Friday 16.02.2024 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Denys Bulavka (Charles University): TBA
Abstract: TBA
Friday 02.02.2024 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Martin Balko (Charles University): The Erdős--Szekeres Theorem for Split Polygons
Abstract: The famous and still open Erdős--Szekeres Conjecture (1935) states that every set of at least 2k-2+1 points in the plane with no three being collinear contains k points in convex position, that is, k points that are vertices of a convex polygon. We prove several new results around this conjecture. In particular, we prove a relaxed version of the Erdős--Szekeres Conjecture where the value 2k-2+1 is exactly the right threshold. This is a joint work with Jineon Baek.
Friday 19.01.2024 at 14:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Gorav Jindal (Max Planck Institute for Software Systems): Sign Me Up: PosSLP, Sign Testing, and Polynomials
Abstract: Given an integer, deciding its positivity may appear trivial initially. However, this problem becomes more compelling when the integer is presented in a compact form, as opposed to being explicitly represented as a bit string. One such compact representation involves utilizing straight line programs and arithmetic circuits. In this talk, I introduce the concept of straight line programs and subsequently delve into the PosSLP problem, which is the problem of testing the positivity of integers represented by straight line programs. Furthermore, I provide a brief survey of how PosSLP is intricately connected to the Blum–Shub–Smale (BSS) model of computations over reals, numerical analysis, and other intriguing problems in complexity theory. To conclude the talk, I discuss our recent and ongoing research on the PosSLP problem.
Wednesday 17.01.2024 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Samuel Braunfeld (Charles University): Automorphism-invariant measures on countable structures
Abstract: We discuss the classification of automorphism-invariant measures on certain highly symmetric countable structures. The tools include model theory, exchangeability, and probabilistic constructions. This is joint work with Colin Jahel and Paolo Marimon.
Monday 15.01.2024 at 10:00 ICS, room 318 (and on ZOOM, 4-digit password consisting of the prime numbers <10), Václav Rozhoň (ETH Zürich): Network decompositions in distributed computing and beyond
|
Abstract: I will talk about so-called network decompositions and their applications in distributed computing and beyond. In particular, Bernshteyn and Yu recently proved a lemma about the existence of network decompositions in graphs of polynomial growth and used that lemma to prove results about so-called measurable graphs. I plan to present a simple proof of their lemma. Joint work with Jan Grebík, Andrew Marks, Forte Shinko |
