Testing Permanent Oracles -- Revisited

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran +1

Suppose we are given an oracle that claims to approximate the permanent for most matrices X, where X is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate…