Tag Info

13

One way is described in Berkowitz, On computing the determinant in small parallel time using a small number of processors (see also Soltys, Berkowitz's algorithm and clow sequences). Another way is described in Hrubeš and Tzameret, Short proofs for the determinant identities.

12

In the case of determinant, Gaussian elimination can indeed be seen as equivalent to the idea that the determinant has a large symmetry group (of a particular form) and is characterized by that symmetry group (meaning any other homogeneous degree $n$ polynomial in $n^2$ variables with those symmetries must be a scalar multiple of the determinant). (And, as ...

11

Yes, cancellations are needed and there are lower bounds for monotone and for non-commutative models where cancellations are impossible. See discussion in Monotone arithmetic circuits. A survey of aritmetic circuit complexity can be found in http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf

11

It is very possible that the determinant is, in a way, harder than the permanent. They are both polynomials, the Waring Rank(sums of n powers of linear forms) of the permanent is roughly 4^n, Chow Rank(sums of products of linear forms) is roughly 2^n. Clearly, Waring Rank \leq 2^{n-1} Chow Rank. For the determinant, those numbers are just lower bounds. On ...

11

Permanent is complete for VNP under p-projections over any field not of characteristic 2. This provides a positive answer to your second question. If this reduction were linear, it would give a positive answer to your first question, but I believe that remains open. In more detail: there is some polynomial $q(n)$ such that $det_n(X)$ is a projection of $... 11 This was shown to be hard (more precisely$\mathsf{NP}$-hard to approximate to better than exponential in$k$) by Marco Di Summa, Friedrich Eisenbrand, Yuri Faenza, Carsten Moldenhauer, "On largest volume simplices and sub-determinants", arXiv:1406.3512 and SODA 2015. (They talk about the largest volume simplex contained in the convex hull, rather than the ... 9 I extend my comment in an answer. By rewriting$e^{i \cdot sgn(\mu)\theta} = \cos(sgn(\mu)\theta)+i\sin(sgn(\mu)\theta) = \cos(\theta)+i \cdot sgn(\mu)\sin(\theta)$we have:$Det_\theta(A) = \cos(\theta)Perm(A)+i\sin(\theta)Det(A)$. Thus, if$\cos(\theta) \neq 0$, we have$Perm(A) = (Det_\theta(A)-i\sin(\theta)Det(A))/\cos(\theta)$, meaning that$Det_\...

9

It is known that the number of arithmetic operations necessary to compute the determinant of an $n\times n$ matrix is $n^{\omega+o(1)}$, where $\omega$ is the matrix multiplication constant. See for example this table on Wikipedia, as well as its footnotes and references. Note that the asymptotic complexity of matrix inversion is also the same as matrix ...

8

It means that to separate permanent from determinant (a la GCT) one must either (a) use actual differences in multiplicities (and not merely their vanishing or non-vanishing) in order to get an inequality that rules out an inclusion of complexity classes, and/or (b) seriously consider multiplicities in the coordinate ring of the orbit closure of the ...

8

I think this may have been a typo in Agrawal's paper. The best I know is how to write an $n \times n$ determinant as a projection of an $O(n^3)$-sized permanent, by writing the determinant as an algebraic branching program (and I think this is currently the best known). See the comments on this answer.

7

There are cases where the symmetries of a problem ( seem to ) characterize its complexity. One very interesting example is constraint satisfaction problems (CSPs). Definition of CSP A CSP is given by a domain $U$, and a constraint language $\Gamma$ ($k$-ary functions from $U^k$ to $\{0, 1\}$). A constraint satisfaction instance is given by a set of ...

6

Depends how you feel about the exponent of matrix multiplication, as this would come very close to showing $\omega=2$. If the answer to your question were positive, then you could compute the determinant of an arbitrary symmetric $n \times n$ $\{0,1\}$ matrix $M$ (=adjacency matrix of an undirected graph, possibly with self-loops) in $O(n^2)$ time. As the ...

5

Determinantal identities can be useful, but perhaps not exactly in the way you think. As far as I know, however, the identities do not all "reduce to" the symmetries of the determinant (except for the fact that the symmetries of the determinant characterize it). Whenever one has some determinantal identities, they can often be massaged into getting equations ...

5

Storjohann designs a Las-Vegas algorithm with $\tilde O(n^\omega M)$ bit operations http://dx.doi.org/10.1016/j.jco.2005.04.002 Prior to this, Kaltofen and Villard gave improved algorithms, see http://lara.inist.fr/bitstream/handle/2332/850/LIP-RR2003-36.pdf%3Fsequence%3D1

4

With a risk of not having understood the details of the question properly: Being able to approximate the determinant within any factor requires being able to decide whether a square matrix is singular or not, which should have some consequences. For one thing, it gives a randomized test for whether a general graph has a perfect matching (via the Tutte ...

3

Consider circuit value problem and Boolean formula evaluation for various small complexity classes. Deterministic sequential time complexity of them are the similar as far as we know, yet they are very different from circuit complexity perspective. Similarity in one particular type of resource on one model doesn't imply similarity for other resources in ...

2

I'd say that the gap in the arithmetic settings tells us that matrix multiplication is inherently a much more parallel task than the determinant. In other words, while the sequential complexities of both problems are closely related, their parallel complexities are not that close from each other. A relevant paper is Fast parallel matrix inversion algorithms ...

1

I think this paper directly answers your question. Cancellation is exponentially powerful for computing the determinant Sengupta shows that even if you use subtraction (hence the circuit is not monotone) but as long as you never "cancel" any computed monomials, then the circuit computing determinant of the matrix of size $n \times n$ has size at least \$n(...

Only top voted, non community-wiki answers of a minimum length are eligible