All reports by Author Cris Moore:

__
TR17-158
| 23rd October 2017
__

Eric Allender, Joshua Grochow, Dieter van Melkebeek, Cris Moore, Andrew Morgan#### Minimum Circuit Size, Graph Isomorphism, and Related Problems

__
TR17-131
| 1st September 2017
__

Joshua Grochow, Cris Moore#### Designing Strassen's algorithm

__
TR15-162
| 9th October 2015
__

Eric Allender, Joshua Grochow, Cris Moore#### Graph Isomorphism and Circuit Size

Revisions: 1

__
TR14-073
| 14th May 2014
__

Shachar Lovett, Cris Moore, Alexander Russell#### Group representations that resist random sampling

Revisions: 1

Eric Allender, Joshua Grochow, Dieter van Melkebeek, Cris Moore, Andrew Morgan

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 >>>

Joshua Grochow, Cris Moore

In 1969, Strassen shocked the world by showing that two n x n matrices could be multiplied in time asymptotically less than $O(n^3)$. While the recursive construction in his algorithm is very clear, the key gain was made by showing that 2 x 2 matrix multiplication could be performed with ... more >>>

Eric Allender, Joshua Grochow, Cris Moore

We show that the Graph Automorphism problem is ZPP-reducible to MKTP, the problem of minimizing time-bounded Kolmogorov complexity. MKTP has previously been studied in connection with the Minimum Circuit Size Problem (MCSP) and is often viewed as essentially a different encoding of MCSP. All prior reductions to MCSP have applied ... more >>>

Shachar Lovett, Cris Moore, Alexander Russell

We show that there exists a family of groups $G_n$ and nontrivial irreducible representations $\rho_n$ such that, for any constant $t$, the average of $\rho_n$ over $t$ uniformly random elements $g_1, \ldots, g_t \in G_n$ has operator norm $1$ with probability approaching 1 as $n \rightarrow \infty$. More quantitatively, we ... more >>>