
Image reconstruction using graphical models
Ficová, Klára ; Kazda, Alexandr (advisor) ; Bulín, Jakub (referee)
Graphical models represent probability relations among random variables using a graph. They offer an effective way of modelling real life situations and are frequently used in machine learning and statistical thinking. The main goal of this thesis is to describe and implement techniques of denoising an image using graphical models. The graphical model we choose is factorgraph, representing pixels in image and interactions between them as nodes. Using algorithms on the graph, we determine the most probable true image. We also apply those theoretical methods on noisy images and compare the results. 1


Properties of deltamatroids
Šíma, Lucien ; Kazda, Alexandr (advisor) ; Rolínek, Michal (referee)
We investigate deltamatroids which are formed by families of subsets of a finite ground set such that the exchange axiom is satisfied. We deal with some natural classes of deltamatroids. The main result of this thesis establishes sev eral relations between even, linear, and matchingrealizable deltamatroids. Fol lowing up on the ideas due to Geelena, Iwatab, and Murota [2003], and apply ing the properties of field extensions from algebra, we prove that the class of strictly matchingrealizable deltamatroids, the subclass of matchingrealizable deltamatroids, is included in the class of linear deltamatroids. We also show that not every linear deltamatroid is matchingrealizable by giving a skewsymmetric matrix representation to the non matchingrealizable deltamatroid constructed by Kazda, Kolmogorov, and Rol'ınek [2019].


Presentations of subgroups
Jakubec, Tomáš ; Růžička, Pavel (advisor) ; Kazda, Alexandr (referee)
This bachelor thesis shows, how to create the presentation of subgroup, if the presentation of group is known by ReidemeisterSchreier method. At first, a term presentation of group is defined and then the text shows, how to obtain the group, which is isomorphic to the original group, from this presentation and how the presentation can be changed, although the group, which is ob tained from the presentation, stays same. Then the text finds presentation of subgroup from the presentation of group, however this presentation cannot be in general used in practice. The obtained presentation of subgroup can be simplified by Reidemeister theorem, Schreier theorem and appropriate genera tors of subgroup. This thesis also contains solved examples of application of ReidemeisterSchreier method. The text is intended as an educational material for students of combinatorial group theory. 1

 

On impossibility of elementary integration
Zelina, Michael ; Pražák, Dalibor (advisor) ; Kazda, Alexandr (referee)
This work is devoted to studying of problem of (non)existence an elementary pri mitive function of a given function. In the first place, we introduce the structure of a differential field and then we find a suitable way of formalizing the concept of the elementary function. This tools opens up the possibility to formulate and prove the crucial theorem which says what form an elemental primitive function must necessarily have if it exists. Then we use it to find the conditions for the existence of an ele mentary integrals of two functions in a special but still quite general form. By using these conditions, we will show the nonelementarity of a number of more or less known integrals. 3


Key dependent message security
Hostáková, Kristina ; Hojsík, Michal (advisor) ; Kazda, Alexandr (referee)
In this work, we deal with cryptosystems which are provably secure even if we encrypt a keydependent message. These cryptosystems are called KDMsecure. First, we define KDMsecurity and discuss its relationship with other kinds of security, especially INDCPAsecurity. Thereafter, we construct the public key and the symmetrickey encryption scheme of Applebaum et al. (CRYPTO 2009) and we prove KDMsecurity of these cryprosystems with respect to the set of affine functions. The security of our cryptosystems is based on the LWE problem and the LPN problem as its special case. We study these problems and their variants. Moreover, we give a brief introduction to lattices and hard lattice problems because there exist reductions from hard lattice problems to LWE. 1


Homomorphic encryption schemes
Titěrová, Anežka ; Kazda, Alexandr (advisor) ; Hojsík, Michal (referee)
Title: Homomorphic encryption schemes Author: Anežka Titěrová Department: Department of Algebra Supervisor: RNDr. Alexandr Kazda, Department of Algebra Abstract: Rivest et al. posed in 1978 the cryptographic problem how to correctly compute arbitrary functions over encrypted data without direct decrypting. This problem is solved by using of a fully homomorphic encryp tion scheme, which was discovered and first described by Craig Gentry in 2009. This work gives a summary of contemporary knowledge in this field. The attention will be restricted to a general overview how to construct the fully homomorphic encryption scheme with respect to the information security. The results will be applied in an implementation of a somewhat homomorphic encryption scheme as a computer program. Fully homomorphic encryption schemes have abundant applications, especi ally in secure cloud computing. Nevertheless, the greatest challenge for scien tists is finding out more efficient algorithm because existing implementations are not as effective and fast as required for everyday use. Keywords: homomorphic encryption, fully homomorphic encryption scheme, lattice cryptography, logic circuit


Constraint Satisfaction Problem and Universal Algebra
Kazda, Alexandr ; Barto, Libor (advisor) ; Růžička, Pavel (referee) ; Valeriote, Matt (referee)
The thesis consists of a collection of my contributions to universal algebra. Motivated by the Constraint Satisfaction Problem (CSP), we study the algebras of polymorphisms of relational structures. We begin by showing by an algebraic argument (and a bit of calculus) that random relational structures' CSP is almost always NPcomplete. We then study digraphs with a Maltsev polymorphism, and conclude that such digraphs must also have a majority polymorphism. Next, we show how to use absorption tech niques to prove that congruence modular reflexive digraphs must have an NU operation. We close our work by giving an algebraic proof of a result (first obtained by graph theorists) that 3conservative relational structures with only unary and binary relations either define NPcomplete CSP, or CSP for them can be solved by the local consistency algorithm. 1


Model building using CSP
Peterová, Alena ; Stanovský, David (advisor) ; Kazda, Alexandr (referee)
In the present work, we study algorithms for building finite models of sets of firstorder axioms with the aim of proposing and implementing a new method, based on translation onto constraint satisfaction problem (CSP). In the theoretical part, we describe the standard MACEstyle method, based on translating problems onto SAT, and advanced techniques that improve the effectiveness of this method: clause splitting, term definitions and static symmetry reduction. Next, we propose an alternative method, which translates problems onto CSP in a similar way. In addition, we have newly proposed a static symmetry reduction technique for binary functions. Next, we describe an implementation of the alternative method using a CSPmodelling language MiniZinc and a CSPsolver Gecode. Finally, we compare performance of our model finder against stateoftheart representatives of standard methods, systems Paradox and Mace4.

 