Conditional results implying difficulty of improving upper/lower bounds for permanent 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 &gt; 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?
An upper bound of $O(2^{n^{\epsilon}})$ may not be possible for any $\epsilon&lt;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

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

Transform the permanent to a determinant over the larger matrix

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'&lt;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.