Minimum Circuit Size, Graph Isomorphism, and Related Problems

Eric Allender, Joshua A. Grochow, Dieter van Melkebeek +2

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…