8
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ I think that this question could use a little more explanation. I believe I've figured out what you mean, but I'm not totally sure. $\endgroup$ – Peter Shor Nov 13 '11 at 18:51
  • 1
    $\begingroup$ Is there a reference for the "quadratic lower bound for $B$ such that det(B) = per(A)" ? $\endgroup$ – Suresh Venkat Nov 14 '11 at 0:49
  • 1
    $\begingroup$ @SureshVenkat Doesn't the following result imply a quadratic lower bound? pages.cs.wisc.edu/~jyc/papers/per-det.pdf $\endgroup$ – v s Nov 14 '11 at 1:02
  • 1
    $\begingroup$ Well that's my point. it would be useful to link to that in the question. $\endgroup$ – Suresh Venkat Nov 14 '11 at 1:26
  • $\begingroup$ @SureshVenkat Oh Ok! $\endgroup$ – v s Nov 14 '11 at 1:49
15
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.