# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

On 10.3.2006 at 12:20 in S5, there is the following noon lecture:

# Complexity of linear mappings induced by graphs

## Jose Zamora

## Abstract

What is the computational complexity of the following problem:

Given a set X of cardinality N=2^n and k bijections f_1,f_2,...,f_k: X --> X, does there exist a bijection g: X --> GF(2)^n such that each composed mapping g^{-1} o f_i o g is linear (affine)?

The problem is motivated by locally bijective graph homomorphisms (also known as graph covers). We study the case k=1, and give polynomial algorithm under some assuptions. The algorithm is based on a procedure to find a representative of any conjugacy class of GL(n,2).

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

Webmaster: kamweb.mff.cuni.cz Archive page