吃瓜官网

Alexander Rybalov (Sobolev Institute of Mathematics, Omsk, Russia) will present his talk "The Diophantine problem in classical matrix groups".

The subset sum problem is a classical combinatorial problem, studied for many decades. This problem is very popular in cryptography, where there are many cryptosystems based on it. Myasnikov, Nikolaev and Ushakov in 2015 introduced analogs of the subset sum problem for arbitrary groups (semigroups). They explored the computational complexity of these problems for various groups: polynomial solvability is proved for hyperbolic groups, NP-completeness is proved for Baumslag-Solitar groups. In this talk I present results about generic polynomial decidability of the subset sum problem for following semigroups: monoid Mat(N,k) of k x k matrices with natural entries, monoid SL(N,2) of unimodular 2x2 matrices with natural entries, groups PSL(Z,2) and SL(Z,2), and some Brandt semigroups.

Preliminary future speakers: V. Remeslennikov, A. Treyer. 

You can connect to the Zoom conference via this link:  or manually in the Zoom app using the conference ID 812 2079 3393.

Please pay attention to the following rules for conducting an Internet seminar:

• Please, use your real first and last name
• Keep your microphone off during the talk
• Should you have any questions, ask them in the chat