|
[ Home ] [ Current ] [ Archive ]
Školska 2023/24. / Academic year 2023/24 07/06/2024 Simona Prokić (FTN UNS): Probabilistic reasoning in computation and simple type theory In this talk, two different approaches used to introduce probabilistic
reasoning in models of computation will be presented. The most usual approach is to extend the language of untyped lambda calculus with
probabilistic choice operator which results in probabilistic computation. Another approach is to extend the language of a typed calculus with
probability operators and to obtain a framework for probabilistic reasoning about the typed calculus in the style of probability logic. 17/05/2024 Novosadski algebarski kolokvijum povodom 75. rođendana prof. Siniše Crvenkovića Rozalija Madaras Silađi: Uvodno slovo Igor Dolinka: Algebra i mali fudbal u godinama koje su pojeli skakavci Petar Đapić: "Mala" i "velika" matematika na otkucajima srca Nebojša Mudrinski: SC & SC Petar Marković: Turniri kao algebre 18/04/2024 Branislav Šobot (Humboldt University, Berlin, Germany): Generically unramified semisimple perverse sheaves on commutative algebraic groups Algebraic Geometry is a branch of mathematics which uses abstract methods of commutative algebra in order to solve problems of geometric nature. In the first part of this talk we give basic notations of this theory including the famous Hilbert Nullstellensatz. Afterwards, we introduce the etale cohomology machinery, which was the main ingredient in the proof of the Weil conjectures, and represent "the correct" analog of the singular cohomology from algebraic topology. At the end, we will mention perverse sheaves and their relation to some estimation problems in analytic number theory. 04/04/2024 Aleksandar Prokić (FTN UNS): Bulatov's colored edge theory in minimal Taylor algebras The Algebraic Dichotomy Conjecture states that
the CSP over a Taylor algebra is tractable, and NP-complete over a non-Taylor algebra.
The conjecture was proved independently by Bulatov and Zhuk, in 2017. In both proofs authors do not work with general Taylor algebras, they reduce
Taylor algebras by dropping some of the operations. In the paper of Barto, Brady, Bulatov, Kozik and Zhuk,
the authors propose and investigate a new class of very interesting algebras, minimal Taylor algebras (MTA). Every minimal Taylor algebra
A is Taylor so the CSP over A is tractable according to the Dichotomy
Theorem. Also, every tractable CSP produces a Taylor algebra and we can reduce that algebra to
a MTA. So if someone solves the CSP for minimal Taylor algebras it would be an alternative proof for the Dichotomy Conjecture. 09/02/2024 Kristina Asimi (Durham University, UK): (Promise) Constraint Satisfaction Problem In this lecture, I will present the basics of the Constraint Satisfaction Problem (CSP) and one of its generalizations, the Promise Constraint Satisfaction Problem (PCSP). In the final part, I will present some special classes of PCSP, the so called not finitely tractable PCSPs. Namely, all the currently known tractable (i.e., solvable in polynomial time) PCSPs over finite templates can be reduced to tractable CSPs and I will present some classes of PCSPs for which that CSP has to be over an infinite domain (unless P=NP). 17/01/2024 Boriša Kuzeljević (DMI PMF NS): Lower bounds of P-point ultrafilters The Rudin-Keisler ordering was introduced in the early seventies of the twentieth century. In the talk, we will give some historical background of this notion, and then focus on the structure of P-point ultrafilters under this ordering. Since P-points form a downward closed subset of the set of all ultrafilters on the set of natural numbers, this provides some global information about the lower part of this class. We will present some recent results on the existence of lower bounds of sets of P-points, obtained in a joint work with Dilip Raghavan and Jonathan Verner. 08/12/2023 Petar Marković (DMI PMF NS): The Constraint Satisfaction Dichotomy Conjecture: History, proofs and generalizations The Constraint Satisfaction Problem was defined in the 1990s inspired by certain topics in Descriptive Complexity. At that time, the Dichotomy Conjecture on the complexity of the Constraint Satisfaction Problem was posed. The Dichotomy Conjecture was proved a quarter of a century later, in 2017, independently by Andrei Bulatov and Dmitriy Zhuk. In this lecture I will define the Constraint Satisfaction Problem, motivate the Dichotomy Conjecture, and survey the main ideas in the proofs by Bulatov and Zhuk. In the final part, I will briefly describe the two most popular generalizations which are a focus of research by numerous teams since the proof of the Dichotomy Conjecture, introduce a third possibility of generalizing the Dichotomy Conjecture and argue why this third topic should also be in the focus of research. 17/11/2023 Edward T. Dobson (University of Primorska, Koper, Slovenia): Towards inductive proofs in algebraic combinatorics One of the main obstacles to solving problems concerning automorphism groups of vertex-transitive graphs and digraphs is that the natural factors of the automorphism group do not necessarily give groups that are automorphism groups of vertex-transitive graphs or digraphs (or even 2-closed groups). Thus using induction can be difficult. We find a class of transitive permutation groups, which properly contains the automorphism groups of vertex-transitive graphs and digraphs, and call them 5/2-closed, as, using Wielandt's hierarchy of permutation groups, the class is larger than 2-closed but contain groups which are not 3-closed. We give a sufficient condition for the natural quotients of transitive groups in this class to remain in this class, in effect giving a sufficient condition for natural inductive proofs to work. We will then give examples of results that have been proven for this new class, solving several problems concerning isomorphisms between combinatorial objects, automorphism groups of combinatorial objects, and more. Ademir Hujdurović (University of Primorska, Koper, Slovenia): Erdős-Ko-Rado property of transitive permutation groups The Erdős-Ko-Rado theorem is one of the central results in extremal combinatorics. It gives a bound on the size of a family of intersecting k-subsets of a set and classifies the families satisfying the bound. In this presentation I will talk about the classical Erdős-Ko-Rado theorem and its extension to transitive permutation groups. I will present some known and some new results on the maximum sizes of intersecting sets in certain permutation groups. We will see how the construction of certain cyclic codes was used for disproving a recent conjecture regarding transitive groups of degree a product of two primes. Several open problems will be presented. |
