Upcoming meeting:
-
Meeting #969
Alexander Prolubnikov (Omsk State University)
"An approach to finding connected components of graphs using perturbations of adjacency matrices."
Abstract. We consider the problem of finding connected components of a graph. The natural approach to the problem is the breadth-first search (BFS) that is implemented in the software libraries which are using the benefits of modern computer architectures. We present the approach that uses perturbations of adjacency matrix of a graph to implement the connectivity test. To perform the test, we compare solutions of the two systems of linear algebraic equations (SLAE) which we associate with the unperturbed adjacency matrix and with the perturbed one. Such approach allows to use computationally effective implementations of numerical methods for solving SLAE to solve connectivity problems on graphs. Iterations of iterative methods for solving SLAE may be considered as implementations of graph traversals which, in general, are not equivalent to the traversal that is implemented by BFS. We present the algorithm to find connected components of a graph that uses such a traversal. For every instance of the problem, the computational complexity of the algorithm is not greater than the one of BFS, and it is lower than that in most instances.
Latest announcements:
-
Meeting #968
Alexey Nikitin (Deeplay, Omsk)
"Computations in universal classes with applications for graph and order models."
Abstract. In the talk I will present results concerning algebraic geometry over partially ordered sets:
1. Complexity of algorithms for solving systems of equations over partial orders;
2. Noethericity by equations for partial orders;
3. Decidability of theories over partial orders;
4. Construction of radicals and coordinate partial orders for systems of equations over partial orders and strict partially ordered sets. -
Meeting #967
Vitaly Roman'kov (Sobolev Institute of Mathematics)
"On the embedding of free nilpotent groups in partially commutative nilpotent groups."
Abstract. An algorithm is presented that allows one to calculate the maximum rank of a free nilpotent group of class k into a given partially commutative nilpotent group of class k.
-
Meeting #966
Marina Rasskazova (Omsk State Technical University)
"Binary Lie algebras and its application to the theory of Binary Lie superalgebras."
Abstract. The tropical structures min-plus and max-plus are well-known and have many interesting applications.
By definition an algebra \(B\) is binary-Lie algebra iff any two elements \(a,b\in B\) generate a Lie subalgebra. A \({\bf Z}_2-\)graded algebra \(B=B_0\oplus B_1\) is a binary-Lie superalgebra iff \(B\times \Gamma=B_0\otimes \Gamma_0\oplus B_1\otimes \Gamma_1\) is a binary Lie algebra, where \(\Gamma=\Gamma_0\oplus \Gamma_1\) is a Grassman algebra with natural gradation. We apply the theory of binary-Lie algebras for proving the following result.
Theorem. Let \(B=B_0\oplus B_1\) be a simple binary-Lie superalgebra finite dimensional over the field \({\bf C}\) of complex numbers. Then \(B_0\) is a solvable algebra or \(B\) is a Lie superalgebra.
This theorem reduced the problem (open yet!) of classification of a simple binary-Lie superalgebra finite dimensional over the field \({\bf C}\) to the case where subalgebra \(B_0\) is solvable.
This talk is based on the joint paper with A.Grishkov and I.Shestakov. -
Meeting #965
Matvei Kotov (Sobolev Institute of Mathematics)
"Tropical approach in cryptography."
Abstract. The tropical structures min-plus and max-plus are well-known and have many interesting applications.
In two papers “Tropical Cryptography” (2014) and “Tropical Cryptography II: extensions by homomorphisms” (2019), V. Shpilrain and D. Grigoriev suggested using tropical algebras as platforms for several cryptographic schemes in order to avoid linear algebra attacks. Another reason for their popularity is efficiency because multiplication is replaced by addition. Also, in “An application of different dioids in public key cryptography” (2014), M. Durcheva offered other cryptographic protocols based on tropical algebras and similar algebras. In recent years, other authors also developed some schemes in this area.
Many of these protocols were analyzed and attacks were developed by M. Kotov and A. Ushakov (2018), A. Muanalifah, and S. Sergeev (2020), D. Rudy and C. Monico (2020), S. Isaac and D. Kahrobaei (2021), K. Ahmed, S. Pal, and R. Mohan (2022).
Recently, we analyzed one of Durcheva’s protocols and implemented a successful attack (joint work with Ivan Buchinskiy and Alexander Treier).
In this talk, I will review the current status of tropical cryptography (protocols, methods to analyze them, and attacks) and discuss our new attack.