Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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