pith. sign in

arxiv: 1610.00159 · v1 · pith:DIYL6UNMnew · submitted 2016-10-01 · 💻 cs.CC

On the complexity of the permanent in various computational models

classification 💻 cs.CC
keywords answercomplexitydeterminantalmodelsresultsshowingaravindcomputation
0
0 comments X
read the original abstract

We answer a question in [Landsberg, Ressayre, 2015], showing the regular determinantal complexity of the determinant det_m is O(m^3). We answer questions in, and generalize results of [Aravind, Joglekar, 2015], showing there is no rank one determinantal expression for perm_m or det_m when m >= 3. Finally we state and prove several "folklore" results relating different models of computation.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.