Home / Events / Seminar: "Algorithmic problems in right-angled Artin groups complexity and applications" (Delaram Kahrobaei, CUNY)

Seminar: "Algorithmic problems in right-angled Artin groups complexity and applications" (Delaram Kahrobaei, CUNY)

Seminari Teoria de Grups 2017/2018, session 3

Date: Friday November 17th, 2017, 11 - 12 h.
Place: room 004, FME-UPC
Speaker:  Delaram Kahrobaei (City University of New York)


Abstract. The interesting connections between graph theoretic problems and group theoretic problems are evident by the way a right-angled Artin groups has been defined. For example the recent result by Babai on graph isomorphism problem, leads to the fact that the group isomorphism problem for RAAG is also in quasi-polynomial time.

The algorithmic graph theoretic problems have been studied for many years and there are many known complexity analysis for such problems. By connecting some of these problems to group theoretic ones for RAAGs, there will be more doors open to solve such problems in complexity theory.

Flores and Kahrobaei recently proposed right-angled Artin groups for cryptography, in particular for two authentication schemes using group homomorphism problem and subgroup isomorphism problem. It has also pointed out because the word problem in the right-angled Artin groups is in linear time, this could be used for a secret sharing schemes.

Since the graph theoretic problems have been of central attention for the complexity problems, it is a natural direction to think of some of these graph theoretic problems which are equivalent to group theoretic problems in the right-angled Artin groups. This direction will be fruitful for finding efficient algorithms for the known graph theoretic algorithms. At the same time some of these problems been used for cryptography such as authentication, zero-knowledge, secret sharing schemes, among others.

The talk will be of interest of group theorists, graph theorists, and computer scientists.

This is a joint work with Ramon Flores and Thomas Koberda.

Filed under: , ,