Gaussian Noise Sensitivity and Fourier Tails
Guy Kindler, Ryan W. O’Donnell · 2012
We study the problem of matrix isomorphism of matrix Lie algebras (MatIsoLie). Lie algebras arise centrally in areas as diverse as differential equations, particle physics, group theory, and the Mulmuley -- Sohoni Geometric Complexity Theory program. A matrix Lie algebra is a set L of matrices that is closed under linear combinations and the operation [A, B] = AB - BA. Two matrix Lie algebras L, L' are matrix isomorphic if there is an invertible matrix M such that conjugating every matrix in L by M yields the set L'. We show that certain cases of MatIsoLie -- for the wide and widely studied classes of semi simple and abelian Lie algebras -- are equivalent to graph isomorphism and linear code equivalence, respectively. On the other hand, we give polynomial-time algorithms for other cases of MatIsoLie, which allow us to mostly derandomize a recent result of Kayal on affine equivalence of polynomials.