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?

Improve this question
$\endgroup$
3
  • $\begingroup$ The lower bound is only for circuits with small constants. $\endgroup$
    – Yuval Filmus
    Commented Feb 13, 2016 at 15:43
  • $\begingroup$ There are some surveys on arithmetic circuits – have you looked at them? $\endgroup$
    – Yuval Filmus
    Commented Feb 13, 2016 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
    Commented Feb 13, 2016 at 21:34

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.