All reports by Author Andrew Morgan:

__
TR22-115
| 17th August 2022
__

Dieter van Melkebeek, Andrew Morgan#### Polynomial Identity Testing via Evaluation of Rational Functions

__
TR17-158
| 23rd October 2017
__

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

Dieter van Melkebeek, Andrew Morgan

We introduce a hitting set generator for Polynomial Identity Testing

based on evaluations of low-degree univariate rational functions at

abscissas associated with the variables. Despite the univariate

nature, we establish an equivalence up to rescaling with a generator

introduced by Shpilka and Volkovich, which has a similar structure but

uses ...
more >>>

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