1
$\begingroup$

In this http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.1090&rep=rep1&type=pdf an unconditional lower bound (provided constants used are bounded by absolute value smaller than $1$) of $\Omega(n^2\log n)$ for size of arithmetic circuits computing $n\times n$ Matrix Multiplication is given.

What is the best unconditional lower bound for size of arithmetic circuits computing $n\times n$ Matrix Determinant and Permanent along similar lines?

$\endgroup$
  • $\begingroup$ The lower bound is only for circuits with small constants. $\endgroup$ – Yuval Filmus Feb 13 '16 at 15:43
  • $\begingroup$ There are some surveys on arithmetic circuits – have you looked at them? $\endgroup$ – Yuval Filmus Feb 13 '16 at 21:13
  • $\begingroup$ @YuvalFilmus I looked at this one cs.technion.ac.il/~shpilka/publications/SY10.pdf it gave specific cases like multilinear, monotone and certain depth but could not find what I wanted. $\endgroup$ – user39969 Feb 13 '16 at 21:34
1
$\begingroup$

Kalorkoti gave an $\Omega(n^3)$ lower bound on arithmetic formulas for the determinant and permanent. As far as I know, nothing is known for unrestricted circuits.

| cite | improve this answer | |
$\endgroup$

Your Answer

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