Conditional results implying difficulty of improving upper/lower bounds for permanent

Question

Let $A$ be a given square matrix. Is there any evidence that beating quadratic lower bounds for $B$ such that $\text{det}(B) = \text{per}(A)$ could be hard?

Is there any plausible conjecture which implies that proving lower bounds is difficult? Is there any evidence that proving an $\Omega(n^{2+\epsilon})$ rows (or columns) lower bound for some $\epsilon > 0$ is hard (e.g. equivalent to $\mathsf{VP} \ne \mathsf{VNP}$)?

Is there any plausible conjecture which implies that proving upper bounds is difficult? Is there any evidence that proving an $O(2^{n^\epsilon})$ upper bound for some $\epsilon \in (0,1)$ is hard?

Answer 1

An upper bound of $O(2^{n^{\epsilon}})$ may not be possible for any $\epsilon<1$ unless the Exponential Time Hypothesis (ETH) is false, see

Holger Dell, Thore Husfeldt, and Martin Wahlén.

Exponential time complexity of the permanent and the Tutte polynomial.

Full paper at ECCC TR10-78. http://eccc.hpi-web.de/report/2010/078/

That is, if your embedding of the $n\times n$ permanent into a determinant of size $O(2^{n^{\epsilon}})\times O(2^{n^{\epsilon}})$ is fast enough, you could

1. Transform a 3SAT-instance to a permanent as in the paper above

2. Transform the permanent to a determinant over the larger matrix

3. Compute the determinant to find the number of solutions to the original 3SAT-instance.

The running time for an $n$-variate 3SAT instance would be $O(2^{n^{\epsilon'}})$ for some $\epsilon'<1$ depending on $\epsilon$ if step (2) is fast enough (say polynomial in n for each entry of the larger matrix). This would contradict the ETH.