Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LINEAR CODE EQUIVALENCE:
Reports tagged with linear code equivalence:
TR11-168 | 9th December 2011
Joshua Grochow

#### Lie algebra conjugacy

We study the problem of matrix Lie algebra conjugacy. 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 $\mathcal{L}$ of matrices such that $A,B \in \mathcal{L}$ implies\$AB - BA \in ... more >>>

TR17-158 | 23rd October 2017
Eric Allender, Joshua Grochow, Dieter van Melkebeek, Cris Moore, Andrew Morgan

#### Minimum Circuit Size, Graph Isomorphism, and Related Problems

We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted as MKTP where circuit size is replaced by a polynomially-related Kolmogorov measure. All prior reductions ... more >>>

ISSN 1433-8092 | Imprint