Timeline for Arithmetic complexity of matrix powering
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 24 at 4:42 | comment | added | Turbo | Instead of M^{2^N} if we are asked M^{2^N} mod q where q is of order 2^N (that is N bits) then is the problem in NC^2? | |
| Feb 23 at 5:08 | comment | added | Joshua Grochow | If M is m x m with n-bit entries, then bit-size of entries of M^d is roughly d(n + log m), so I don't think there's an issue... (Maybe you're thinking of "repeated squaring circuits"? Which are circuits of N size computing x^{2^N}, which can have bit-size 2^N. But that's not what's happening here.) | |
| Feb 23 at 4:48 | comment | added | Turbo | If we power and $d$ is allowed to grow, then wouldn't number of bits to represent matrix entries could be exponential. Correct? Would the answers still hold? | |
| Mar 28, 2016 at 4:36 | comment | added | Joshua Grochow | In the second case (m growing, d fixed), the situation is essentially unchanged if the $x_i$ don't commute. I'd have to think a little about the various equivalences in the other cases. | |
| Mar 28, 2016 at 3:14 | comment | added | user34945 | What if the variables $x_i$ are non-commutative? | |
| Sep 21, 2015 at 22:50 | vote | accept | CommunityBot | ||
| Sep 21, 2015 at 22:50 | vote | accept | CommunityBot | ||
| Sep 21, 2015 at 22:50 | |||||
| Sep 21, 2015 at 22:50 | vote | accept | CommunityBot | ||
| Sep 21, 2015 at 22:50 | |||||
| Sep 21, 2015 at 22:50 | vote | accept | CommunityBot | ||
| Sep 21, 2015 at 22:50 | |||||
| Sep 21, 2015 at 19:33 | history | edited | Joshua Grochow | CC BY-SA 3.0 |
added 322 characters in body
|
| Sep 21, 2015 at 16:41 | history | undeleted | Joshua Grochow | ||
| Sep 21, 2015 at 16:40 | history | deleted | Joshua Grochow | via Vote | |
| Sep 21, 2015 at 16:40 | history | answered | Joshua Grochow | CC BY-SA 3.0 |