Bit Complexity of Jordan Normal Form and Spectral Factorization
summary
Gives a concrete, polynomial‑time procedure that either computes a matrix polynomial spectral factor q (to error ε in coefficient norm) or certifies none exists, by reducing to an explicitly bounded algorithm for Jordan normal form. Combines a symbolic Frobenius canonical form, Brand’s confluent Vandermonde description, Mignotte gap lower bounds and numeric conditioning to get an explicit polynomial‑time algorithm (running roughly poly(d,n,a,log(1/ε)), instantiating as about d^6 n^6 in the paper) and a worst‑case exp(O(n^3 a)) condition bound on the similarity; the mixed symbolic/numeric pipeline succeeds with provable bit complexity.
AI-written summary · about
chapters (7)
- 0:00Introduction
- 1:00Spectral factorization
- 4:43Algorithmic results
- 8:01Jordan normal form
- 13:18Complexity and bounds
- 16:42Proof of Lemma
- 22:29Open questions
related talks
01h 31mCircuits of Bounded Depth
30mSymbolic Execution of Hadamard-Toffoli Quantum Circuits
33mLower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems
26mLower Bounds on the Running Time for Scheduling and Packing Problems
01h 02mFine-Grained Counting Complexity I
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
27mOn the Subexponential Time Complexity of the CSP
31mNew Unconditional Lower Bounds for Algorithms and Enumeration Problems