Meeting #204 of the Omsk Group Seminar will feature a talk by Markus Lohrey

The next Omsk Group Seminar meeting will take place on October 15 at 18:00 (Omsk time), 19:00 (Novosibirsk time), 08:00 (New York time), 15:00 (Moscow time). Markus Lohrey (Siegen University, Germany) will present his talk "Knapsack and the power word problem in solvable Baumslag-Solitar groups".

We show that the power word problem for a solvable Baumslag-Solitar groups BS(1,q) belongs to the circuit complexity class TC0; a very small complexity class within polynomial time (even logspace). The power word problem is a succinct version of the classical word problem, where the input consists of group elements g_1,…, g_d (encoded as words over a set of generators) and binary encoded integers z_1,..., z_d and it is asked whether g_1^{n_1} ... g_d^{n_d} = 1 holds in the underlying group. Moreover, we prove that the knapsack problem for BS(1,q) is NP-complete. In  the knapsack problem, the input consists of group elements g_1,…, g_d, h, and it is asked whether the equation g_1^{x_1} ... g_d^{x_d} = h  (where the x_i are variables ranging over the natural numbers) has a solution.

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

You can connect to the Zoom conference via this link: https://us02web.zoom.us/wc/join/81220793393 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