Seminar Talk Announcement

  • Martin Pilát (Faculty of Mathematics and Physics, Charles University, Prague):

    Evolutionary Algorithms for Expansive Optimization

    28.05.2024 14:00Room 318 (zoom) @ Institute of Computer Science
    Pod Vodárenskou věží 2
    Praha, 182 00
    Hora Informaticae

    Evolutionary algorithms are powerful optimizers with applications in many areas. However, their use is complicated by the large number of objective function evaluations that they require. This is especially problematic in cases where the evaluation is slow or expensive. There are generally two ways, how to deal with this problem - one is to parallelize the algorithm, the other is to use so- called surrogate models (cheap approximations of the real expensive objective function). In the talk, we will explore both of these areas. In the first part, we will discuss two types of parallelization - one of them is usable in cases when the evaluation is not only slow, but also the evaluation time is variable, i.e. in cases where standard parallelization techniques often cannot fully utilize the available computational resources. Then we will discuss recent libraries for implementing evolutionary algorithms on GPUs. In the second part, we will briefly talk about surrogate-based optimization. Surrogate models are mostly used in areas, where the individual encoding is rather simple. We will talk about the potential to apply them also in areas with complex individual structure, such as in genetic programming, automated machine learning and neural architecture search.

  • David Cerna (Czech Academy of Sciences, Institute of Computer Science):

    One is all you need: Second-order Unification without First-order Variables

    05.06.2024 16:00Room 318 (live) and ZOOM @ Institute of Computer Science
    Pod Vodárenskou věží 2
    Praha, 182 00
    Applied Mathematical Logic Seminar

    We consider the fragment of Second-Order unification, referred to as Second-Order Ground Unification (SOGU), with the following properties: (i) only one second-order variable allowed, (ii) first-order variables do not occur. We show that Hilbert's 10th problem is reducible to a necessary condition for SOGU unifiability if the signature contains a binary function symbol and two constants, thus proving undecidability. This generalizes known undecidability results, as either first-order variable occurrences or multiple second-order variables were required for the reductions. Furthermore, we show that adding the following restriction:(i) the second-order variable has arity 1, (ii) the signature is finite, and (iii) the problem has bounded congruence, results in a decidable fragment. The latter fragment is related to bounded second-order unification in the sense that the number of bound variable occurrences is a function of the problem structure. We conclude with a discussion concerning the removal of the bounded congruence restriction. Joint work with Julian Parsert.

Past Talks